Как 2D-упаковка упакована программно?

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

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

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

Ответы

Ответ 1

я Googled "код упаковки bin" , и это был мой первый хит: http://codeincomplete.com/posts/2011/5/7/bin_packing/

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

В приведенной выше статье я объясню это более подробно, с диаграммами и кодом JavaScript. В нем также объясняется, как динамически выращивать лист спрайтов, а не заранее выбирать фиксированный размер.

Ответ 2

Все, что вам нужно, здесь: https://github.com/juj/RectangleBinPack

Существует бумага и достойная реализация на С++.

Если вам нужен еще более простой псевдокод, посмотрите на этот сайт: http://www.blackpawn.com/texts/lightmaps/

"Гильотинный пакет" называется там на основе дерева.