如何安排N个矩形覆盖最小面积

Question

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

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

(我需要这些来自动化游戏精灵的排列,这样我就可以创建精灵表并从动画师的各种图像中保存精灵位置.)

例如:

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

                                       Unused: 8                 Unused: 18

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

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

Answer 1

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

这应该在早期就给它更多的空间，并防止它总是在最后一刻耗尽空间并留下大部分空白的边距。