代码之家 › 专栏 › 技术社区 › Matt Brindley

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

geometry .net c#

Matt Brindley · 技术社区 · 14 年前

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

grid layout

但我所要做的就是收集矩形对象:

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的结构,其中每个矩形都有一个childrectanges属性,该属性包含网格中包含的矩形。

最终结果应该允许我将这样的结构转换为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。例如,以第一个矩形的孙子为例,父对象确实包含孙子,但它不应该是直接子对象,而应该是父对象的第一个子对象。

5 回复 | 直到 14 年前

Jim Mischel 14 年前

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

BeemerGuy 14 年前

使用 Contains() 一个 Rectangle .

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

更新 :
供将来参考。。。
有意思的是 矩形 也有 IntersectsWith(Rectangle rect) 如果您想检查一个矩形是否与另一个矩形部分碰撞。

Jander 8 年前

平均情况O(n logn)解决方案:

将矩形集想象成一棵树,父节点“包含”子节点——这与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

“contains”关系询问一个矩形是否包含另一个矩形“父”、“子”和“兄弟”指的是树结构。

编辑 :修复了一个错误,该错误将无法将某些节点移动到当前目录中。

Sam Axe 14 年前

检查矩形中的每个点是否在其他矩形的边界内。在.NET中,矩形类有一个.Contains(Point)方法。或者可以再次检查目标矩形的.Left、.Right、.Top和.Bottom属性的角点坐标。

Ali Tarhini 14 年前

伪代码:

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