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

Question

我有一个重叠矩形的理论网格,可能看起来像这样:

但我必须使用的是Rectangle对象的集合:

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只是我如何使用这种结构的一个例子.

我坚持的是如何有效地确定哪个矩形属于哪个.

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

编辑通常会有数百个矩形,我应该遍历每个矩形以查看它是否包含在另一个矩形中？

编辑有人建议包含(不是我最好的时刻,错过了!),但我不确定如何最好地构建DOM.例如,取第一个矩形的孙子,父母确实包含孙子,但它不应该是直接的孩子,它应该是父母的第一个孩子的孩子.

Answer 1

使用Contains()a Rectangle.

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

更新:
供将来参考...
有趣的是,如果您想要检查矩形是否与另一个矩形部分碰撞,Rectangle也可以添加IntersectsWith(Rectangle rect).

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)解决方案(毕竟它只是一个排序操作),但它有点复杂.