從矩形列表中創建一棵樹

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. 重複列表。