Мне было интересно, знает ли кто-нибудь о каких-либо алгоритмах, подходящих для объединения N числа прямоугольников неизвестного размера в наименьший возможный содержащий прямоугольник.
Оптимальным я имею в виду уменьшение количества оставшегося пробела в полученном прямоугольнике.
Я хотел бы использовать это для генерации css-спрайтов из серии изображений.
Большое спасибо,
Ян
Через упаковывая изображения в квадратную текстуру и Simon ответ. Я добрался до этой ссылки http://code.activestate.com/recipes/442299/
Я не проверял рецепт, но, похоже, разрешает использование не квадратных контейнеров.
Я думаю, что вы описываете вариант проблемы с "двумерной корзиной". Единственное отличие состоит в том, что у вас есть элементы и вы пытаетесь найти самый маленький прямоугольник.
Единственным способом гарантировать и оптимальное решение является грубая сила ответа. Это быстро становится неуправляемым для персональных компьютеров, когда у вас есть несколько прямоугольников и допускает возможность поворота.
В Википедии есть хорошая статья о проблеме упаковки http://en.wikipedia.org/wiki/Packing_problem
Вот хорошее описание алгоритма быстрой упаковки - http://www.codeproject.com/KB/web-image/rectanglepacker.aspx