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 个规范对象类型 - 尽管每个项目可能有也可能没有所有不同的对象类型。但是，如果项目确实包含对象类型，则该对象类型的实例的列表是有限的。

现在我想做的是找到给定对象类型的所有对象，这些对象位于彼此之上（并且我知道我只会对其中 2 个对象类型感兴趣，并且我假设只有相同类型将相互叠加）。但是这些对象是手工绘制和定位的，所以我不能假设这些对象具有完全相同的尺寸或位置 - 但我会假设它们将在某个 aribtray 最大尺寸差异内匹配，所以我有这种感觉我需要根据对象的中心位置，按照某种模糊要求对对象进行扫描和分组。

而“我也可以有一匹小马吗”的请求是，我只对看到多个物体叠加在另一个物体上感兴趣。在给定对象类型的列表中，可能有一组彼此重叠的对象，以及一堆不重叠的其他对象 - 我不想知道后面的对象。

因此，对于由 XDocument 加载的文件，我正在考虑采用 2 遍方法（并且我不确定我是否有 Top 等人的正确语法）

  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 ???????

：有点不知道怎么写。我知道我想按项目和对象类型进行分组，然后按顶部、左侧、宽度和高度的一些数学函数进行分组。这是一个双重问题，因为我知道我不理解 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，但我没有任何限制可以阻止我从 Timwi 的回答中提出的问题转向 4.0

Edit1

。对于任何对象类型，我预计会有一堆对象彼此位置很好，但不会与不在同一堆中的其他对象重叠。因此，对于重叠的对象 A、B、C，您将没有有 A 和 C。 B重叠，B& C重叠且A& C 不重叠。

因此A将始终与B和C重叠，B将始终与A和C重叠。 C 和 C 总是与 A 和 C 重叠。 B. 然而，可能存在位于其他地方且不与 A、B 或 C（或彼此）重叠的对象 D、E 和 F，但可能存在第三（或更多）组对象 G、H 和 I，它们自身重叠。

因此，对于给定的项目、给定的对象类型以及对象 A、B、C（与自身重叠）、D、E 和 F（不与任何其他对象重叠）以及 G、H 和 I（与自身重叠）并且也没有其他对象）我希望看到如下分组的输出：

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

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

Answer 1

我无法帮助您进行分组，因为您的分组标准定义不够明确。如果有三个矩形，其中 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 };

当然，这将返回每个重叠对两次，其中“一”和“二”交换。

Answer 2

如果您的输入完全由不相交的矩形组组成，并且在每个组中每个矩形都与每个其他相交，那么您需要将每个矩形与每组中最多一个进行比较。因此：

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);