可能重复:
以相当优化的方式打包矩形所需的算法
我有N个矩形,每个矩形的大小都是随机的(随机宽度和高度)。所有矩形都平行于 X 和 Y 轴。我正在寻找一种算法,它可以帮助我并排排列这些矩形,使生成的边界矩形具有最小面积,并且输入矩形周围/之间的潜在间隙尽可能小。矩形不能旋转,也不能相互重叠。
(我需要这些来自动排列游戏精灵,这样我就可以创建精灵表并从动画师那里获得的各种图像中保存精灵位置。)
例如:
+---+ +----------+
| 1 | | 2 |
+---+ +----------+ +----------+.. +---+----------+
| 2 |.. | 1 | 2 |
+--------+ ===> +--------+-+-+ vs +---+----+-----+
| | | | 1 | | |......
| 3 | | 3 +---+ | 3 |......
+--------+ +--------+.... +--------+......
Unused: 8 Unused: 18
图中未使用的空间由点 (.) 标记。由于第一个结果的边界矩形具有较小的未使用空间,因此最好找到输入矩形的这种排列。
是否已经有一种算法可以帮助解决这个问题?我做了很多谷歌搜索,但大多数结果都与找到最小边界矩形或查找 N 个矩形是否覆盖预定区域有关。