Соединение прямоугольников оптимальным образом

Question

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

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

Я хотел бы использовать это для генерации спрайтов CSS из серии изображений.

Большое спасибо,

Ian

Answer 1

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

Эта обзорная статья - хорошее начало.

Answer 2

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

В Википедии есть хорошая статья о проблеме упаковки. http://en.wikipedia.org/wiki/Packing_problem

Answer 3

Через упаковка изображений в квадратную текстуру и Ответ Саймона Я попал по этой ссылке http://code.activestate.com/recipes/442299/

Я не проверял рецепт, но похожеразрешить использование неквадратных контейнеров.

Answer 4

Вот хорошее описание алгоритма быстрой упаковки - http://www.codeproject.com/KB/web-image/rectanglepacker.aspx