我有一个重叠矩形的理论网格,可能看起来像这样:
但是我所需要处理的只是 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。例如,取第一个矩形的孙子,父级确实包含孙子,但它不应该是直接子级,它应该是父级第一个子级的子级。
使用
Contains()
的 Rectangle
。
Rectangle rect1, rect2;
// initialize them
if(rect1.Contains(rect2))
{
// do something...
}
更新: 备查... 有趣的是,如果您想检查一个矩形是否与另一个矩形部分碰撞,
Rectangle
也有 IntersectsWith(Rectangle rect)
。
正如@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) 解决方案(毕竟这只是一个排序操作),但它有点复杂。
平均情况 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
“包含”关系询问一个矩形是否包含另一个矩形。 “Parent”、“child”和“sibling”指的是树结构。
已编辑:修复了一个错误,该错误会错过将某些节点移动到 current_rect 中。
检查矩形中的每个点是否都在其他矩形的边界内。 在 .NET 中,矩形类有一个 .Contains(Point) 方法。或者您可以根据目标矩形的 .Left、.Right、.Top 和 .Bottom 属性检查角点坐标。
伪代码:
for i = 0 to rectangles.length - 2
for j = i + 1 to rectangles.length - 1
if rectangles[i].Contains(rectangles[j])
//code here
}}}