Какой алгоритм можно использовать для упаковки прямоугольников разных размеров в наименьший возможный прямоугольник довольно оптимальным способом?

Question

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

Мне известны различные алгоритмы упаковки, которые максимально упакуют элементы в заданное пространство, однако в этом случае мне нужен алгоритм, чтобы определить, насколько большим должно быть это пространство.

Например, скажем, у меня есть следующие прямоугольники

• 128 * 32
• 128 * 64 * 1 010 *
• 64 * 32
• 64 * 32

Они могут быть упакованы в 128 * 128

 _________________
|128*32          |
|________________|
|128*64          |
|                |
|                |
|________________|
|64*32  |64*32   |
|_______|________|

Однако, если бы имелись также 160 * 32 и 64 * 64, ему потребовалось бы пространство 256 * 128

 ________________________________
|128*32          |64*64  |64*32  |
|________________|       |_______|
|128*64          |       |64*32  |
|                |_______|_______|
|                |               |
|________________|___            |
|160*32              |           |
|____________________|___________|

Какие существуют алгоритмы, которые могут упаковать группу прямоугольников и определить требуемый размер для контейнера (до степени 2 и в пределах заданного максимального размера для каждого измерения)?

Answer 1

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

Вот выдержка из алгоритмов:

1. Алгоритм уменьшения первой высоты (FFDH)
   FFDH упаковывает следующий предмет R (в не увеличивающейся высоте) на первом уровне, где R соответствует. Если ни один уровень не может вместить R, создается новый уровень.
   Временная сложность FFDH: O (n · log n).
   Коэффициент аппроксимации: FFDH (I) <= (17/10) · OPT (I) +1; асимптотическая граница 17/10 плотная. </p>

2. Алгоритм уменьшения высоты следующего приближения (NFDH)
   NFDH упаковывает следующий элемент R (в не увеличивающейся высоте) на текущий уровень, если R соответствует. В противном случае текущий уровень «закрыт» и создается новый уровень.
   Временная сложность: O (n · log n).
   Коэффициент аппроксимации: NFDH (I) <= 2 · OPT (I) +1; асимптотическая граница 2 плотная. </p>

3. Алгоритм оптимальной посадки по убыванию высоты (BFDH)
   BFDH упаковывает следующий элемент R (в не увеличивающейся высоте) на уровне среди тех, которые могут вместить R, для которых остаточное горизонтальное пространство является минимальным. Если ни один уровень не может вместить R, создается новый уровень.

4. Алгоритм снизу-слева (BL)
   BL элементы первого порядка по не увеличивающейся ширине. BL упаковывает следующий предмет как можно ближе к основанию, а затем как можно ближе к левому краю, чтобы он мог не перекрываться с любым упакованным предметом. Обратите внимание, что BL не является алгоритмом упаковки, ориентированным на уровень.
   Временная сложность: O (n ^ 2).
   Коэффициент приближения: BL (I) <= 3 · OPT (I). </p>

5. Алгоритм Бейкера-Up-Down (UD)
   UD использует комбинацию BL и обобщение NFDH. Ширина полосы и предметов нормализуются так, чтобы полоса имела единичную ширину. UD упорядочивает элементы по не увеличивающейся ширине, а затем разделяет элементы на пять групп, каждая из которых имеет ширину в диапазоне (1/2, 1], (1 / 3,1 / 2], (1 / 4,1 / 3 ], (1 / 5,1 / 4], (0,1 / 5]. Полоса также разделена на пять областей R1, ..., R5. В основном, некоторые элементы ширины в диапазоне (1 / i + 1, 1 / i], для 1 <= i <= 4, упакованы в область Ri с помощью BL. Поскольку BL оставляет пространство увеличивающейся ширины сверху вниз на правой стороне полосы, UD использует это преимущество первым упаковка элемента в Rj для j = 1, ..., 4 (по порядку) сверху вниз. Если такого пространства нет, элемент упаковывается в Ri с помощью BL. Наконец, элементы размером не более 1/5 упакованы в пространства в R1, ..., R4 (обобщенным) алгоритмом NFDH. Опять же, если в этих областях нет места, элемент упаковывается в R5 с использованием NFDH. <br> Коэффициент аппроксимации: UD (I) <= (5/4) · OPT (I) + (53/8) H, где H - максимальная высота предметов; асимптотическая граница 5/4 плотная. </p>

6. Алгоритм обратной подгонки (RF)
   RF также нормализует ширину полосы и предметов так, чтобы полоса имела единичную ширину. RF сначала укладывает все элементы шириной больше 1/2. Остальные элементы сортируются по не увеличивающейся высоте и будут упакованы выше высоты H0, достигнутой теми, кто больше 1/2. Затем РФ повторяет следующий процесс. Грубо говоря, RF упаковывает предметы слева направо так, чтобы их дно было вдоль линии высоты H0, пока не осталось места. Затем упаковывает предметы справа налево и сверху вниз (так называемый обратный уровень), пока общая ширина не станет как минимум 1/2. Затем обратный уровень падает до тех пор, пока (по крайней мере) один из них не коснется какого-либо предмета ниже. Раскрытие как-то повторяется.
   Коэффициент приближения: RF (I) <= 2 · OPT (I). </p>

7. алгоритм Штейнберга
   Алгоритм Стейнбергаритм, обозначенный в статье буквой M, оценивает верхнюю границу высоты H, необходимую для упаковки всех элементов, так что доказано, что входные элементы могут быть упакованы в прямоугольник ширины W и высоты H. Затем они определяют семь процедур (с семью условиями), каждое из которых делит задачу на две меньшие и решает их рекурсивно. Было показано, что любая поддающаяся решению проблема удовлетворяет одному из семи условий.
   Коэффициент приближения: M (I) <= 2 · OPT (I). </p>

8. Алгоритм Split-Fit (SF) SF делит предметы на две группы: L1 с шириной больше 1/2 и L2 не более 1/2. Все предметы L1 сначала упакованы FFDH. Затем они располагаются так, чтобы все элементы с шириной более 2/3 были ниже элементов с шириной не более 2/3. Это создает прямоугольник R пространства с шириной 1/3. Остальные элементы в L2 затем упаковываются в R, а пространство над теми, которые упакованы в L1, используют FFDH. Уровни, созданные в R, считаются ниже уровней, созданных выше упаковки L1.
   Коэффициент приближения: SF (I) <= (3/2) · OPT (I) + 2; асимптотическая граница 3/2 плотная. </p>

9. Алгоритм Слеатора
   Алгоритм Слитера состоит из четырех шагов:

   1. Все элементы шириной более 1/2 упакованы друг на друга в нижней части полосы. Предположим, что h0 - высота полученной упаковки. Вся последующая упаковка будет происходить выше h0.

   2. Остальные предметы упорядочены по возрастанию. Уровень предметов упаковывается (в порядке увеличения высоты) слева направо по линии высоты h0.

   3. Затем в середине рисуется вертикальная линия, чтобы разрезать полосу на две равные половины (обратите внимание, что эта линия может разрезать предмет, который частично упакован в правой половине). Нарисуйте два горизонтальных отрезка длиной одну половину, один поперек левой половины (называемый левой базовой линией) и один поперек правой половины (называемой правой базовой линией) настолько низко, насколько возможно, чтобы две линии не пересекали какой-либо элемент.

   4. Выберите левую или правую базовую линию, которая имеет меньшую высоту, и упакуйте уровень предметов в соответствующую половину полосы, пока следующий предмет не станет слишком широким.

   Формируется новая базовая линия, и шаг (4) повторяется на нижней базовой линии, пока все элементы не будут упакованы.
   Временная сложность: O (n · log n).
   Коэффициент аппроксимации алгоритма Слеатора составляет 2,5, что является жестким.

Answer 2

Быстрое и грязное решение первого прохода - это всегда отличное решение для сравнения, если не считать ничего другого.

Жадное размещение от большого к маленькому.

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

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

Answer 3

Посмотрите на проблемы с упаковкой . Я думаю, что ваша подпадает под "2D упаковка бен". Вы должны научиться многому из решений этой и других проблем упаковки.

См. Также: Упаковка данных прямоугольного изображения в квадратную текстуру.

Answer 4

Существует обширная литература по этой проблеме. Хорошая жадная эвристика - это размещение прямоугольников от наибольшей области до наименьшей в первой доступной позиции по направлению к дну и слева от контейнера. Подумайте о гравитации, потянув все предметы вниз в левый нижний угол. Для описания этого Google "Chazelle внизу слева упаковки".

Для оптимальных решений современные методы могут упаковать более 20 прямоугольников за несколько секунд. У Хуанга есть алгоритм , который отделяет проблему нахождения наименьшего ограничивающего прямоугольника от задачи определения, может ли набор прямоугольника поместиться в ограничивающий прямоугольник определенного размера. Вы даете его программе набор прямоугольников, и он сообщает вам наименьшую ограничивающую рамку, необходимую для их упаковки.

В вашем случае ваш внешний цикл должен повторяться от наименьшего возможного ограничивающего прямоугольника вверх (ширина и высота последовательно увеличиваются на степени два). Для каждого из этих ограничивающих прямоугольников проверьте, можете ли вы найти упаковку для ваших прямоугольников. Вы получите кучу ответов «нет», вплоть до первого ответа «да», который, как гарантируют, будет оптимальным решением.

Для внутреннего цикла вашего алгоритма - того, который отвечает «да» или «нет» ограничивающему прямоугольнику определенного размера, я бы посмотрел ссылку на Хуан и просто реализовал его алгоритм. Он включает в себя множество оптимизаций поверх базового алгоритма, но вам действительно нужно только основное мясо и картофель. Поскольку вы хотите обрабатывать повороты, в каждой точке ветвления во время поиска просто попробуйте оба поворота и возврат, если оба поворота не приводят к решению.

Answer 5

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

Хорошая новость заключается в том, что из-за необходимости упаковать двухмерные прямоугольники в ограниченное двухмерное пространство вы можете сократить множество возможностей на ранних этапах, так что это может быть НЕ ТАК плохо.

Answer 6

То, что вам нужно, это на https://github.com/nothings/stb/blob/master/stb_rect_pack.h

образец:

stbrp_context context;

struct stbrp_rect rects[100];

for (int i=0; i< 100; i++)
{
    rects[i].id = i;
    rects[i].w = 100+i;
    rects[i].h = 100+i;
    rects[i].x = 0;
    rects[i].y = 0;
    rects[i].was_packed = 0;
}

int rectsLength = sizeof(rects)/sizeof(rects[0]);

int nodeCount = 4096*2;
struct stbrp_node nodes[nodeCount];


stbrp_init_target(&context, 4096, 4096, nodes, nodeCount);
stbrp_pack_rects(&context, rects, rectsLength);

for (int i=0; i< 100; i++)
{
    printf("rect %i (%hu,%hu) was_packed=%i\n", rects[i].id, rects[i].x, rects[i].y, rects[i].was_packed);
}

Answer 7

Я использую один из:

https://codereview.stackexchange.com/questions/179565/incremental-2d-rectangle-bin-packer?newreg=cce6c6101cf349c58423058762fa12b2

Он реализует алгоритм гильотины и требует в качестве входных данных одно измерение и пытается оптимизировать другое (вы также можете установить максимум с небольшим изменением в коде). Может быть, если вы попробуете разные значения двух значений, это сработает для вас.

Это ни в коем случае не является оптимальным, но он небольшой, переносимый (только .h) и не имеет никакой другой зависимости, кроме C ++ и STL.

Answer 8

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