1. 首页
  2. 问答
  3. 什么算法可用于以相当优化的方式将不同大小的矩形打包成最小的矩形？

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

2009-07-31 51 views
223

我得到了一堆矩形物体，我需要将它们放入最小的空间（这个空间的尺寸应该是2的幂）。什么算法可用于以相当优化的方式将不同大小的矩形打包成最小的矩形？

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

如说Ive得到了如下矩形

  • 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的幂，并且对于每个维度在给定的最大尺寸内）？

来源

2009-07-31 Fire Lancer

+87

我投票这个问题了，不仅因为它是有趣的，但他们肯定矩形相当。 – jr3 2009-07-31 16:14:11

+1

+1这就是我要求将字体字形装入纹理的问题，但是比我所做的任何更好的提议 – 2010-03-31 00:18:11

+2

第二种解决方案不是最优的吗？难道它不是128乘224？ – 2010-08-20 22:46:49

回答

55

快速和肮脏的第一遍解决方案始终是一个伟大的开始，作为比较，如果没有别的。

贪婪的从大到小的摆放位置。

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

这并不完美，但它很容易和一个很好的基线。它仍然会完美地包装您的原始示例，并为第二个示例给出相应的答案。

来源

2009-07-31 16:33:45 SPWorley

5

我相当肯定这是an NP-hard problem，所以，对于一个最佳的解决方案，你必须实现一个回溯算法，试用所有可能的组合。

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

来源

2009-07-31 16:04:53 Blindy

0

一般的解决方案是不平凡的（数学为完全****荷兰国际集团不可能说吧）
一般人使用遗传算法来尝试可能的组合，但你可以做得很好把最大的形状放在第一位，然后尝试不同的地方进行下一个最大的形状，等等。

来源

2009-07-31 16:18:18

16

关于这个问题有大量的文献。良好的贪婪法则是将矩形从最大面积放置到容器底部和左侧的第一个可用位置。想想重力将所有物品拉到左下角。有关此谷歌“Chazelle左下包装”的描述。

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

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

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

来源

2010-06-22 02:00:27 Eric

69

有关解决方案的调查，请参阅this page on the ARC project，实现复杂性/时间和最优性之间存在权衡，但有多种算法可供选择。

下面的算法的提取物：

  1. 最先适合降低的高度（FFDH）算法
    FFDH上式中，R拟合第一级包的下一个项目R（非高度增加）。如果没有级别可以容纳R，则会创建一个新级别。
    FFDH的时间复杂度：O（n·log n）。 （I）< =（17/10）·OPT（I）+1;其中， 17/10的渐近界很紧。

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

  3. 最优适应降低的高度（BFDH）算法
    BFDH上水平包的下一个项目R（非高度增加），这些可容纳R，的量，残留的水平空间为最小之间。如果没有级别可以容纳R，则会创建一个新级别。

  4. 左下（BL）算法
    BL一阶项目的宽度不增加。 BL将下一个物品放在靠近底部的位置，因为它可以放入，然后尽可能靠近左侧，因为它可以与任何包装物品不重叠。请注意，BL不是一种面向级别的打包算法。
    时间复杂度：O（n^2）。 （I）
    近似比例：BL（I）< = 3·OPT（I）。（UD）算法
    UD使用BL和NFDH泛化的组合。条的宽度和项目被标准化，以便条的宽度为单位。 UD以非增加的宽度对项目进行排序，然后将项目分成五组，每组的宽度在范围（1/2,1），（1/3,1/2]，（1/4,1/3） ]，（1/5,1/4]，（0,1/5）。条带也分为5个区域R1，...，R5。基本上，一些宽度在（1/i +由于BL在条带的右侧从顶部到底部留下宽度增加的空间，因此UD首先利用该优势，即首先利用该优势如果没有这样的空间，那么物品被BL打包到Ri，最后物品的尺寸至多为1/5通过（广义）NFDH算法打包到R1，...，R4中的空间，再次如果这些区域中没有空间，则使用NFDH将项目打包到R5。 =（5/4）·OPT（I）+（53/8）H，其中H是物品的最大高度; 5/4的渐近界是紧的。

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

  6. Steinberg的算法
    Steinberg的算法，在纸表示为M，估计的上部结合到包装中的所有项目，使得它证明了输入项目可装入宽度的矩形所需要的高度H的W和高度H.然后他们定义了七个程序（有七个条件），每个程序将一个问题分成两个较小的问题并递归解决问题。已经表明任何易处理的问题都满足七个条件之一。 （I）
    近似比：M（I）< = 2·OPT（I）。 （SF） SF将项目分为两组，L1宽度大于1/2且L2最多为1/2。所有的L1项目都由FFDH首先打包。然后将它们排列成使得宽度大于2/3的所有项目在宽度最多为2/3的项目之下。这将创建宽度为1/3的矩形R空间。然后将L2中的剩余项目打包到R，并使用FFDH打包L1以上的空间。在R中创建的级别被认为低于在L1的包装之上创建的级别。 （I）< =（3/2）·OPT（I）+ 2; 3/2的渐近界是紧的。

  7. Sleator算法
    Sleater的算法包括以下四个步骤：

    1. 宽度大于1/2的所有的数据项被打包在彼此的顶部上在带的底部。假设h0是结果包装的高度所有后续包装将发生在h0以上。

    2. 剩余项目按非增加高度排序。沿着高度h0的线从左到右打包物品的级别（以不增加的高度顺序）。

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

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

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

来源

2010-11-24 07:47:32

1

你需要的是在 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); 
}

来源

2016-09-22 17:24:53 Orbitus007

相关问题

 相关问题