7

可能重复：
以相当优化的方式打包矩形所需的算法

我有N个矩形，每个矩形的大小都是随机的（随机宽度和高度）。所有矩形都平行于 X 和 Y 轴。我正在寻找一种算法，它可以帮助我并排排列这些矩形，使生成的边界矩形具有最小面积，并且输入矩形周围/之间的潜在间隙尽可能小。矩形不能旋转，也不能相互重叠。

（我需要这些来自动排列游戏精灵，这样我就可以创建精灵表并从动画师那里获得的各种图像中保存精灵位置。）

例如：

+---+   +----------+
| 1 |   |    2     |
+---+   +----------+                 +----------+..           +---+----------+
                                     |    2     |..           | 1 |    2     |
+--------+                ===>       +--------+-+-+    vs     +---+----+-----+
|        |                           |        | 1 |           |        |......
|    3   |                           |    3   +---+           |    3   |......
+--------+                           +--------+....           +--------+......

                                       Unused: 8                 Unused: 18

图中未使用的空间由点 (.) 标记。由于第一个结果的边界矩形具有较小的未使用空间，因此最好找到输入矩形的这种排列。

是否已经有一种算法可以帮助解决这个问题？我做了很多谷歌搜索，但大多数结果都与找到最小边界矩形或查找 N 个矩形是否覆盖预定区域有关。

4

1 回答 1

3

什么算法可以用于以相当优化的方式将不同大小的矩形打包成最小的矩形中建议的解决方案？看起来不错，但我会稍微改变一下：与其贪婪地将边界框扩展到最小区域，不如将其贪婪地扩展到最小区域，留下大于剩余矩形使用的区域的空间。此外，按最大尺寸而不是最大面积选择下一个矩形。

这应该在早期为它提供更多空间，并防止它总是在最后一分钟用完空间并留下大部分空白的余量。

于 2013-01-11T03:44:11.597 回答