什么algorithm可以用于以相当优化的方式将不同大小的矩形打包成最小的矩形？

我得到了一堆矩形物体，我需要把它放到最小的空间里（这个空间的尺寸应该是2的幂）。

我知道各种打包algorithm，将尽可能多的物品打包到一个给定的空间，但在这种情况下，我需要algorithm来计算出这个空间应该有多大。

例如说，我有以下矩形

• 128 * 32
• 128 * 64
• 64 * 32
• 64 * 32

它们可以打包成一个128 * 128的空间

  _________________
 | 128 * 32 |
 | ________________ |
 | 128 * 64 |
 |  |
 |  |
 | ________________ |
 | 64 * 32 | 64 * 32 |
 | _______ | ________ |

但是，如果还有一个160 * 32和一个64 * 64的话，那就需要一个256 * 128的空间

  ________________________________
 | 128 * 32 | 64 * 64 | 64 * 32 |
 | ________________ |  | _______ |
 | 128 * 64 |  | 64 * 32 |
 |  | _______ | _______ |
 |  |  |
 | ________________ | ___ |
 | 160 * 32 |  |
 | ____________________ | ___________ |

哪些algorithm能够打包一堆矩形，并确定容器所需的大小（对于2的幂，并且对于每个维度在给定的最大尺寸内）？

Answer 1

如果没有别的办法，那么快速而肮脏的第一遍解决scheme总是一个很好的开始。

贪婪的从大到小的摆放。

把最大的矩形留在你的包装区域。 如果无法放在任何地方，请将其放置在尽可能less地延伸包装区域的地方。 重复，直到你完成最小的矩形。

这不是完美的，但它很容易和一个很好的基线。 它仍然会把你最初的例子完美地包装起来，并且给你第二个同样的答案。

Answer 2

在ARC项目中查看这个页面以获得对解决scheme的调查，在实现复杂性/时间和最优性之间进行权衡，但有多种algorithm可供select。

以下是algorithm的摘录：

1. 首次拟合降低高度（FFDH）algorithm
   FFDH在R适合的第一个级别打包下一个项目R（在非增加的高度）。 如果没有级别可以容纳R，则创build一个新的级别。
   FFDH的时间复杂度：O（n·log n）。
   近似比：FFDH（I）<=（17/10）·OPT（I）+1; 17/10的渐近线是紧的。

2. Next-Fit降低高度（NFDH）algorithm
   如果R符合，NFDH会将当前级别的下一个项目R（在非增加的高度）打包。 否则，目前的水平是“closures”，并创build一个新的水平。
   时间复杂度：O（n·log n）。
   近似比：NFDH（I）≤2·OPT（I）+1; 2的渐近界是紧的。

3. 最佳适应降低高度（BFDH）algorithm
   BFDH将水平上的下一个项目R（在不增加的高度上）包装在能容纳R的项目中，剩余的水平空间是最小的。 如果没有级别可以容纳R，则创build一个新的级别。

4. 左下（BL）algorithm
   BL第一次订购的产品不增加宽度。 BL将下一个物品放在靠近底部的位置，因为它可以放入，然后尽可能地靠近左侧，因为它可以与任何包装物品不重叠。 请注意，BL不是一个面向级别的打包algorithm。
   时间复杂度：O（n ^ 2）。
   近似比例：BL（I）<= 3·OPT（I）。

5. 贝克上下（UD）algorithm
   UD使用BL和NFDH的泛化的组合。 条的宽度和项目被标准化，使得条的宽度是单位的。 UD将项目以非增加的宽度sorting，然后将项目分成五组，每组的宽度在范围（1/2,1），（1 / 3,1 / 2]，（1 / 4,1 / 3 ]，（1 / 5,1 / 4]，（0,1 / 5），也分为5个区域R1，…，R5，基本上有一些宽度在（1 / i + 1,1 / i]，1 <= i <= 4，被BL打包到区域Ri，由于BL在条带右侧留下了从上到下宽度增加的空间，所以UD利用这个优势如果没有这样的空间，那么这个项目被BL打包到Ri，最后，项目大小最多为1/5用（广义的）NFDHalgorithm打包到R1，…，R4中的空格中，再次如果在这些区域中没有空间，则使用NFDH打包R5。
   近似比：UD（I）<=（5/4）·OPT（I）+（53/8）H，其中H是物品的最大高度; 5/4的渐近界是紧的。

6. 反向拟合（RF）algorithm
   RF还规格化条带和物品的宽度，使条带具有单位宽度。 RF首先堆叠宽度大于1/2的所有项目。 剩余的物品按非增加的高度进行分类，并且将在大于1/2的高度达到高度H0以上。 然后RF重复以下过程。 粗略地说，射频从左到右打包物品的底部沿着高度H0的线，直到没有更多的空间。 然后从右到左，从上到下打包（称为反转级别），直到总宽度至less为1/2。 然后倒下，直到（至less）其中一个触及下面的某个项目。 下降是不知何故重复。
   近似比：RF（I）<= 2·OPT（I）。

7. 斯坦伯格的algorithm
   Steinberg的algorithm（在文章中用M表示）估计打包所有项目所需的高度H的上限，以便certificateinput项目可以打包成宽度W和高度H的矩形。然后，他们定义了七程序（有七个条件），每个程序把一个问题分成两个小问题，recursion求解。 已经表明，任何易处理的问题都满足七个条件之一。
   近似比：M（I）<= 2·OPT（I）。

8. 拆分algorithm（SF）SF将项目分为两组，L1宽度大于1/2，L2最多为1/2。 L1的所有项目都是由FFDH首先打包的。 然后将它们排列成使得宽度大于2/3的所有项目在宽度最多为2/3的那些之下。 这将创build一个宽度为1/3的矩形R空间。 然后将L2中的剩余项目打包到R，并使用FFDH打包L1以上的空间。 在R中创build的等级被认为低于在L1的包装之上创build的等级。
   近似比：SF（I）<=（3/2）·OPT（I）+ 2; 3/2的渐近界是紧的。

9. Sleator的algorithm
   Sleater的algorithm由四个步骤组成：

   1. 所有宽度大于1/2的物品都在条的底部堆叠在一起。 假设h0是结果包装的高度所有后续的包装将发生在h0以上。

   2. 剩余的物品按不增加的高度sorting。 物品的高度按照高度h0从左到右被包装（高度不增加）。

   3. 然后在中间画一条垂直线，将条切成两半（注意这条线可能会切割右半部分包装的物品）。 绘制两条长度为一半的水平线段，一条横跨左半部分（称为左侧基线）和一条横跨右侧（称为右侧基线）的水平线段尽可能低，使得两条线不交叉任何项目。

   4. select较低高度的左侧或右侧基线，并将一定量的物品打包到条带的相应一半，直到下一个物品太宽。

   形成新的基线，并在较低的基线上重复步骤（4），直到所有项目都被打包。
   时间复杂度：O（n·log n）。
   Sleatoralgorithm的逼近比是2.5。

Answer 3

看看包装问题 。 我认为你们属于“二维装箱”。 您应该能够从解决scheme和其他包装问题中学到很多东西。

另请参阅：将矩形图像数据打包成方形纹理。

Answer 4

关于这个问题有大量的文献。 一个好的贪婪的启发是将第一个可用位置的矩形从最大的区域放到最小的区域，朝向容器的底部和左侧。 想想重力将所有物品拉到左下angular。 有关此谷歌“Chazelle左下包装”的描述。

为了获得最佳解决scheme，最先进的技术可以在几秒钟内打包超过20个矩形。 Huang有一个algorithm ，将find最小的封闭边界框的问题与决定一组矩形是否可以放入特定大小的边界框的问题分开。 你给他的程序一组矩形，它告诉你需要打包它们的最小封闭边框。

对于你的情况，你的外部循环应该从最小的可能的边界框向上迭代（宽度和高度依次增加2的幂）。 对于每个边界框，testing以查看是否可以find矩形的包装。 你会得到一堆“没有”的答案，直到第一个“是”的答案，这将是保证是最佳的解决scheme。

对于你的algorithm的内部循环 – 对具有特定大小的边界框回答“是”或“否”的那一个，我将查找黄色参考并且只实现他的algorithm。 他在基本algorithm的基础上包含了很多优化，但是你只需要基本的肉和土豆。 既然你想处理旋转，在search过程中的每个分支点，当两个旋转都不会导致解决scheme时，只需尝试旋转和回溯。

Answer 5

我相当肯定这是一个NP难题 ，所以，对于一个最佳的解决scheme，你必须实现一个回溯algorithm来尝试所有可能的组合。

好消息是，由于需要在有限的2D空间中打包2D矩形，所以可以在早期修剪很多可能性，所以可能并不是那么糟糕。

Answer 6

你需要的是在https://github.com/nothings/stb/blob/master/stb_rect_pack.h

样品：

stbrp_context context; struct stbrp_rect rects[100]; for (int i=0; i< 100; i++) { rects[i].id = i; rects[i].w = 100+i; rects[i].h = 100+i; rects[i].x = 0; rects[i].y = 0; rects[i].was_packed = 0; } int rectsLength = sizeof(rects)/sizeof(rects[0]); int nodeCount = 4096*2; struct stbrp_node nodes[nodeCount]; stbrp_init_target(&context, 4096, 4096, nodes, nodeCount); stbrp_pack_rects(&context, rects, rectsLength); for (int i=0; i< 100; i++) { printf("rect %i (%hu,%hu) was_packed=%i\n", rects[i].id, rects[i].x, rects[i].y, rects[i].was_packed); } 

Answer 7

一般的解决scheme是非平凡的（math说话是完全不可能的）
通常，人们使用遗传algorithm来尝试可能的组合，但是通过将最大的形状放在第一位，然后尝试不同的地方放在第二大的位置等等，你可以做得相当好。