如何确定一个矩形是否完全包含在另一个矩形中？
我有一个重叠矩形的理论网格，可能看起来像这样：
但我必须使用的是Rectangle对象的集合：
var shapes = new List(); 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，类似于：
但它主要是我想要的内存中类似DOM的结构，输出XML只是我如何使用这种结构的一个例子。
我坚持的一点是如何有效地确定哪个矩形属于哪个。
注意没有矩形部分包含在另一个中，它们总是完全在另一个内部。
编辑通常会有数百个矩形，我应该遍历每个矩形以查看它是否包含在另一个矩形中？
编辑有人建议包含（不是我最好的时刻，错过了！），但我不确定如何最好地构建DOM。 例如，取第一个矩形的孙子，父母确实包含孙子，但它不应该是直接的孩子，它应该是父母的第一个孩子的孩子。
正如@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）解决方案（毕竟它只是一个排序操作），但它有点复杂。
使用Rectangle的Contains() 。
Rectangle rect1, rect2; // initialize them if(rect1.Continas(rect2)) { // do... }
更新 ：
备查…
有趣的是，如果要检查矩形是否与另一个矩形部分碰撞，则Rectangle还具有IntersectsWith(Rectangle rect) 。
平均情况O（n log n）解决方案：
将您的矩形集视为树，其中父节点“包含”子节点 – 与DOM结构相同的东西。 您将一次构建一个矩形的树。
创建一个虚拟节点作为树的根。 然后，对于每个矩形（“current_rect”），从root的子项开始向下工作，直到找到它的去向：
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。
检查矩形中的每个点是否在其他矩形的边界内。 在.NET中，Rectangle类有一个.Contains（Point）方法。 或者，您可以在目标rect的.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 }}}