Как 2D упаковка бункера достигается программно?

Question

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

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

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

Answer 1

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

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

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