2

このバリエーションであるこの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の最後のブロックからシートサイズを取得しようとしましたが、これはシートがいっぱいの場合にのみ機能します。

もう一度質問しますが、各シートの最終的なシートサイズを取得するにはどうすればよいですか?

4

2 に答える 2

0

拡大アルゴリズムを使用して、ビンを左または右に拡大できます:http: //codeincomplete.com/posts/2011/5/7/bin_packing

于 2012-08-09T22:01:27.653 に答える
0

私は最終的にそれを理解しました。findNode()に2行追加しました

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
于 2012-08-10T14:19:33.160 に答える