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

273

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

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

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

  • 128 * 32
  • 128 * 64
  • 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 и в пределах определенного максимального размера для каждого измерения)?

Огненный Лансер
источник
6
Разве второе решение не является оптимальным? Разве это не должно быть 128 на 224?
Мантас Видутис
«размеры этого пространства должны быть степенью двойки». Так что это не имеет значения, поскольку то, что это было / есть, потому что я не могу предположить, что не-степень двойки безоговорочно поддерживается базовым оборудованием.
Огненный Лансер
2
Как бы то ни было, в конце концов он упростил алгоритм (попробуйте уместить его все в 32x32, если nto, то попробуйте 64x32, затем 64x64, 128x64 и т. Д.) :)
Fire Lancer
См. Jair.org/media/3735/live-3735-6794-jair.pdf
Джим Балтер
Я положил один тип решения грубой силы здесь stackoverflow.com/a/47698424/1641247
Шон

Ответы:

67

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

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

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

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

SPWorley
источник
1
Я просто играл с чем-то вроде этого на небольшом листе бумаги, сейчас он выглядит довольно оптимально в большинстве случаев, даже без вращения прямоугольников или чего-либо еще
Fire Lancer
1
Я реализовал его и провел через него кучу тестовых данных, похоже, он неплохо справляется, оставляя лишь немного потерянных данных. Теперь мне просто нужно переписать мою реализацию, чтобы она была более эффективной, чем линейный поиск для каждого прямоугольника по доступному пространству, проверяя каждый пиксель, является ли точка заблокированной (против всех существующих линий) ...
Fire Lancer
4
Оптимальное решение дано в jair.org/media/3735/live-3735-6794-jair.pdf
Джим Балтер
2
Я с трудом представлял, как это может работать оптимально. Итак, я закодировал это (с квадратной формой), и результаты отличные. Вот демонстрационная анимация: imgur.com/ISjxuOR
Attila
@JimBalter квадратное пространство ... вероятно ... с точки зрения скорости и масштабируемости? На самом деле, нет?
Арек Бал
86

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

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

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

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

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

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

  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.
    Коэффициент аппроксимации: UD (I) <= (5/4) · OPT (I) + (53/8) H, где H - максимальная высота предметов; асимптотическая граница 5/4 плотная.

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

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

  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 плотная.

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

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

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

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

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

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

Неопределенное поведение
источник
6
Все это требует знания ширины пространства.
Quantum7
1
@ Quantum7, возможно, не слишком важен, поскольку OP требует, чтобы стороны были степенями двух, поэтому мы могли бы просто попробовать несколько измерений с достаточной площадью.
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
19

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

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

AIB
источник
Вот еще один хороший пример оптимизирующего алгоритма упаковки прямоугольников: codeproject.com/Articles/210979/…
Андерсон Грин,
Проблема также упоминается в: en.wikipedia.org/wiki/… Примечательно, что это ограничивает упаковку бинов одним бином неизвестного размера, интересно, если он все еще NP-завершен там.
Сиро Сантилли 郝海东 冠状 病 六四 事件 法轮功
17

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

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

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

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

Эрик
источник
9

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

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

Blindy
источник
3
Вы, вероятно, имеете в виду NP-полный.
звездный синий
7
Ну, а если NP завершена, то это легко решить, просто решите эквивалентный пример коммивояжера, и все готово. Но тривиально показать, что это не так, поскольку NP-полные проблемы - это проблемы принятия решений (вы получаете ответы «да / нет») и имеют алгоритм проверки полиномиального времени. Вопрос "есть ли расположение прямоугольников a, b, c ..., которые занимают меньшую площадь, чем 256 * 128, может быть NP-полным?"
Eclipse
2
@ Затмение верно. От jair.org/media/3735/live-3735-6794-jair.pdf «Задача оптимизации сложна с точки зрения NP, в то время как проблема определения, может ли набор прямоугольников быть упакован в заданную ограничивающую рамку, является NP-полной, через сокращение от упаковки в мусорное ведро (Korf, 2003). " Тем не менее, обратите внимание, что ФП попросил «довольно оптимальный путь», и в P есть решения для достаточно широких определений «достаточно».
Джим Балтер
Я также подозреваю NP-твердость, но нам нужна ссылка / доказательство.
Сиро Сантилли 郝海东 冠状 病 六四 事件 法轮功
2
Святая нить некро, Бэтмен. Это проблема упаковки, и в лучшем случае она уже является NP-трудной: en.wikipedia.org/wiki/Packing_problems
Blindy
2

Что вам нужно, это на 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);
}
Orbitus007
источник
1

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

Мартин Беккет
источник