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

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

Оптимальным я имею в виду уменьшение количества оставшегося пробела в полученном прямоугольнике.

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

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

Ян

Ответы

Ответ 2

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

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

Ответ 3

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

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