Мне было интересно, знает ли кто-нибудь о каких-либо алгоритмах, подходящих для подгонки N числа прямоугольников неизвестного размера в наименьший возможный содержащий прямоугольник.Фиксация прямоугольников вместе оптимальным образом
Оптимальным я имею в виду уменьшение количества оставшегося пробела в полученном прямоугольнике.
Я хотел бы использовать это, чтобы генерировать css спрайты из серии изображений.
Большое спасибо,
Ян
Через packing images into square texture и Simon «s ответ я получил эту ссылку http://code.activestate.com/recipes/442299/
Я не проверял рецепт, но это, кажется, позволяет использовать неквадратные контейнеры ,
Я думаю, что вы описываете вариант проблемы с «двумерной корзиной». Единственное отличие состоит в том, что у вас есть элементы и вы пытаетесь найти самый маленький прямоугольник.
This обзор статья хорошее начало.
Теперь это мертвая ссылка. –
Единственный способ гарантировать и оптимальное решение - перенаправить ответ. Это быстро становится неуправляемым для персональных компьютеров, когда у вас есть несколько прямоугольников и допускается возможность поворота.
В Википедии есть хорошая статья на упаковках проблем http://en.wikipedia.org/wiki/Packing_problem
Вот хорошее описание алгоритма быстрой упаковки - http://www.codeproject.com/KB/web-image/rectanglepacker.aspx
Почему содержащая форма также должна быть квадратными? Почему он не может быть прямоугольным, но не квадратным? –
Хорошая точка. Я имел в виду прямоугольник. Я отредактирую. – madcapnmckay
http://www.google.com/search?q=rectangle+packing+algorithm – Dan