如何高效地存儲佔用/未佔用的2D空間（帶插入）

Question

我有一個X乘Y空間，其中X和Y由給定的矩形大小決定。我將一定大小的定向矩形插入空間，一次一個。儘可能將每個插入儘可能留下，然後儘可能地遠（儘可能接近（0,0））。代表這一點的最佳方式是什麼？我正在Python中實現這一點。 this問題的最佳答案很有幫助，但我希望得到一些Python特有的建議，因爲我對語言本身也很陌生。

謝謝！

Answer 1

如果您嘗試有效地打包矩形，有一些已建立的算法。這是一個特定algorithm的Python實現。還有一篇關於打包光照貼圖here的文章，我有一個Python version（我真的不記得自己是移植它，還是從其他地方移植它）。

Answer 2

在這樣的二維空間中工作有兩種選擇。

1. 列表的列表。 [ [0, 0, ..., 0], [0, 0, ..., 0], ... [0, 0, ..., 0] ]外部列表是'X'訪問，內部列表是'Y'訪問。每個點是space[x][y]。你用space = list(list(EMPTY for j in range(Y_size)) for i in range(X_size))或類似的東西來構建它。

   使用一些填充算法遮蓋矩形，該算法將值設置爲矩形的空間補丁。

   for x in range(low, high): 
       for y in range (low, high): 
        space[x][y]= FILLED # or whatever object you're putting there. 
   

2. 映射。 { (0,0): 0, (0,1): 0, ... (X,Y): 0 }。每個點是space[x,y]。你用space = dict(((x,y), EMPTY) for x in range(X_size) for y in range(Y_size))來構建它。

   用幾乎相同的填充算法掩蓋矩形。稍微改變語法。

Answer 3

Quadtrees通常用於這種事情。這聽起來像你想要一個區域四叉樹。