什么算法可以用来将不同大小的矩形以一种相当优化的方式填充到尽可能小的矩形中?

我有一堆长方形的物体，我需要把它们塞到尽可能小的空间里(这个空间的维数应该是2的幂)。

我知道各种包装算法，将包装项目以及尽可能到一个给定的空间，但在这种情况下，我需要算法来计算出该空间应该有多大。

假设我有下面这些矩形

  • 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              |           |
|____________________|___________|

有什么算法能够打包一堆矩形并确定容器所需的大小(以2为幂，并且在每个维度的给定最大尺寸范围内)?

111464 次浏览
小开

我相当确定这是np难题，因此，对于一个最优解，你必须实现一个回溯算法，尝试每一个可能的组合。

好消息是，由于需要在有限的2D空间中填充2D矩形，你可以在早期删除许多可能性，所以这可能并不是那么糟糕。

小开

看看包装问题。我认为你的属于“2D箱子包装”。你应该能从这个和其他包装问题的解决方案中学到很多东西。

也请参见:将矩形图像数据打包到正方形纹理中。

小开

通解是非平凡的(数学上讲完全****ing不可能)
通常人们使用遗传算法来尝试可能的组合，但你可以做得相当好，只要把最大的形状放在前面，然后在不同的地方尝试第二大的形状，等等

小开
最佳答案

快速和肮脏的第一遍解决方案总是一个很好的开始，如果没有其他的比较。

贪心安置由大到小。

把剩下的最大的矩形放入打包区域。如果它放不下任何地方，就把它放在一个尽可能不扩大背包区域的地方。重复这一步骤，直到你完成最小的矩形。

它一点也不完美，但它很简单，是一个很好的底线。它仍然会完美地包装你原来的例子，并为第二个例子提供相同的答案。

小开

关于这个问题有大量的文献。一种好的贪婪启发式方法是将矩形从大到小放置在容器底部和左侧的第一个可用位置上。想象重力把所有的东西都拉到左下角。对于这个谷歌“沙雷左下角包装”的描述。

为了获得最佳解决方案，最先进的技术可以在几秒钟内完成20多个矩形。Huang有一个算法，它将寻找最小的外围包围框的问题与确定一组矩形是否适合特定大小的包围框的问题分开。你给他的程序一组矩形，它会告诉你打包这些矩形所需要的最小的包围框。

对于您的情况，外部循环应该从最小的边界框向上迭代(宽度和高度依次以2的幂增加)。对于每个包围框，测试一下是否可以为矩形找到一个填充。你会得到一堆“不”的答案，直到第一个“是”的答案，这将保证是最优解。

对于算法的内部循环——对特定大小的边界框回答“是”或“否”的循环，我将查找Huang参考并实现他的算法。他在基本算法的基础上进行了大量优化，但你只需要最基本的部分。由于您希望处理旋转，因此在搜索过程中的每个分支点上，只要同时尝试两个旋转并在两个旋转都没有得到解决方案时回溯即可。

小开

有关解决方案的调查，请参阅关于ARC项目的本页，在实现复杂性/时间和最优性之间存在权衡，但有广泛的算法可供选择。

以下是算法的摘录:

  1. FFDH (First-Fit递减高度)算法
    FFDH将下一个项目R(在不增加高度的情况下)打包到R适合的第一层。如果没有级别可以容纳R，则创建一个新的级别 FFDH的时间复杂度:O(n·log n).
    近似比:FFDH(I)<=(17/10)·OPT(I)+1;17/10的渐近界很紧

  2. 下一次拟合递减高度(NFDH)算法
    如果R合适，NFDH将下一个项目R(不增加高度)打包到当前级别。否则，当前级别被“关闭”，并创建一个新的级别 时间复杂度:O(n·log n).
    近似比:NFDH(I) <= 2·OPT(I)+1;2的渐近界很紧

  3. BFDH算法
    BFDH在能容纳R的水平剩余空间最小的水平中，将下一项R(不增加高度)装在水平上。如果没有关卡可以容纳R，则创建一个新关卡。李< / p > < / >

  4. 左下(BL) Algorithm
    . BL一阶项不增加宽度。BL将下一件物品包装得尽可能靠近底部，然后尽可能靠近左侧，而不会与任何包装的物品重叠。注意BL不是一个面向级别的打包算法 时间复杂度:O(n²).
    近似比:BL(I) <= 3·OPT(I)。李< / p > < / >

  5. Baker's Up-Down (UD)算法
    UD采用BL和广义NFDH的组合。条带和项目的宽度经过标准化处理，使条带具有单位宽度。UD以宽度不变的方式对项目进行排序，然后将项目分为五组，每组的宽度范围为(1/2,1]，(1/3,1/2]，(1/4,1/3]，(1/5,1/4]，(0,1/5]。该条带还分为R1、···、R5五个区域。基本上，对于宽度范围为(1/i+ 1,1 /i]，对于1 <= i <= 4的项目，BL会将其打包到区域Ri中。由于BL在条带的右侧留出了从上到下宽度递增的空间，UD利用这一优势，首先将项目打包到Rj中，j = 1，····，4(顺序)。如果没有这样的空间，则使用BL将项目打包到Ri，最后使用(广义)NFDH算法将大小不超过1/5的项目打包到R1，····，R4的空间中。同样，如果这些区域中没有空间，则使用NFDH将项目打包到R5 .
    近似比:UD(I) <=(5/4)·OPT(I)+(53/8)H，其中H为项目的最大高度;5/4的渐近界很紧

  6. 反向拟合(RF)算法
    RF还将带材和项目的宽度归一化，使带材具有单位宽度。RF首先堆叠宽度大于1/2的所有项。其余物品按照不递增的高度进行排序，大于1/2的物品将在H0高度以上进行包装。然后RF重复以下过程。大致来说，RF将物品从左到右，底部沿高度H0的线进行包装，直到没有空间为止。然后从右到左，从上到下(称为反向)打包物品，直到总宽度至少为1/2。然后，反向层向下下降，直到(至少)其中一个接触到下面的某个项目。下拉框以某种方式重复。
    近似比例:射频(I) & lt; = 2·选择(I)。< / p > < /李> <李> < p > < br >斯坦伯格的算法 Steinberg的算法，在文中记为M，估计了一个高度H的上界来打包所有的项目，从而证明输入项目可以打包到一个宽W高H的矩形中。然后定义了七个过程(有七个条件)，每个过程将一个问题分成两个小问题，并递归地解决它们。已证明，任何可处理的问题都满足这七个条件中的一个 近似比例:M (I) & lt; = 2·选择(I)。< / p > < /李> 分割拟合算法(SF) SF将物品分为两组，L1宽度大于1/2,L2宽度不超过1/2。L1的所有物品都是由FFDH先包装的。然后对它们进行排列，使宽度大于2/3的项都在宽度不超过2/3的项之下。这就创建了一个宽度为1/3的矩形R。L2中剩余的物品用FFDH打包到R中，L1上面的空间用FFDH打包。R中创建的级别被认为低于L1包装上创建的级别 近似比:SF(I) <=(3/2)·OPT(I) + 2;3/2的渐近界很紧

    7. <李> < p > < br >看到的算法 Sleater算法由四个步骤组成:

    1. 宽度大于1/2的所有物品都在带材底部一个接一个地打包。假设h0是最终封装的高度，所有后续封装都将出现在h0以上。

    2. 其余项目按不增加高度排序。一级物品按照高度h0从左到右的顺序(不增加高度顺序)进行包装。

    3. 然后在中间画一条垂直线，将条切成相等的两半(注意，这条线可能会将部分包装在右侧的物品切割)。画两条长度为一半的水平线，一条横过左半部分(称为左基线)，另一条横过右半部分(称为右基线)，越低越好，这样两条线就不会交叉任何项目。

    4. 选择高度较低的左侧或右侧基线，并将一层项目打包到相应的半条中，直到下一个项目太宽。

    一个新的基线形成，在较低的基线上重复步骤(4)，直到所有项目都打包完毕 时间复杂度:O(n·log n).
    Sleator算法的逼近比为2.5，较紧凑，

小开
你需要的是 https://github.com/nothings/stb/blob/master/stb_rect_pack.h < / p >

示例:

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);
}

提交答案