javascript алгоритм двумерной упаковки или компактная расстановка прямоугольников

Информация о материале
Категория: JavaScript
Просмотров: 12974

 

Алгоритм свертки или упаковка прямоугольников в контейнер  Решая небольшую задачу по созданию модуля joomla для компанента jwallpapers, столкнулся с легкой на первый взгляд проблемой: как оптимально плотно расположить несколько прямоугольников внутри другого контейнера. Алгоритм упаковки прямоугольников в контейнере заданных размеров краеугольная задача для всяческих галерей-мозаик, или интерфейсов с плавающими блоками управления, где элементы нужно расположить, как можно компактней.

  Задача совсем не тривиальная, как кажется с первого взгляда на нее и решается самыми сложными методами, включая генетические алгоритмы. Также тут подходит алгоритм раскроя: оптимально раскроить некое полотно, чтобы осталось как можно меньше отходов.  Здесь я приведу ряд найденных мною решений, их применение, преимущества и недостатки. 

Первый найденный мной алгоритм на выходе дает вот такой результат

javascript алгоритм двумерной упаковки или компактная расстановка прямоугольников javascript алгоритм двумерной упаковки или компактная расстановка прямоугольников javascript алгоритм двумерной упаковки или компактная расстановка прямоугольников

Вполне сносно, однако очевидны недостатки, к примеру непонятно, почему на второй картинке черный, зеленый, красный и фиолетовый прямоугольники не подняты вверх. Тоже и в третьей картинке. Общее направление получившейся мозаики также далеко не случайно и если в примерах с малым количеством прямоугольников мало заметно, то при большом их количестве отчетливо проясняется.

javascript алгоритм двумерной упаковки или компактная расстановка прямоугольников

Построение идет от центра вправо и вниз. Вот код, который делает это:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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 содержаться несколько элементов

1
2
3
4
5
6
7
<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>

тогда расположить их нужным образом не составит труда

1
2
3
4
5
6
7
8
9
10
11
12
13
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 и подключаем его 

1
<script src="RectanglePacker.js" language="javascript"></script>

воспользуемся предыдущим примером для демонстрации

1
2
3
4
5
6
7
8
9
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;
}

результат будет примерно такой, скрипт можно пощупать на демо примере

javascript алгоритм двумерной упаковки или компактная расстановка прямоугольниковjavascript алгоритм двумерной упаковки или компактная расстановка прямоугольников - алгоритм раскрояjavascript алгоритм двумерной упаковки или компактная расстановка прямоугольников

для модуля я использовал именно этот вариант, потому, что он самый простой и действенный. Однако и в нем заметна тенденция упаковки от центра к краям.

Результат работы RectanglePacker

Реализация номер 3 по алгоритму упаковки бинарным деревом, сразу взгляните на демо пример

Вот, что пишет автор про свой скрипт

Это очень простое бинарное дерево основанное на алгоритме упаковки в контейнеры, которые инициализируются с фиксированной шириной и высотой. Лучшие результаты достигаются, когда входные блоки сортируются по высоте, а еще лучше при сортировке по максимальной величине (ширина, высота).

Результат работы такой

Алгоритм раскроя - упаковка прямоугольников внутри прямоугольникаАлгоритм раскроя - упаковка прямоугольников внутри прямоугольникаАлгоритм раскроя - упаковка прямоугольников внутри прямоугольника

Для работы необходимо скачать один из двух скриптов packer.growing.js или packer.js Отличие двух файлов состоит в том, что первый упаковывает прямоугольники в неограниченный контейнер, а второму при инициализации можно задать размеры. 

Используем так:

1
2
<script src="packer.growing.js" language="javascript"></script>
<script src="packer.js" language="javascript"></script>

а затем

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 прямоугольников и не факт, что она чем-то лучше остальных. Однако она имеет право на жизнь, быть может кому-нибудь и пригодиться. 

Результат работы примерно такой:

xdBinPacker оптимальная упаковка прямоугольников внутри контейнера, алгоритм раскроя xdBinPacker оптимальная упаковка прямоугольников внутри контейнера, алгоритм раскроя xdBinPacker оптимальная упаковка прямоугольников внутри контейнера, алгоритм раскроя

для работы потребуется файл xdRectPacker.js

Подключаем его

1
<script src="xdRectPacker.js" language="javascript"></script>

используем тот же пример, что и ранее

собираем все блоки в массив blocks

1
2
3
4
5
6
7
8
9
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)));
}

далее расставляем все блоки

1
2
3
4
5
6
7
8
9
10
11
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

Ну и разумеется все исходники

Оставлять комментарии могут только зарегистрированные пользователи

Комментарии  

Владимир
# Владимир 08.02.2014 21:31
В исходниках у вас блоки появляются за счет скрипта temp.js в котором рандомно задается размер блоков, при попытке использовать заранее имеющиеся блоки, скрипт RectanglePacker.js вылетает с ошибкой, не подскажете в чем косяк



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;

}
Ринат
# Ринат 28.02.2014 03:48
ну и ещё блоки друг на дружку наезжают так что ковырять скрипт и ковырять))