如何排列 N 个矩形以覆盖最小面积 [英] How to arrange N rectangles to cover minimum area

问题描述

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

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

I have N rectangles, each of a random size (random width & height). All rectangles are parallel to the X & Y axes. I'm looking for an algorithm that helps me arrange these rectangles side-by-side in a way that the resulting bounding rectangle has minimum area and the potential gaps around / between the input rectangles are as small as possible. Rectangles cannot be rotated and may not overlap each other.

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

(I need these to automate the arrangement of game sprites so I can create sprite sheets and save sprite locations from the various images I get from animators.)

例如:

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

                                       Unused: 8                 Unused: 18

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

Unused space is marked by the dots (.) in the drawing. Since the first result has a bounding rectangle with smaller unused space, it'd be preferable to find this arrangement of the input rectangles.

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

Is there an algorithm already that helps with this? I did a lot of googling but most results are related to finding minimum bounding rectangle or to finding if N rectangles cover a pre-determined area.

推荐答案

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

The solution suggested at What algorithm can be used for packing rectangles of different sizes into the smallest rectangle possible in a fairly optimal way? looks nice, but I would change it slightly: Rather than greedily extend the bounding box by the smallest area, greedily extend it to the smallest area leaving space greater than the area used by the remaining rectangles. Also, select the next rectangle by greatest dimension, not greatest area.

这应该会在早期为其提供更多空间，并防止它在最后一分钟总是用完空间并留下几乎为空的余量.

That should give it more room early on, and prevent it from always running out of space at the last minute and leaving a mostly-empty margin.

这篇关于如何排列 N 个矩形以覆盖最小面积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！