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

Question

可能是重复问题:
需要一种算法以相对最优的方式放置矩形

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

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

例如：

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

                                       Unused: 8                 Unused: 18

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

是否已经存在可帮助完成此任务的算法？我进行了大量搜索，但大多数结果都与查找最小边界矩形或查找N个矩形是否覆盖预定区域有关。

- xxbbcc

---

请参见 https://dev59.com/InM_5IYBdhLWcg3w02z8，该网页提供了一个用于相对最优地排列矩形的算法。 - wich

这类问题类似于（比较自由）集成电路布局问题。您想要一个简单的工具来解决此问题，但我不确定在哪里可以找到。 - Potatoswatter

你看到这个了吗: https://dev59.com/eHVC5IYBdhLWcg3wjyDu? 这或许会有所帮助。 - Ajoy

@Potatoswatter，工具固然好用，但我也觉得这个问题很有趣，想看看如何通过编程来解决它。 - xxbbcc

@wich 谢谢，我会去查看一下。在我得到的搜索结果中没有看到它。 - xxbbcc

Answer 1

在如何将不同大小的矩形打包到最小的矩形中以达到相对最佳效果？所提出的解决方案看起来很好，但我会稍微改变它：不是贪婪地通过最小面积扩展边界框，而是贪婪地将其扩展到最小面积留下大于剩余矩形使用面积的空间。此外，选择下一个矩形时应根据其最大尺寸而非最大面积进行选择。

这样可以在开始时给它更多的空间，并防止它总是在最后一分钟用完空间并留下大量空白边距。

- Potatoswatter