Решая небольшую задачу по созданию модуля joomla для компанента jwallpapers, столкнулся с легкой на первый взгляд проблемой: как оптимально плотно расположить несколько прямоугольников внутри другого контейнера. Алгоритм упаковки прямоугольников в контейнере заданных размеров краеугольная задача для всяческих галерей-мозаик, или интерфейсов с плавающими блоками управления, где элементы нужно расположить, как можно компактней.
Задача совсем не тривиальная, как кажется с первого взгляда на нее и решается самыми сложными методами, включая генетические алгоритмы. Также тут подходит алгоритм раскроя: оптимально раскроить некое полотно, чтобы осталось как можно меньше отходов. Здесь я приведу ряд найденных мною решений, их применение, преимущества и недостатки.
Первый найденный мной алгоритм на выходе дает вот такой результат
Вполне сносно, однако очевидны недостатки, к примеру непонятно, почему на второй картинке черный, зеленый, красный и фиолетовый прямоугольники не подняты вверх. Тоже и в третьей картинке. Общее направление получившейся мозаики также далеко не случайно и если в примерах с малым количеством прямоугольников мало заметно, то при большом их количестве отчетливо проясняется.
Построение идет от центра вправо и вниз. Вот код, который делает это:
function Rect(x, y, w, h){
this.x = x;
this.y = y;
this.w = w;
this.h = h;
}
Rect.prototype.fits_in = function(outer){
return outer.w >= this.w && outer.h >= this.h;
}
Rect.prototype.same_size_as = function(other){
return this.w == other.w && this.h == other.h;
}
function Node(){
this.left = null;
this.right = null;
this.rect = null;
this.filled = false;
}
Node.prototype.insert_rect = function(rect){
if(this.left != null)
return this.left.insert_rect(rect) || this.right.insert_rect(rect);
if(this.filled)
return null;
if(!rect.fits_in(this.rect))
return null;
if(rect.same_size_as(this.rect)){
this.filled = true;
return this;
}
this.left = new Node();
this.right = new Node();
var width_diff = this.rect.w - rect.w;
var height_diff = this.rect.h - rect.h;
var me = this.rect;
if(width_diff > height_diff){
// split literally into left and right, putting the rect on the left.
this.left.rect = new Rect(me.x, me.y, rect.w, me.h);
this.right.rect = new Rect(me.x + rect.w, me.y, me.w - rect.w, me.h);
}else{
// split into top and bottom, putting rect on top.
this.left.rect = new Rect(me.x, me.y, me.w, rect.h);
this.right.rect = new Rect(me.x, me.y + rect.h, me.w, me.h - rect.h);
}
return this.left.insert_rect(rect);
}
Как использовать:
к примеру в div с id=mosaic содержаться несколько элементов
<div id="mosaic" style="width: 200px; height: 200px; position: relative"> <div style="width: 20px; height: 61px; position: absolute; background-color: rgb(0, 0, 92)" id="div1"/> <div style="width: 23px; height: 28px; position: absolute; background-color: rgb(150, 217, 0);" id="div2"/> <div style="width: 21px; height: 90px; position: absolute; background-color: rgb(81, 196, 94); id="div3"/> *** <div style="width: 49px; height: 24px; position: absolute; background-color: rgb(0, 82, 99); id="div20"/> </div>
тогда расположить их нужным образом не составит труда
var start_node = new Node();
start_node.rect = new Rect(0, 0, width, height);
var tags = mosaic.getElementsByTagName('div');
for(var i in tags){
var div = tags[i];
var rect = new Rect(0, 0,parseInt(div.style.width),parseInt(div.style.height));
var node = start_node.insert_rect(rect);
if(node){
var r = node.rect;
div.style.left = r.x;
div.style.top = r.y;
}
}
результат можно посмотреть на подготовленном мной демо примере №1
Вариант номер два, еще более прост в использовании для начала качаем файл RectanglePacker.js и подключаем его
<script src="RectanglePacker.js" language="javascript"></script>
воспользуемся предыдущим примером для демонстрации
var tags = mosaic.getElementsByTagName('div');
var coords,
packer = new NETXUS.RectanglePacker( 200, 200 );
for(var i in tags){
var div = tags[i];
coords=packer.findCoords( parseInt(div.style.width), parseInt(div.style.height) );
div.style.left = coords.x;
div.style.top = coords.y;
}
результат будет примерно такой, скрипт можно пощупать на демо примере
для модуля я использовал именно этот вариант, потому, что он самый простой и действенный. Однако и в нем заметна тенденция упаковки от центра к краям.
Результат работы RectanglePacker
Реализация номер 3 по алгоритму упаковки бинарным деревом, сразу взгляните на демо пример
Вот, что пишет автор про свой скрипт
Это очень простое бинарное дерево основанное на алгоритме упаковки в контейнеры, которые инициализируются с фиксированной шириной и высотой. Лучшие результаты достигаются, когда входные блоки сортируются по высоте, а еще лучше при сортировке по максимальной величине (ширина, высота).
Результат работы такой
Для работы необходимо скачать один из двух скриптов packer.growing.js или packer.js Отличие двух файлов состоит в том, что первый упаковывает прямоугольники в неограниченный контейнер, а второму при инициализации можно задать размеры.
Используем так:
<script src="packer.growing.js" language="javascript"></script> <script src="packer.js" language="javascript"></script>
а затем
var blocks = [],
packer = new Packer( width, height );// либо GrowingPacker();
for(var i in tags){
var div = tags[i];
if(div.style)blocks[blocks.length]={w:parseInt(div.style.width),h:parseInt(div.style.height)};
}
blocks.sort(function(a,b) { return (b.w > a.w); }); // сортируем прямоугольники для улучшения результата
packer.fit(blocks);
for(var i in tags){
var div = tags[i];
var block = blocks[i];
if(div.style && block.fit){
div.style.left = block.fit.x;
div.style.top = block.fit.y;
div.style.width = block.w;
div.style.height = block.h;
}
}
Результат работы GroingPacker
На этом найденные мной реализации заканчиваются. В завершении внесу и свою лепту в разработку подобных алгоритмов. Моя реализация пожалуй самая медленная, она безбожно тормозит при расстановке 300 прямоугольников и не факт, что она чем-то лучше остальных. Однако она имеет право на жизнь, быть может кому-нибудь и пригодиться.
Результат работы примерно такой:
для работы потребуется файл xdRectPacker.js
Подключаем его
<script src="xdRectPacker.js" language="javascript"></script>
используем тот же пример, что и ранее
собираем все блоки в массив blocks
var mosaic = document.getElementById('mosaic');
var tags = mosaic.getElementsByTagName('div');
var blocks = [],
packer = new xdRectPacker( 200, 200 ); // создаем пакер
for(var i in tags){
var div = tags[i];
if( div.style )
blocks.push(new xdRect(0,0,parseInt(div.style.width),parseInt(div.style.height)));
}
далее расставляем все блоки
packer.fit(blocks);
for(var i in packer.pack){
var div = tags[i];
var block = packer.pack[i];
if(div.style){
div.style.left = block.x;
div.style.top = block.y;
div.style.width = block.w;
div.style.height = block.h;
}
}
Результат работы xdRectPacker
Ну и разумеется все исходники
Комментарии
1
2
3
4
var total_area = 1200 * 800;
var filled_area = 0;
var tags = mosaic.getElementsByTagName('div');
var coords,
packer = new NETXUS.RectanglePacker( 1200, 800 );
for(var i in tags){
var div = tags;
coords=packer.findCoords( parseInt(div.style.width), parseInt(div.style.height) );
div.style.left = coords.x;
div.style.top = coords.y;
}