一种方法来实现矩形装箱 [英] An approach to implement rectangular bin packing

问题描述

我想用最大矩形的算法如下面的文件来实现2D装箱。

I'm trying to implement 2D bin packing using the Maximal rectangles algorithms as in the following paper.

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

为了实现这一点，是什么类型的数据结构将是最合适的？ 谷歌搜索后，我发现有使用树不同的实施断头台包装算法。可以同样的方法被应用到这一点。 该算法本身没有太多明确的给我。我可以有更多的澄清这一点。

In order to implement this, what type of a data structure will be most appropriate? After googling I found there are different implementation of Guillotine packing algorithm using trees. Can the same approach be applied to this as well. The algorithm itself is not much clear to me. Can I have more clarification on this as well.

推荐答案

我自动CSS精灵世代研究时，无意中发现了一些东西。我想在这里再presented由元组的矩形，实际算法与二叉树工作的来源中。也许这是对你有用。

I stumbled on something when researching for automatic CSS sprite generation. I think in the source the rectangles where represented by tuples, the actual algorithm worked with a binary tree. Maybe it is useful to you.

HTTP：//$c$cincomplete.com/posts/2011 / 5/7 / bin_packing /

修改 这里距离 HTTPS的code样品：// github上。 COM / jakesgordon /装箱/ BLOB /主/ 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;
  }

}

这篇关于一种方法来实现矩形装箱的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！