用於擬合一組正方形之間的正方形的圖形算法

Question

假設我在二維座標系（浮點座標）中的有限區域內有n個大小相等且平均旋轉的方形框。這些箱子不應該重疊。 現在我想爲另外一個盒子找一個空閒空間。我需要一些提示來解決這個問題。有任何想法嗎？

Answer 1

這裏應該有一個掃描線算法。你說這些盒子是同樣旋轉的，所以如果有必要，你應該能夠旋轉座標系，使盒子的邊緣平行於x和y座標。然後，我會按照y座標的順序對這些框進行排序。

現在嘗試將盒子放在儘可能最低的位置。從已排序的框中讀取，找到所有足夠低的框以干擾您的放置，並創建這些框的有序集（例如，紅黑樹或類似的容器類）。現在掃描這組盒子，看看是否有足夠大的空隙放置盒子。如果沒有，請使用原始的已排序列表框來查找和刪除最下面的框，以便您可以考慮將新框放在最下面的框的上方，以免干擾。從排序列表中添加更多框以覆蓋所有高度足以干擾框的新可能高度的框。跟蹤您從列表中刪除框的位置，並檢查是否有足夠大的空隙來放置框。如果沒有，重複練習，直到找到可能區域頂部的間隙或空間不足。

這看起來像初始排序的成本N log N，然後每個盒子的成本至多爲log N，以便從有序集合中插入和刪除盒子。檢查間隙不會比這更昂貴，因爲您只檢查剛刪除箱子的位置的間隙。所以我認爲總成本是N日誌N.