javascript - Bin Packing Js 实现使用盒子旋转以获得最佳匹配

Question

我这里用到了装箱js实现https://github.com/jakesgordon/bin-packing

当我将帧大小指定为 800x600 时

Blocks size as 150x700,150x700 它会说，它不能容纳 但是，有足够的空间。 700x150的时候也一样，做成700x150的就可以了。

我如何调整代码，以便它可以动态旋转 block 大小并适合框架。

这里使用的js打包器是，

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

}

Answer 1

我正在添加第二个答案，因为这与第一个答案完全不同，并试图通过问题中提出的 2D Bin Packing 算法解决更核心的问题。使用该特定算法，splitNode 例程生成可用于拟合 block 的 down 和 right 节点，但没有考虑到作为可用节点积累，相邻节点的联合可以容纳更大的 block ......

例如，在下面提出的算法中，给定一个 800x600 的初始堆，放置一个 500x300 的 block 将导致该堆包含 (0,300)-(800,600) 和 (500,0)-(800,600) 两个堆 block 。这两个 heapBlock 将在 (500,300)-(800,600) 的区域重叠，以确保在搜索适合 block 的位置时表示最大的 heapBlock 区域。而在 2D Bin Packing 算法中，down 或 right 没有相交区域，而是倾向于一个或另一个节点的潜在重叠空间...

下面的算法试图通过实现代表最大可用 block 的可用堆 block 数组来弥补这个缺点，即使这些堆 block 彼此重叠。缺点是这引入了一个 O(n^2) 算法 (unionAll) 来管理堆，在 O(n) 循环 (fit) 之上通过 block 来适应。因此，该算法的性能可能接近 O(n^3)，尽管这可能是更糟糕的情况……

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

Packer.prototype = {

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

  intersect: function(block0, block1) {
    //
    // Returns the intersecting block of
    // block0 and block1.
    //
    let ix0 = Math.max(block0.x0, block1.x0);
    let ix1 = Math.min(block0.x1, block1.x1);
    let iy0 = Math.max(block0.y0, block1.y0);
    let iy1 = Math.min(block0.y1, block1.y1);

    if (ix0 <= ix1 && iy0 <= iy1) {
      return {x0: ix0, y0: iy0, x1: ix1, y1: iy1};
    } else {
      return null;
    }
  },

  chunkContains:  function(heapBlock0, heapBlock1) {
    //
    // Determine whether heapBlock0 totally encompasses (ie, contains) heapBlock1.
    //
    return heapBlock0.x0 <= heapBlock1.x0 && heapBlock0.y0 <= heapBlock1.y0 && heapBlock1.x1 <= heapBlock0.x1 && heapBlock1.y1 <= heapBlock0.y1;
  },

  expand: function(heapBlock0, heapBlock1) {
    //
    // Extend heapBlock0 and heapBlock1 if they are
    // adjoining or overlapping.
    //
    if (heapBlock0.x0 <= heapBlock1.x0 && heapBlock1.x1 <= heapBlock0.x1 && heapBlock1.y0 <= heapBlock0.y1) {
      heapBlock1.y0 = Math.min(heapBlock0.y0, heapBlock1.y0);
      heapBlock1.y1 = Math.max(heapBlock0.y1, heapBlock1.y1);
    }

    if (heapBlock0.y0 <= heapBlock1.y0 && heapBlock1.y1 <= heapBlock0.y1 && heapBlock1.x0 <= heapBlock0.x1) {
      heapBlock1.x0 = Math.min(heapBlock0.x0, heapBlock1.x0);
      heapBlock1.x1 = Math.max(heapBlock0.x1, heapBlock1.x1);
    }
  },

  unionMax: function(heapBlock0, heapBlock1) {
    //
    // Given two heap blocks, determine whether...
    //
    if (heapBlock0 && heapBlock1) {
      // ...heapBlock0 and heapBlock1 intersect, and if so...
      let i = this.intersect(heapBlock0, heapBlock1);
      if (i) {
        if (this.chunkContains(heapBlock0, heapBlock1)) {
          // ...if heapBlock1 is contained by heapBlock0...
          heapBlock1 = null;
        } else if (this.chunkContains(heapBlock1, heapBlock0)) {
          // ...or if heapBlock0 is contained by heapBlock1...
          heapBlock0 = null;
        } else {
          // ...otherwise, let's expand both heapBlock0 and
          // heapBlock1 to encompass as much of the intersected
          // space as possible.  In this instance, both heapBlock0
          // and heapBlock1 will overlap.
          this.expand(heapBlock0, heapBlock1);
          this.expand(heapBlock1, heapBlock0);
        }
      }
    }
  },

  unionAll: function() {
    //
    // Loop through the entire heap, looking to eliminate duplicative
    // heapBlocks, and to extend adjoining or intersecting heapBlocks,
    // despite this introducing overlapping heapBlocks.
    //
    for (let i = 0; i < this.heap.length; i++) {
      for (let j = 0; j < this.heap.length; j++) {
        if (i !== j) {
          this.unionMax(this.heap[i],this.heap[j]);
          if (this.heap[i] && this.heap[j]) {
            if (this.chunkContains(this.heap[j], this.heap[i])) {
              this.heap[i] = null;
            } else if (this.chunkContains(this.heap[i], this.heap[j])) {
              this.heap[j] = null;
            }
          }
        }
      }
    }
    // Eliminate the duplicative (ie, nulled) heapBlocks.
    let onlyBlocks = [];
    for (let i = 0; i < this.heap.length; i++) {
      if (this.heap[i]) {
        onlyBlocks.push(this.heap[i]);
      }
    }
    this.heap = onlyBlocks;
  },

  fit: function(blocks) {
    //
    // Loop through all the blocks, looking for a heapBlock
    // that it can fit into.
    //
    this.heap = [{x0:0,y0:0,x1:this._root.w, y1: this._root.h}];
    var n, node, block;
    for (n = 0; n < blocks.length; n++) {
      block = blocks[n];
      block.rotate = false;
      if (this.findInHeap(block)) {  
        this.adjustHeap(block);
      } else {
        // If the block didn't fit in its current orientation,
        // rotate its dimensions and look again.
        block.w = block.h + (block.h = block.w, 0);
        block.rotate = true;
        if (this.findInHeap(block)) {
          this.adjustHeap(block);
        }
      }
    }  
  },

  findInHeap: function(block) {
    //
    // Find a heapBlock that can contain the block.
    //
    for (let i = 0; i < this.heap.length; i++) {
      let heapBlock = this.heap[i];
      if (heapBlock && block.w <= heapBlock.x1 - heapBlock.x0 && block.h <= heapBlock.y1 - heapBlock.y0) {
        block.x0 = heapBlock.x0;
        block.y0 = heapBlock.y0;
        block.x1 = heapBlock.x0 + block.w;
        block.y1 = heapBlock.y0 + block.h;
        return true;
      }
    }
    return false;
  },

  adjustHeap:  function(block) {
    //
    // Find all heap entries that intersect with block,
    // and adjust the heap by breaking up the heapBlock
    // into the possible 4 blocks that remain after
    // removing the intersecting portion.
    //
    let n = this.heap.length;
    for (let i = 0; i < n; i++) {
      let heapBlock = this.heap[i];
      let overlap = this.intersect(heapBlock, block);
      if (overlap) {

        // Top
        if (overlap.y1 !== heapBlock.y1) {
          this.heap.push({
            x0: heapBlock.x0,
            y0: overlap.y1,
            x1: heapBlock.x1,
            y1: heapBlock.y1
          });
        }

        // Right
        if (overlap.x1 !== heapBlock.x1) {
          this.heap.push({
            x0: overlap.x1,
            y0: heapBlock.y0,
            x1: heapBlock.x1,
            y1: heapBlock.y1
          });
        }

        // Bottom
        if (heapBlock.y0 !== overlap.y0) {
          this.heap.push({
            x0: heapBlock.x0,
            y0: heapBlock.y0,
            x1: heapBlock.x1,
            y1: overlap.y0
          });
        }

        // Left
        if (heapBlock.x0 != overlap.x0) {
          this.heap.push({
            x0: heapBlock.x0,
            y0: heapBlock.y0,
            x1: overlap.x0,
            y1: heapBlock.y1
          });
        }       

        this.heap[i] = null;
      }
    }

    this.unionAll();
  }

}

fit 算法会将结果留在heap 和传入的blocks 数组中。例如……

p = new Packer(2400,1200);
blocks = [{w:2100,h:600},{w:2100,h:600},{w:150,h:200},{w:740,h:200},{w:500,h:100}];
p.fit(blocks);

...将留下 p.heap 和 blocks 如下...

The final HEAP
[{"x0":2100,"y0":940,"x1":2400,"y1":1200},
{"x0":2300,"y0":500,"x1":2400,"y1":1200},
{"x0":2250,"y0":0,"x1":2300,"y1":200}]

The final BLOCKS
[{"w":2100,"h":600,"rotate":false,"x0":0,"y0":0,"x1":2100,"y1":600},
{"w":2100,"h":600,"rotate":false,"x0":0,"y0":600,"x1":2100,"y1":1200},
{"w":150,"h":200,"rotate":false,"x0":2100,"y0":0,"x1":2250,"y1":200},
{"w":200,"h":740,"rotate":true,"x0":2100,"y0":200,"x1":2300,"y1":940},
{"w":100,"h":500,"rotate":true,"x0":2300,"y0":0,"x1":2400,"y1":500}]

请注意，此算法未优化。即，它不会对传入的 block 进行排序(即，按宽度、高度或面积等)，也不会在执行 unionAll 后对堆进行排序，这会将堆减少到最大大小的列表堆 block 。 (即，在每次调用 unionAll 后，都有机会按宽度、高度或面积等对堆进行排序，以便在堆中搜索下一个要放置的可用 block 时，如果堆是从大到小排序，算法会将 block 放置在最大的可用堆 block 中，或者如果从小到大排序， block 将放置在刚好足够大的堆 block 中...)无论如何，将保留这些类型的优化作为练习。

另外，请以怀疑的态度看待这个算法，并进行适当的测试。