LINQ发现矩形定位在彼此

Question

我使用linqtoxml分析现有的XML文件，该文件是基本形式

<Projects> 
    <Project ProjectName="name1"> 
    <ObjectType1List> 
     <ObjectType1 ProjectName="name1" Idx="1"> 
     <Location Top="104" Left="32" Height="64" Wdth="128" /> 
     ... 
     </ObjectType1> 

     <ObjectType1 ProjectName="name1" Idx="2"> 
     ... 
     </ObjectType1> 
    </ObjectType1List> 

    <ObjectType2List> 
     ... 
    </ObjectType2List> 
    </Project> 

    <Project Name ="name2"> 
    </Project> 
    ... 
</Project> 

如果有一个项目中的文件在多个项目和大约10 cannonical对象类型 - 虽然每个项目可能有也可能没有所有不同的对象类型。但是当一个项目包含一个对象类型时，这个对象类型的实例将会有一个有限的列表。

现在我想要做的是找到一个给定的对象类型的所有对象定位在对方的顶部（我知道我只会对2种对象类型感兴趣，并且我假设只有相同类型的对象会彼此叠加）。但是这些物体是通过手工绘制和定位的，所以我不能假定这些物体的尺寸或位置完全相同 - 但我会认为它们会在某些aribtray最大尺寸差异内匹配，所以我有这种感觉我需要通过基于对象的中心位置的某种模糊要求来扫描和分组对象。

而且“我可以有一匹小马”的要求是我只对看到另一个以上的多个对象感兴趣。在给定对象类型的列表中，可能有一组对象位于彼此的顶部，还有一堆其他对象不重叠 - 我不想了解后面那些对象。

因此，对于由一个XDocument我想到像2遍方法加载的文件（和我不知道如果我有顶等人的正确语法）：

var objects = from object in xdoc.Descendants() 
    where object.Name = "ObjectType1" or object.Name = "ObjectType2" 
    select new 
    { 
     Project = object.Attribute("ProjectName").Value.ToString(), 
     ObjectType = object.Name, 
     Index = (int)object.Attribute("Idx").Value, 
     Top = (int)object.Element("Location").Attribute("Top").Value, 
     Left = (int)object.Element("Location").Attribute("Left").Value, 
     Width = (int)object.Element("Location").Attribute("Width").Value, 
     Height = (int)object.Element("Location").Attribute("Height").Value 
    }; 


    var stacked = from object in objects 
    group object by ??????? 

它的？ ?????我不知道该怎么写。我知道我想按照Project和ObjectType进行分组，然后通过Top，Left，Width和Height的一些数学函数进行分组。这是一个双重的问题，因为我知道我不明白，在LINQ多个分组，然后物体的对比将是这样的：

abs(obj1.Left + obj1.Width/2 - obj2.Left - obj2.Width/2)<epsilon && 
abs(obj1.Top + obj1.Height/2 - obj2.Top - obj2.Height/2)<epsilon 

所以有什么建议？

注意的是，虽然我目前的项目.NET 3.5我没有retrictions会阻止我去4.0

EDIT1

从Timwi的回答提出的问题。对于任何对象类型，我预计会有一堆对象位于彼此之上，但不会与其他对象不重叠。因此对于重叠的对象A，B，C，您将有而不是有A重叠，C重叠和A & C不重叠。因此A总是重叠B和C，B总是重叠C并且C总是重叠A & B.然而，可能存在位于别处的不重叠A，B的对象D，E和F或C（或彼此），但可能有第三个（或更多）对象G，H和I自己重叠。因此，对于给定的项目和给定的对象类型以及对象A，B，C（它们自己重叠），D，E和F（与任何其他对象不重叠）以及G，H和I （其overap本身并没有其他目的以及）我想看到的输出分组，如：

Project 
    ObjectType1List 
    Group1 
     A, B, C 
    Group2 
     G, H, I 

在实际数据可能有许多这样的基团对于给定的对象类型。

Answer 1

如果输入完全矩形不相交的组组成，每组每矩形每隔相交之内，那么你就需要每个矩形与每组最多一个比较。因此：

var groups = new Dictionary<Rectangle, List<Rectangle>>(); 
foreach (var rectangle in input) 
{ 
    var key = groups.Keys.FirstOrDefault(k => k.IntersectsWith(rectangle)); 
    if (key.IsEmpty) 
     groups[rectangle] = new List<Rectangle> { rectangle }; 
    else 
     groups[key].Add(rectangle); 
} 

既然你提到你想省略仅具有单一的矩形组，你可以筛选出来结尾：

foreach (var pair in groups.Where(kvp => kvp.Value.Count == 1).ToList()) 
    groups.Remove(pair.Key); 

Answer 2

我无法帮助您进行分组，因为您的分组标准不够明确。如果有三个矩形，其中A重叠B和B重叠C但A不重叠C，会发生什么？在开始为它设计算法之前，您需要清楚这些问题。

但是，您不需要编写数学来确定两个矩形是否相交。你可以使用System.Drawing.Rectangle为：

var objects = from object in xdoc.Descendants() 
    where object.Name = "ObjectType1" or object.Name = "ObjectType2" 
    select new 
    { 
     Project = object.Attribute("ProjectName").Value.ToString(), 
     ObjectType = object.Name, 
     Index = (int)object.Attribute("Idx").Value, 
     Rectangle = new Rectangle(
      (int)object.Element("Location").Attribute("Top").Value, 
      (int)object.Element("Location").Attribute("Left").Value, 
      (int)object.Element("Location").Attribute("Width").Value, 
      (int)object.Element("Location").Attribute("Height").Value 
    ) 
    }; 

然后你就可以很容易找到重叠的对：

var overlapping = from obj1 in objects 
        from obj2 in objects 
        where obj1 != obj2 && obj1.Rectangle.IntersectsWith(obj2.Rectangle) 
        select new { One = obj1, Two = obj2 }; 

当然，这将返回每个重叠对两次，一，二交换。