Как 2D упаковка бункера достигается программно?
Есть несколько похожих вопросов о стековом потоке, но ни один из них, по-видимому, не дает осязаемого ответа, который может понять кто-то без четкого понимания сложных задач и алгоритмов.
Как выполнить 2D упаковку в бункер прямоугольных объектов? В моем случае я пытаюсь собрать несколько изображений в одно изображение для использования в качестве таблицы спрайтов, используя наименьшее количество места. Каждое изображение может иметь совершенно разные границы, но нет никаких установленных границ для контейнера.
Я надеялся, что кто-то, понимающий алгоритмы упаковки бункеров, сможет объяснить, как этого можно достичь программным путем, вместо общего обзора метода упаковки бинов.
2 ответа
Я прогуглил "код упаковки бина", и это был мой первый хит: http://codeincomplete.com/posts/2011/5/7/bin_packing/
Вот резюме: построить двоичное дерево. Каждая ветка в дереве содержит спрайт. Каждый листовой узел представляет доступное пространство. Первоначально дерево имеет только корневой узел, который представляет все доступное пространство. Чтобы добавить спрайт к дереву, найдите в дереве незанятый (листовой) узел, достаточно большой для размещения спрайта. Превратите этот узел из листа в ветвь, установив спрайт в качестве владельца узла и предоставив узлу двух дочерних элементов. Один дочерний элемент представляет оставшееся пространство справа от спрайта; другой представляет оставшееся пространство под спрайтом и первым дочерним элементом.
Статья, которую я привел выше, объясняет это гораздо более полно, с диаграммами и кодом JavaScript. Это также объясняет, как динамически увеличивать лист спрайта, а не выбирать фиксированный размер заранее.
Все, что вам нужно, это здесь: https://github.com/juj/RectangleBinPack
Есть бумага и достойная реализация C++.
Если вам нужен еще более простой псевдокод, взгляните на этот сайт: http://www.blackpawn.com/texts/lightmaps/
"Гильотинная пачка" там называется древовидной упаковкой.