如何使用 javascript 增长垃圾箱打包算法获得最终垃圾箱大小
How can I get final bin size with javascript growing bin packing algorithm?
使用这种 2d 垃圾箱打包算法(编辑:固定演示)这是它的变体,我如何获得每个垃圾箱的最终垃圾箱宽度和高度?
我的演示代码如下:
var blocks = [
{w: 1000, h: 800},
{w: 500, h: 700},
{w: 500, h: 700},
{w: 500, h: 350},
{w: 500, h: 350},
{w: 500, h: 350},
{w: 500, h: 350},
{w: 500, h: 350},
{w: 500, h: 350},
{w: 500, h: 350},
{w: 500, h: 350},
{w: 250, h: 350},
{w: 250, h: 350},
{w: 250, h: 350},
{w: 250, h: 350},
{w: 250, h: 350},
{w: 250, h: 350},
{w: 250, h: 350},
{w: 250, h: 350},
{w: 250, h: 350},
{w: 250, h: 350},
{w: 250, h: 350},
{w: 250, h: 350},
{w: 250, h: 350}
];
var sheets = [];
while(blocks.length) {
var packer = new GrowingPacker(1000,800);
packer.fit(blocks);
sheet = [];
for (var i=blocks.length-1; i>=0; i--) {
if (blocks[i].fit !== undefined && blocks[i].fit !== null) {
//console.log(blocks[i].fit);
sheet.unshift(blocks[i]);
blocks.splice(i,1);
}
}
//console.log(sheet[sheet.length-1].fit.y + sheet[sheet.length-1].h);
//console.log(sheet);
sheets.push(sheet);
}
for(var i=0; i<sheets.length; i++) {
var sheet = sheets[i];
var sheetWidth = sheet[sheet.length-1].w + sheet[sheet.length-1].fit.x;
var sheetHeight = sheet[sheet.length-1].h + sheet[sheet.length-1].fit.y;
for(var j=0; j<sheet.length; j++) {
console.log("SHEET #" + i + " - W: " + sheetWidth + " H: " + sheetHeight + " BLOCK #" + j + " - W: " + sheet[j].w + " H: " + sheet[j].h + " X: " + sheet[j].fit.x + " Y: " + sheet[j].fit.y);
}
}
原始算法只处理一个不断扩展的箱,所以我修改了它以采用最大宽度和高度。然后我运行块数组,调用打包器,将适合块推送到新数组,并取消设置它们从"块"直到"块"为空。这是否是最好的办法是另一个问题的主题。
无论如何,我尝试像这样修改growNode:
growNode: function(w, h) {
var canGrowRight = (w <= this.root.w && this.root.w + w <= maxW);
var canGrowDown = (h <= this.root.h && this.root.h + h <= maxH);
if (canGrowRight) {
this.sheetW = this.root.w + w; //<--------------added
return this.growRight(w, h);
}
else if (canGrowDown) {
this.sheetH = this.root.h + h; //<--------------added
return this.growDown(w, h);
}
else
return null; // need to ensure sensible root starting size to avoid this happening
},
它适用于除第一张纸以外的每张纸。我也尝试在其他一些方法中添加这些行,但没有成功。我还尝试从工作表宽度 + x 的最后一个块中获取工作表大小,但这仅在工作表已满时才有效。
我的问题再次是我如何获得每张纸的最终纸张尺寸?
您可以使用增长算法,您可以将箱向左或向右增长:http://codeincomplete.com/posts/2011/5/7/bin_packing。
我最终想通了。我添加了两行来查找节点()
findNode: function(root, w, h) {
if (root.used) {
return this.findNode(root.right, w, h) || this.findNode(root.down, w, h);
}
else if ((w <= root.w && w <= this.maxW) && (h <= root.h && w <= this.maxW)) {
this.binWidth = this.root.w <= this.maxW ? this.root.w : this.maxW;
this.binHeight = this.root.h <= this.maxH ? this.root.h : this.maxH;
return root;
}
else {
return null;
}
},
如果你想玩它,这里是jsfiddle。我建议对输入尝试这样的事情:
100x80
50x70
50x35x2
25x35x4
相关文章:
- 循环比赛位置算法
- javascript扫雷器floodfill算法不能正常工作
- Node JS中的排名系统算法
- 查找仅适用于原始图像的图像放大算法的名称
- 在数组的 2/3 上调用自身的排序算法
- Luhn算法的实现
- 算法:从数组(javascript/angular)中按当前日期获取上一个和下一个事件
- 加速单纯形算法
- 最短路径算法js错误
- 代码战争中的算法混乱
- 用于自动放置流程图形状的算法
- PHP或JavaScript的基本遗传算法开源代码
- 用Javascript实现算法
- 堆中for循环的奇怪行为's算法
- 一种从随机数的序列中查找值的简单算法
- Node.js上的高性能算法
- JavaScript排序算法不起作用 - 任何明显的我做错了
- 需要使用JavaScript实现我的算法
- 用于计算产品价格的JavaScript构建和算法
- 如何使用 javascript 增长垃圾箱打包算法获得最终垃圾箱大小