Я добавляю второй ответ, так как это радикальный отход от первого ответа, и пытается решить более центральную проблему с помощью алгоритма 2D Bin Packing, представленного в вопросе. С этим конкретным алгоритмом подпрограмма splitNode генерирует узлы down и right, доступные для подгонки блоков, но не учитывает возможность того, что по мере накопления доступных узлов объединение соседних узлов может вместить более крупные блоки. ..
Например, в предлагаемом алгоритме, приведенном ниже, при исходной куче 800x600, размещение блока 500x300 приведет к тому, что куча будет содержать два блока heapBlocks: (0,300) - (800,600) и (500,0) - (800,600). Эти два heapBlocks будут перекрываться в области (500 300) - (800 600), чтобы гарантировать, что максимальные области heapBlock представлены при поиске местоположения, подходящего для блока. Принимая во внимание, что в алгоритме 2D Bin Packing нет никакой пересекающейся области в down или right, но, скорее, предпочитает потенциальное перекрывающееся пространство одному или другому узлу ...
Приведенный ниже алгоритм пытается устранить этот недостаток путем реализации массива доступных heapBlocks, которые представляют самые большие доступные блоки, даже если эти heapBlocks перекрывают друг друга. Недостатком является то, что здесь вводится алгоритм 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 существует возможность сортировать кучу по ширине, высоте или площади и т. Д., Чтобы при поиске в куче следующий доступный блок для размещения, если куча сортируется по наибольшему или наименьшему, алгоритм поместит блок в наибольший доступный блок heapBlock, или, если отсортирован от наименьшего к наибольшему, блок будет помещен в достаточно большой блок heapBlock ...) В любом случае эти типы оптимизации будут оставлены в качестве упражнения.
Также, пожалуйста, посмотрите на этот алгоритм с некоторым скептицизмом и протестируйте его соответствующим образом.