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

  • Z时代
  • 2024-01-10
  • 分类：问答

我有 N个

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

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

例如：

+---+   +----------+
| 1 |   |    2     |
+---+   +----------+                 +----------+..           +---+----------+
                                     |    2     |..           | 1 |    2     |
+--------+                ===>       +--------+-+-+    vs     +---+----+-----+
|        |                           |        | 1 |           |        |......
|    3   |                           |    3   +---+           |    3   |......
+--------+                           +--------+....           +--------+......
                                       Unused: 8                 Unused: 18

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

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

回答：

在提出的解决方案是什么算法可用于包装不同大小的矩形到最小矩形可能在一个相当最佳方式？看起来不错，但我会稍作更改：与其贪婪地将边界框扩大到最小区域，不如贪婪地将边界框扩大到最小区域， 而留下的空间要大于其余矩形所使用的区域

。另外，请按最大尺寸而不是最大面积选择下一个矩形。

这样可以在早期为它提供更多的空间，并防止它在最后一刻总是耗尽空间并留出大部分为空的余量。

以上是 如何排列N个矩形以覆盖最小面积 的全部内容， 来源链接： utcz.com/qa/422104.html

回到顶部