javascript - 如何使用 javascript growing bin packing algorithm 获得最终的 bin 大小？

Question

使用这个 2d bin-packing algorithm (编辑:固定演示)这是 this 的变体如何获取每个 bin 的最终 bin 宽度和高度？

我的演示代码如下:

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

原始算法只处理一个单一的、不断扩展的容器，所以我修改它以采用最大宽度和高度。然后我遍历 block 数组，调用打包器，将适合的 block 推送到一个新数组并将它们从“ block ”中取消设置，直到“ block ”为空。这是否是最佳方法是另一个问题的主题。

无论如何，我试过像这样修改 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 中的最后一个 block 获取工作表大小，但这仅在工作表已满时才有效。

我的问题又是如何获得每张纸的最终纸尺寸？

Answer 1

您可以使用增长算法，并且可以向左或向右增长 bin:http://codeincomplete.com/posts/2011/5/7/bin_packing .