Fir*_*cer 269 algorithm packing
我有一堆矩形物体,我需要将它们装入尽可能小的空间(这个空间的尺寸应该是2的幂).
我知道各种打包算法会将项目尽可能地打包到给定的空间中,但是在这种情况下我需要算法来计算出该空间应该有多大.
例如,说我有以下矩形
它们可以装入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,并且每个维度的给定最大大小)？
小智 85
有关解决方案的调查,请参阅ARC项目的此页面,在实现复杂性/时间和最优性之间进行权衡,但有多种算法可供选择.
这是算法的摘录:
First-Fit Decreasing Height(FFDH)算法
FFDH在R适合的第一级包装下一个项目R(非增加高度).如果没有级别可以容纳R,则会创建一个新级别.
FFDH的时间复杂度:O(n·log n).
逼近率:FFDH(I)<=(17/10)·OPT(I)+1; 17/10的渐近界是紧的.
Next-Fit Decreasing Height(NFDH)算法
如果R适合,NFDH将当前级别的下一个项目R(非增加高度)打包.否则,当前级别"关闭"并创建新级别.
时间复杂度:O(n·log n).
近似比:NFDH(I)<= 2·OPT(I)+1; 2的渐近界是紧的.
最佳拟合减小高度(BFDH)算法
BFDH在水平上包含下一个项目R(非增加高度),其中可以容纳R,其中剩余水平空间是最小的.如果没有级别可以容纳R,则会创建一个新级别.
左下(BL)算法
BL通过非增加宽度的第一顺序项.BL将下一个物品包装在靠近底部的位置,因为它适合,然后尽可能靠近左侧,不会与任何包装物品重叠.请注意,BL不是面向水平的打包算法.
时间复杂度:O(n ^ 2).
近似比:BL(I)<= 3·OPT(I).
Baker的Up-Down(UD)算法
UD使用BL和NFDH的推广的组合.条带的宽度和物品被标准化,使得条带具有单位宽度.UD以不增加的宽度对项目进行排序,然后将项目分为五组,每组的宽度在范围内(1/2,1,1),(1/3,1/2),(1/4,1/3) ],(1/5,1/4),(0,1/5).条带也分为五个区域R1,...,R5.基本上,一些宽度在范围内的项目(1/i +对于1 <= i <= 4,1,1/i]由BL填充到区域Ri.由于BL在条带的右侧从顶部到底部留下增加宽度的空间,UD首先利用这个优势将物品从上到下包装到Rj,j = 1,...,4(按顺序).如果没有这样的空间,则物品由BL打包到Ri.最后,物品的大小最多为1/5通过(广义)NFDH算法打包到R1,...,R4中的空格.
近似比:UD(I)<=(5/4)·OPT(I)+(53/8)H,其中H是项目的最大高度; 5/4的渐近界是紧的.
反向拟合(RF)算法
RF还使条带和物品的宽度标准化,使得条带具有单位宽度.RF首先堆叠宽度大于1/2的所有项目.剩余物品按非增加高度分类,并将被填充到大于1/2的高度H0.然后RF重复以下过程.粗略地说,RF从左到右包装物品,其底部沿着高度线H0,直到没有空间.然后从右到左和从上到下包装物品(称为反向水平),直到总宽度至少为1/2.然后降低反向级别,直到(至少)其中一个触及下面的某个项目.下拉有点重复.
近似比:RF(I)<= 2·OPT(I).
Steinberg的算法
Steinberg的算法,在论文中用M表示,估计包装所有项目所需的高度H的上限,以便证明输入项目可以打包成宽度为W和高度为H的矩形.然后定义七个程序(有七个条件),每个程序将一个问题分成两个较小的程序并递归地解决它们.已经表明,任何易处理的问题都满足七个条件之一.
近似比: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的打包之上创建的级别.
近似比:SF(I)<=(3/2)·OPT(I)+ 2; 3/2的渐近界是紧的.
Sleator的算法
Sleater的算法包括四个步骤:
所有宽度大于1/2的物品都在条带底部彼此叠加.假设h0是所得填料的高度所有后续填料将在h0以上发生.
剩余物品按非增加高度排序.物品等级沿着高度线h0从左到右被打包(以非增加的高度顺序).
然后在中间绘制一条垂直线,将条带切成两半相等(注意,这条线可能会切割出部分装在右半部分的物品).绘制两个长度为一半的水平线段,一个横跨左半部分(称为左基线),另一个横跨右半部分(称为右基线)尽可能低,使得两条线不穿过任何项目.
选择较低高度的左侧或右侧基线,并将一个级别的项目装入相应的条带的一半,直到下一个项目太宽.
形成新基线,并且在下基线上重复步骤(4),直到所有物品都被包装.
时间复杂度:O(n·log n).
Sleator算法的近似比为2.5,这是紧的.
SPW*_*ley 65
快速而肮脏的首次通过解决方案始终是一个很好的开始,作为比较,如果没有别的.
从大到小的贪婪安置.
将最大的矩形放入您的打包区域.如果它无法放在任何地方,请将其放置在尽可能少地延伸包装区域的位置.重复,直到完成最小的矩形.
它根本不是完美的,但它很容易且基线很好.它仍然可以完美地包装您的原始示例,并为您提供相应的答案.
Eri*_*ric 17
关于这个问题的文献很多.一个好的贪心启发式是在第一个可用位置朝向容器的底部和左侧放置从最大区域到最小区域的矩形.想象重力将所有物品拉到左下角.有关此谷歌"Chazelle左下方包装"的描述.
为了获得最佳解决方案,最先进的技术可以在几秒钟内打包超过20个矩形.Huang有一个算法,它将找到最小的封闭边界框的问题与决定一组矩形是否适合特定尺寸的边界框的问题分开.你给他的程序一组矩形,它告诉你打包它们所需的最小的封闭边界框.
对于您的情况,您的外循环应该从最小可能的边界框向上迭代(宽度和高度连续增加2的幂).对于每个边界框,测试是否可以找到矩形的包装.你会得到一堆"不"的答案,直到第一个"是"答案,这将保证是最佳解决方案.
对于算法的内部循环 - 对特定大小的边界框回答"是"或"否"的循环,我会查找黄色参考并实现他的算法.他在基本算法之上包含了很多优化,但你只需要基本的肉和土豆.由于您希望在搜索过程中的每个分支点处理旋转,因此当两个旋转都不会产生解决方案时,只需尝试旋转和回溯.
我很确定这是一个NP难问题,因此,对于最佳解决方案,您必须实现一个尝试每种可能组合的回溯算法.
好消息是,由于需要在有限的2D空间中打包2D矩形,您可以在早期修剪很多可能性,因此可能不是那么糟糕.
你需要的是 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);
}