一種實現矩形bin包裝的方法

Question

我正在嘗試使用最大矩形算法來實現2D bin包裝，如下面的文章中所述。

http://clb.demon.fi/files/RectangleBinPack.pdf

爲了實現這一點，什麼類型的數據結構將是最合適的？ 谷歌搜索後，我發現使用樹木的斷頭臺填充算法有不同的實現。同樣的方法也可以應用於此。算法本身對我來說不是很清楚。我是否也可以對此進行更多的說明。

Answer 1

我在研究自動CSS sprite生成時偶然發現了一些東西。我認爲在源代碼中由元組表示的矩形，實際的算法使用二叉樹。也許它對你有用。

http://codeincomplete.com/posts/2011/5/7/bin_packing/

編輯 這裏是https://github.com/jakesgordon/bin-packing/blob/master/js/packer.js

/****************************************************************************** 

This is a very simple binary tree based bin packing algorithm that is initialized 
with a fixed width and height and will fit each block into the first node where 
it fits and then split that node into 2 parts (down and right) to track the 
remaining whitespace. 

Best results occur when the input blocks are sorted by height, or even better 
when sorted by max(width,height). 

Inputs: 
------ 

    w:  width of target rectangle 
    h:  height of target rectangle 
    blocks: array of any objects that have .w and .h attributes 

Outputs: 
------- 

    marks each block that fits with a .fit attribute pointing to a 
    node with .x and .y coordinates 

Example: 
------- 

    var blocks = [ 
    { w: 100, h: 100 }, 
    { w: 100, h: 100 }, 
    { w: 80, h: 80 }, 
    { w: 80, h: 80 }, 
    etc 
    etc 
    ]; 

    var packer = new Packer(500, 500); 
    packer.fit(blocks); 

    for(var n = 0 ; n < blocks.length ; n++) { 
    var block = blocks[n]; 
    if (block.fit) { 
     Draw(block.fit.x, block.fit.y, block.w, block.h); 
    } 
    } 


******************************************************************************/ 

Packer = function(w, h) { 
    this.init(w, h); 
}; 

Packer.prototype = { 

    init: function(w, h) { 
    this.root = { x: 0, y: 0, w: w, h: h }; 
    }, 

    fit: function(blocks) { 
    var n, node, block; 
    for (n = 0; n < blocks.length; n++) { 
     block = blocks[n]; 
     if (node = this.findNode(this.root, block.w, block.h)) 
     block.fit = this.splitNode(node, block.w, block.h); 
    } 
    }, 

    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) && (h <= root.h)) 
     return root; 
    else 
     return null; 
    }, 

    splitNode: function(node, w, h) { 
    node.used = true; 
    node.down = { x: node.x,  y: node.y + h, w: node.w,  h: node.h - h }; 
    node.right = { x: node.x + w, y: node.y,  w: node.w - w, h: h   }; 
    return node; 
    } 

}