logo标签列表

使用盒子旋转的最佳适合度装箱 Js 实现

javascripthtmlalgorithmsortingbin-packing
3
我在这里使用了bin packing js实现，链接在https://github.com/jakesgordon/bin-packing 当我将框架大小指定为800x600时，
并且块大小为150x700，150x700，则会提示无法容纳。 然而，有足够的空间。 当制作700x150，700x150时亦是如此。
如何调整代码以使其可以动态旋转块大小并适应框架。
此处使用的js packer为，
    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;
  }

}
2个回答
4

我添加了第二个答案，因为这与第一个答案有很大不同，试图解决问题中提出的2D装箱算法的更核心问题。使用特定算法时，splitNode例程生成可用于放置块的down和right节点，但并未考虑相邻节点的联合可能容纳更大的块...

例如，在下面的建议算法中，给定一个800x600的初始堆，放置一个500x300的块将导致堆包含两个(0,300)-(800,600)和(500,0)-(800,600)的堆块。这两个堆块将在(500,300)-(800,600)的区域重叠，以确保在寻找适合块的位置时表示最大堆块区域。而在2D装箱算法中，down或right中没有交叉区域，而是倾向于潜在重叠空间到一个节点或另一个节点...

以下算法尝试通过实现一组可用的堆块数组来解决这个问题，表示最大可用的块，即使这些堆块彼此重叠。缺点是这引入了一个O(n^2)的算法(unionAll)来管理堆，加上O(n)的循环(fit)通过块以适合。因此，这个算法可能接近于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}]

请注意，此算法未做优化。即，它没有对输入的块进行排序（例如按宽度、高度或面积等），也没有在执行 unionAll 后对堆进行排序，这会将堆缩减为最大大小的堆块列表。（即，在每次调用 unionAll 后，都有机会按宽度、高度或面积等对堆进行排序，以便在搜索下一个可用的块放置时，如果堆按从大到小排序，则算法将在最大可用堆块中放置块；如果按照从小到大排序，则块将被放置在刚好足够大的堆块中...）无论如何，我们将把这些类型的优化留给读者自己练习。

另外，请以一定的怀疑态度查看此算法，并适当测试。

真的，你是一个伟大的人。不幸的是，我无法适应这个，因为块（属性）的格式都不同。我的项目非常庞大，我无法将这个答案输出调整为与第一个答案相同。如果您能做到这一点，我很高兴。请别介意。如果您忙碌没有时间，或者我的请求没有任何意义，请忽略我的请求！ - Code Guy
你是在特别指块数组和“fit”属性吗？例如，fit: {x: 2100, y: 600, w: 300, h: 600, used: true}，因为你应该能够通过循环遍历新提出的算法的结果来构建这个属性。但如果你指的是“down”和“right”属性，这将引入一些将新提出的算法的结果逆向工程到旧格式中的代码，这会增加不必要的复杂性。也就是说，更好的做法是花费时间来改变调用程序以处理新提出的算法的结果。 - Trentium
@Trentium 我正在尝试做完全相同的事情，但我使用的是带有<sub>中<g>的svg图标。似乎旋转在<svg>上起作用，但所有子<g>组都没有旋转。图标仍然显示原始状态，但由于新的svg坐标而部分隐藏。我不确定你们是否有任何建议给我。 - mtkilic
@mtkilic 听起来更像是SVG图标旋转问题，而不是算法问题，与将矩形适配到可用空间类似，类似于装箱。也许值得开一个新的问题，详细说明你遇到的具体问题。 - Trentium
@Trentium 是的，它与SVG图标旋转有关。你的逻辑完美地运作着。我可以告诉一切都适合盒子给定的宽度和高度。我只需要弄清楚如何正确旋转SVG图标。我会尝试几天，如果无法解决，我将开启一个新的问题。谢谢。 - mtkilic
显示剩余3条评论
2
我认为下面的代码可能会有用……？（即，我进行了有限的测试，但对于我测试过的内容，它似乎可以工作。）
我基本上在 findnode 程序中添加了另一个选项来旋转块（即，交换宽度和高度尺寸）作为选项，如果它不能适应其预定义的方向。这涉及将另一个属性添加到 block 中，称为 rotate，表示尺寸已经交换。 （当然，引入交换和 rotate 属性需要将 block 传递给 findnode，而不是像以前的代码中那样传递 w 和 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];
      block.rotate = false;
      if (node = this.findNode(this.root, block))
        block.fit = this.splitNode(node, block);
    }  
  },

  findNode: function(root, block) {
    if (root.used) {
      return this.findNode(root.right, block) || this.findNode(root.down, block);
    } else if ((block.w <= root.w) && (block.h <= root.h)) {
      return root;
    } else if ((block.h <= root.w) && (block.w <= root.h)) {
        let temp = block.w;
        block.w = block.h;
        block.h = temp;
        block.rotate = !block.rotate;
        return root;
    } else
      return null;
  },

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

希望这对你有帮助。最初的回答是：

希望这可以为您解决问题。

非常感谢，但我已经测试过了，当框架大小为800x600时似乎可以工作。如果我将框架尺寸反转为600x800，则无法工作并会显示“不适合”。对于2400x1200，我已经测试了2100 x 600、2100 x 600、150 x 200、200 x 740的块，但它们都无法工作。如果我将面板尺寸更改为1200x2400，则完美运行。有什么建议吗？ - Code Guy
我运行了800x600和600x800的四种组合，分别与700x150和150x700进行匹配，它们都得到了适配结果。可能导致问题的原因是，在重新运行另一个适配之前，如果您使用相同的Packer变量，则需要重新初始化它。即，在执行myPackerVar.fit（...）之前，需要执行myPackerVar.init（800,600）。问题在于，如果您连续执行两个myPackerVar.fit运行，则this.root变量具有来自上一次运行的残留信息。 - Trentium
我认为我看到了问题所在。在你的第二个例子中，2400x1200，算法用两个2100 x 600的块填充空间，留下两个300 x 600的区域。虽然是连续的，但算法中没有任何东西来将它们组合成一个600x1200的块，因此200x740的块无处可去。这是一个不同于旋转块的问题(!)。 - Trentium
那么你的意思是说，这个问题无法解决？如果需要修复该问题，我需要在哪里引入代码？ - Code Guy
解决发布的算法问题将涉及（在我看来）遍历每次执行“findNode”时节点树以确定相邻块，这引入了另一层复杂性。这是一个有趣的问题，与垃圾收集有些相关，所以我自己尝试解决了它，并且由于它与原始响应围绕通过旋转简单地适配块的方法有很大不同，因此在另一个答案中包含了我的提议算法。 - Trentium
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接