这可能是一个愚蠢的问题，但没有什么会立刻浮现在脑海中。给定二维矩形列表 R (x, y, w, h ) 的排列使得任何给定的矩形要么完全位于其他矩形之内，要么完全位于其他矩形之外，确定 R 中每个矩形的紧邻矩形 p 的最有效方法是什么？目前，我将 R 按 y 排序，然后按 x 排序，然后遍历每一对 (a, b) 并测试 a 是否是 b 的 child 。这不仅效率不高，而且也不能正常工作:我认为由于 R 已经排序，所以找到的最后一个父级应该是立即封闭的父级，但这似乎不是举行。我的推理有问题吗？如果没有，我会发布代码。
最佳答案
- 按
(x+y)排序。 - 从排序列表的开头开始，抓取一个矩形 Q。
- 为该矩形计算
(x+y+w+h)。 - 对于矩形 Q 之后的列表的一部分中的每个矩形 R，并且具有
x+y for R<=(x+y+w+h) of Q，检查 R 是否在 Q 的边界内。如果是，则将 Q 设置为 R 的父级，覆盖之前设置的任何父级。 - 重复列表。
关于c++ - 从矩形列表创建树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3697076/