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


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

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

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

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

7 237

7 ответов:

быстрое и грязное решение первого прохода всегда отлично подходит для начала, как сравнение, если ничего другого.

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

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

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

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

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

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

  2. Next-Fit алгоритм уменьшения высоты (NFDH)
    NFDH упаковывает следующий элемент R (в не увеличивающейся высоте) на текущем уровне, если R подходит. В противном случае текущий уровень "закрывается" и создается новый уровень.
    Временная сложность: O (n·log n).
    Коэффициент аппроксимации: NFDH(I)

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

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

  5. алгоритм Бейкера вверх-вниз (UD)
    UD использует комбинацию BL и обобщение NFDH. Ширина полосы и элементов нормализуется таким образом, что полоса имеет единичную ширину. УД приказывает детали в не-увеличивая ширине и после этого делит предметы на пять групп, каждая с шириной в диапазоне (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 Коэффициент аппроксимации: UD (I)

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

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

  8. Сплит-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)

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

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

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

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

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

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

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

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

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

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

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

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

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

что вам нужно на 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);
}

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