직사각형 bin 패킹 구현 방법

Question

다음 용지와 같이 Maximal rectangles 알고리즘을 사용하여 2D bin 패킹을 구현하려고합니다. 이를 구현하기 위해

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

는 데이터 구조의 유형이 가장 적합한 것인가? 인터넷 검색을 수행 한 결과, 나무를 사용하여 길로틴 패킹 알고리즘을 구현 한 것으로 나타났습니다. 같은 접근법이 이것에도 적용될 수 있는가? 알고리즘 자체는별로 명확하지 않습니다. 이것에 대해서도 더 많은 설명을 할 수 있을까요?

Answer 1

자동 CSS 스프라이트 생성을 연구 할 때 무언가를 발견했습니다. 소스에서 튜플로 표현 된 사각형을 생각하면 실제 알고리즘은 이진 트리로 작업했습니다. 어쩌면 그것은 당신에게 유용 할 것입니다.

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

}