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

发布于 2024-12-23 11:29:20 字数 331 浏览 1 评论 0 原文

我有一个 X x Y 空间，其中 X 和 Y 由给我的矩形的大小决定。我将一定大小的定向矩形插入到空间中，一次一个。每次插入都尽可能向左，然后尽可能向上（尽可能接近 (0,0)）。表示这一点的最佳方式是什么？我正在用 Python 实现这个。这个问题很有帮助，但我希望得到一些特定于 Python 的建议，因为我对这门语言本身也很陌生。

谢谢！

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

彡翼 2024-12-30 11:29:20

如果您想有效地打包矩形，可以使用一些已建立的算法。以下是一种特定算法的 Python 实现。还有一篇关于打包光照贴图的文章这里，我有一个Python版本（老实说，我不记得是我自己移植的，还是从其他地方获取的）。

回复收藏 0 原文

萌面超妹 2024-12-30 11:29:20

在这样的二维空间中工作，您有两种选择。

列表的列表。 [ [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) ) 或类似的东西来构建它。

您可以使用某种填充算法来屏蔽矩形，该算法将值设置到矩形空间块中。
```
对于范围内的 x（低、高）：
    对于 y 在范围内（低，高）：
        space[x][y]= FILLED # 或您放置在那里的任何对象。
```
映射。 { (0,0): 0, (0,1): 0, ... (X,Y): 0 }。每个点都是空间[x,y]。您可以使用 space = dict( ( (x,y), EMPTY ) for x in range(X_size) for y in range(Y_size) ) 构建它。

您可以使用几乎相同的填充算法来遮盖矩形。只需稍微更改语法即可。

You have two choices for working in two-dimensional space like this.

A list of lists. [ [0, 0, ..., 0], [0, 0, ..., 0], ... [0, 0, ..., 0] ] The outer list is the 'X' access, the inner list is the 'Y' access. Each point is space[x][y]. You build it with space = list( list( EMPTY for j in range(Y_size) ) for i in range(X_size) ) or something similar.

You mask off rectangles with some filler algorithm that sets values into a rectangular patch of space.
```
for x in range( low, high ):
    for y in range ( low, high ):
        space[x][y]= FILLED # or whatever object you're putting there.
```
A mapping. { (0,0): 0, (0,1): 0, ... (X,Y): 0 }. Each point is space[x,y]. You build it with space = dict( ( (x,y), EMPTY ) for x in range(X_size) for y in range(Y_size) ).

You mask off rectangles with almost the same filler algorithm. Just change the syntax slightly.