Мозаика прямоугольников разного размера

Я ищу некоторые указатели на алгоритмы, которые должны позволять разбивать прямоугольники разного размера без перекрытия.

Имея набор прямоугольников разного размера, разместите их на площади размером В x Ш без перекрытия. Цель состоит в том, чтобы максимизировать используемое пространство или, наоборот, минимизировать площадь зазоров. Если места недостаточно, переходите ко второй области того же размера и так далее.

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

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


optimization algorithm tiling
person Vladislavs Dovgalecs    schedule 30.07.2012    source источник
comment
Звучит как учебник по проблеме упаковки. Википедия ссылается на эту страницу, которая выглядит полезным.   -  person Kevin    schedule 30.07.2012
comment
Отлично! Это ключевое слово, которое сразу находит нужные алгоритмы! Я знал, что у этой проблемы должно быть особое имя! Спасибо!   -  person Vladislavs Dovgalecs    schedule 30.07.2012

Ответы (2)


arrow_upward
2
arrow_downward

Наиболее просто использовать kd-дерево для разделения дерева на вертикальное и горизонтальное евклидово двумерное пространство. Затем вы можете упаковать прямоугольник в одно из созданных пространств и рекурсивно разделить дерево. В Интернете доступен пример плагина древовидной карты Jquery. Masonry плагина jquery может сделать то же самое, но это больше похоже на решатель 1d bin-packing. 2D-бин-упаковка намного сложнее и может также означать вращение прямоугольников. Вот пример упаковки карт освещения: http://www.blackpawn.com/texts/lightmaps/default.html.

person Gigamegs    schedule 30.07.2012
comment
Хм, не могли бы вы подробнее описать свой подход? Что происходит с евклидовым пространством, если в нем много сотен или тысяч прямоугольников? Нет никакого риска иметь огромное дерево? - person Vladislavs Dovgalecs; 30.07.2012
comment
Xeon: Ты не можешь сравнить яблоки с апельсинами? Евклидово пространство — это математический закон. Это факт. - person Gigamegs; 30.07.2012
comment
Извините, но я не могу понять, как вы строите такое дерево и что означает разбиение евклидова пространства. То есть, как вы переходите от ваших входных прямоугольников к дереву, а затем как вы используете это дерево для получения окончательной мозаики. - person Vladislavs Dovgalecs; 30.07.2012
comment
@xeon: я добавил ссылку на пример c++. - person Gigamegs; 30.07.2012
comment
Спасибо! Как я и опасался, я задал уже существующий вопрос: stackoverflow.com/questions/8880975/ - person Vladislavs Dovgalecs; 30.07.2012

arrow_upward
0
arrow_downward

У меня есть одна идея, которая может пойти в правильном направлении. Идея состоит в том, чтобы отслеживать соотношение площади плитки и белой области в ограничивающей рамке.

ввод: неупорядоченный набор входных прямоугольников вывод: заполненная область

  1. Определить пустую ограничивающую рамку
  2. Выберите такие два прямоугольника A_i и B_j из входного набора, чья ограничивающая рамка B содержит минимальное соотношение пустых площадей.
  3. Обновите ограничивающую рамку с помощью двух оптимальных рамок.
  4. Поместите ограничивающую рамку в угол, скажем (1,1)
  5. Repeat until no boxes
    1. Take a new box from the set such as the updated bounding box has minimum blank
    2. Ограничить рост в горизонтальном или вертикальном направлении, если ширина или высота ограничивающей рамки превышает ширину или высоту области вывода.
    3. Если невозможно добавить новую рамку, перейдите к новой области В x Ш и перезапустите алгоритм, в противном случае обновите ограничивающую рамку.

Есть еще некоторые моменты, которые нужно определить - как лучше всего определить место ограничивающей рамки? Как наложить ограничения на рост ограничивающей рамки? Как эффективно найти лучшую ограничительную рамку?

person Vladislavs Dovgalecs    schedule 30.07.2012
comment
Нет, это алгоритм, который я должен быстро найти в своем приложении. У меня нет времени кодировать его с нуля, если уже существуют хорошие программные пакеты (быстрый поиск по ключевым словам проблема 2D-биннинга, проблема упаковки и т. д. выявил очень известную проблему во многих областях). - person Vladislavs Dovgalecs; 30.07.2012