Bin Packing Js 实现使用盒子旋转以获得最佳匹配
Bin Packing Js implementation using box rotation for best fit
我这里使用了装箱js实现https://github.com/jakesgordon/bin-packing
当我指定帧大小为 800x600 时
和块大小为 150x700，150x700 它会说，它不能容纳但是，有足够的 space。做成700x150,700x150也一样，都适合
如何调整代码，使其可以动态旋转块大小并适合框架。
这里使用的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;
}
}
我认为下面的代码可以解决问题...？！ （即，我做了有限的测试，但对于我测试的内容，它似乎有效。）
我基本上在 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;
}
}
希望这对你有用。
我正在添加第二个答案，因为这与第一个答案完全不同，并试图解决问题中提出的 2D Bin Packing 算法的更核心问题。使用该特定算法，splitNode 例程生成可用于拟合块的 down 和 right 节点，但没有考虑到随着可用节点的累积，相邻节点的并集的可能性节点可以容纳更大的块...
例如，在下面提出的算法中，给定一个 800x600 的初始堆，放置一个 500x300 的块将导致堆包含 (0,300)-(800,600) 和 (500,0)-(800,600) 的两个堆块.这两个 heapBlock 将在 (500,300)-(800,600) 的区域重叠，以确保在搜索适合块的位置时表示最大的 heapBlock 区域。而在 2D Bin Packing 算法中，down 或 right 中没有相交区域，而是有利于潜在重叠 space 到一个或另一个节点...
下面的算法试图通过实现代表最大可用块的可用堆块数组来弥补这个缺点，即使这些堆块彼此重叠。缺点是这引入了一个 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 将堆减少到最大大小的堆块列表。 （即，在每次调用 unionAll 之后，存在按宽度、高度或面积等对堆进行排序的机会，以便在搜索堆以放置下一个可用块时，如果堆被排序为最大的最小的，算法会将块放置在最大的可用堆块中，或者如果从最小到最大排序，块将放置在刚好足够大的堆块中......）无论如何，将把这些类型的优化作为练习.
另外，请以怀疑的态度看待这个算法，并进行适当的测试。
我这里使用了装箱js实现https://github.com/jakesgordon/bin-packing
当我指定帧大小为 800x600 时
和块大小为 150x700，150x700 它会说，它不能容纳但是，有足够的 space。做成700x150,700x150也一样，都适合
如何调整代码，使其可以动态旋转块大小并适合框架。
这里使用的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;
}
}
我认为下面的代码可以解决问题...？！ （即，我做了有限的测试，但对于我测试的内容，它似乎有效。）
我基本上在 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;
}
}
希望这对你有用。
我正在添加第二个答案，因为这与第一个答案完全不同，并试图解决问题中提出的 2D Bin Packing 算法的更核心问题。使用该特定算法，splitNode 例程生成可用于拟合块的 down 和 right 节点，但没有考虑到随着可用节点的累积，相邻节点的并集的可能性节点可以容纳更大的块...
例如，在下面提出的算法中，给定一个 800x600 的初始堆，放置一个 500x300 的块将导致堆包含 (0,300)-(800,600) 和 (500,0)-(800,600) 的两个堆块.这两个 heapBlock 将在 (500,300)-(800,600) 的区域重叠，以确保在搜索适合块的位置时表示最大的 heapBlock 区域。而在 2D Bin Packing 算法中，down 或 right 中没有相交区域，而是有利于潜在重叠 space 到一个或另一个节点...
下面的算法试图通过实现代表最大可用块的可用堆块数组来弥补这个缺点，即使这些堆块彼此重叠。缺点是这引入了一个 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 将堆减少到最大大小的堆块列表。 （即，在每次调用 unionAll 之后，存在按宽度、高度或面积等对堆进行排序的机会，以便在搜索堆以放置下一个可用块时，如果堆被排序为最大的最小的，算法会将块放置在最大的可用堆块中，或者如果从最小到最大排序，块将放置在刚好足够大的堆块中......）无论如何，将把这些类型的优化作为练习.
另外，请以怀疑的态度看待这个算法，并进行适当的测试。