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

问题描述

可能重复：
  <一href="http://stackoverflow.com/questions/1213394/algorithm-needed-for-packing-rectangles-in-a-fairly-optimal-way">Algorithm在一个相当理想的方式对包装有长方形

我的 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

未使用的空间被标记由点（。）在图中。由于第一个结果具有更小的未用空间边界矩形，这将会是preferable找到输入矩形的这种安排。

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矩形覆盖pre确定的区域。

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.

推荐答案

在<一个解决方案建议href="http://stackoverflow.com/questions/1213394/algorithm-needed-for-packing-rectangles-in-a-fairly-optimal-way">Algorithm需要在看起来不错相当优化的方式包装的矩形，但我会略有改变：而不是由最小面积贪婪地延长边框，贪婪地把它扩展到最小面积的留下空间大于所使用的其余矩形区域的。此外，选择按最大尺寸，而不是面积最大的下一个矩形。

The solution suggested at Algorithm needed for packing rectangles 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.

这应该给它更多的室早，并从始终运行的空间在最后一分钟，留下一个大部分空保证金prevent吧。

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.

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