从矩形列表中创建一棵树

Question

这可能是一个愚蠢的问题，但没有任何想法马上浮现。由于设置成任何给定的矩形或者是内外完全或完全以外的任何其他2D矩形（x，y，w，h）的列表R，什么是最有效的方式来确定的立即封闭矩形R每个矩形的p？目前我排序Ry然后x，然后通过每一对（a,b）和测试是否a是b的孩子。这不但效率不高，而且也不能正常工作：我认为，由于R已经排序，最后找到的父应该是立即封闭的，但这似乎不成立。我的推理有什么问题吗？如果没有，我会发布代码。

Answer 1

1. 排序方式(x+y)。
2. 从排序列表的开始处开始，抓住一个矩形Q.
3. 计算该矩形的(x+y+w+h)。
4. 对于矩形Q后面的部分列表中的每个矩形R，并且具有x+y for R < = (x+y+w+h) of Q，请检查R是否在Q的范围内。如果是，则将Q设置为R的父项，覆盖任何以前设置的父母。
5. 重复列表。