如何有效地存储已占用/未占用的二维空间（带插入）

Question

我有一个X乘Y空间，其中X和Y是由给定矩形的大小决定的。我正在向空间中插入一定大小的定向矩形，一次一个。每次插入尽可能左，然后尽可能向上（尽可能接近（0,0）。最好的表达方式是什么？我用Python实现这个。对this问题的最重要的答案是有帮助的，但是我希望得到一些特定于Python的建议，因为我对该语言本身也是相当陌生的。在

谢谢！在

Answer 1

Quadtrees通常用于这类事情。听起来你想要一个区域四叉树。在

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

如果你想有效地包装矩形，有一些既定的算法。下面是一个特定的algorithm的Python实现。还有一篇关于打包光照贴图here的文章，我有一个Python version（我真的不记得是我自己移植的，还是从其他地方得到的）。在