如何确定一个矩形是否完全包含在另一个矩形内？

Question

我有一个理论上的矩形网格，可能看起来像这样：

但是我手头只有一堆矩形对象：

var shapes = new List<Rectangle>();
shapes.Add(new Rectangle(10, 10, 580, 380));
shapes.Add(new Rectangle(15, 20, 555, 100));
shapes.Add(new Rectangle(35, 50, 40, 75));
// ...

我想要做的是构建一个类似DOM的结构，每个矩形都有一个ChildRectangles属性，其中包含在网格内的子矩形。

最终结果应该允许我将这样的结构转换为XML，类似于：

<grid>
  <shape rectangle="10, 10, 580, 380">
    <shape rectangle="5, 10, 555, 100">
      <shape rectangle="20, 30, 40, 75"/>
    </shape>
  </shape>
  <shape rectangle="etc..."/>
</grid>

但主要是我想要一个类似DOM的内存结构，输出的XML只是我可能使用这种结构的示例。

我卡住的是如何高效地确定哪些矩形属于哪些矩形。

注意：没有矩形部分包含在另一个矩形中，它们总是完全在另一个矩形内。

编辑：通常会有数百个矩形，我应该只遍历每个矩形以查看它是否被另一个矩形包含吗？

编辑：有人建议使用Contains（这不是我最好的时刻，错过了！），但我不确定如何最好地构建DOM。例如，取第一个矩形的孙子，父代确实包含孙子，但它不应该是直接的孩子，它应该是父级的第一个孩子的子级。

- Matt Brindley

---

关于注释：那么你只需要检查一个角点。关于编辑：是的，但是您可能希望标记每个矩形已处理完成，这样您的外部循环可以跳过已经完成DOM操作的矩形。 - Sam Axe

Answer 1

使用Rectangle的Contains()方法。

Rectangle rect1, rect2;
// initialize them
if(rect1.Continas(rect2))
{
    // do...
}

更新:
供将来参考...
有趣的是，Rectangle类还提供了IntersectsWith(Rectangle rect)方法，以便您检查一个矩形是否部分与另一个矩形碰撞。

- BeemerGuy

---

那简直比其他答案都要好太多了。我现在删除我的回答。 - Domenic

当我说“哎呀！”时，我想我代表了在场的每个人！ - 3Dave

哈哈，谢谢 :-) 不过我还不确定如何使用这个构建DOM，即使一个矩形包含在另一个矩形中，它也可能不是直接的子元素，它可能是孙子、曾孙等。 - Matt Brindley

@Matthew -- 希望我知道DOM操作，我只是想提一下Contains()方法。其他人应该在我的答案上继续建立。 - BeemerGuy

Answer 2

如@BeemerGuy所指出的那样，Rect.Contains可以告诉您一个矩形是否包含另一个矩形。建立层次结构需要更多的工作...

有一个O(N^2)的解决方案，对于每个矩形，您都要搜索其他矩形的列表，以查看它是否适合其中。每个矩形的“所有者”是包含它的最小矩形。伪代码：

foreach (rect in rectangles)
{
    owner = null
    foreach (possible_owner in rectangles)
    {
        if (possible_owner != rect)
        {
            if (possible_owner.contains(rect))
            {
                if (owner === null || owner.Contains(possible_owner))
                {
                    owner = possible_owner;
                }
            }
        }
    }
    // at this point you can record that `owner` contains `rect`
}

虽然效率不是特别高，但对于您的目的可能已经足够快了。我很确定我见过O(n log n)的解决方案（毕竟只是排序操作），但它更加复杂。

- Jim Mischel

---

您可以通过按照面积从大到小对矩形进行排序来限制搜索范围。然后，对于任何一个矩形，它不能容纳列表中更高的任何东西（除非它们是相同的，这可能是一个奇怪的特例）。 - Mark T

Answer 3

一个平均情况下O(n log n)的解决方案：

将您的矩形集视为一棵树，其中父节点“包含”子节点 - 与DOM结构相同。 您将逐个矩形地构建树。

创建一个虚拟节点作为树的根。 然后，对于每个矩形（“current_rect”），从根的子节点开始向下工作，直到找到其所属位置：

parent_node = root_node
sibling_nodes = [children of parent_node]

for this_node in sibling_nodes:
    if current_rect contains this_node:
        move this_node: make it a child of current_rect instead of parent_node
    elseif this_node contains current_rect:
        parent_node = this_node
        sibling_nodes = [children of parent_node]
        restart the "for" loop using new set of sibling_nodes

make current_rect a child of parent_node

"包含"关系是指一个矩形是否包含另一个矩形。 "父级"、"子级"和"兄弟"是指树形结构。

已编辑：修复了一个漏移动一些节点到current_rect的错误。

- Jander

---

一个有趣的想法。我认为你可以通过从节点列表和空树开始来简化你的算法。这将大大减少重新启动的次数。 - Jim Mischel

实际上，这将减少重新启动后您需要进行的处理量。 - Jim Mischel

@Jim：实际上，我试图表达的就是这个意思，如果我理解你的意思的话。从一个列表和一个空树开始，将一个节点从列表中取出并添加到树中，重复此过程直到列表为空？但也有可能我漏掉了一些重要的东西，因为我不知道你所说的“重新启动”是什么意思。 - Jander

也许我误解了你的伪代码。重新启动意味着使用新的兄弟节点集合来重新开始“for”循环处理，这是我的理解。这不是什么大问题，我已经为你的答案点赞，因为它提供了基本思路，并且应该很容易实现。 - Jim Mischel

Answer 4

检查矩形中的每个点是否在其他矩形的边界内。 在.NET中，Rectangle类具有.Contains(Point)方法。或者您可以将角点坐标与目标矩形的.Left、.Right、.Top和.Bottom属性进行比较。

- Sam Axe

Answer 5

伪代码：

for i = 0 to rectangles.length - 2
 for j = i + 1 to rectangles.length - 1
     if rectangles[i].Contains(rectangles[j])
        //code here
}}}

- Ali Tarhini