Подходящие прямоугольники вместе оптимальным способом
Я задавался вопросом, знает ли кто-либо о каких-либо алгоритмах, подходящих для совмещения N количество прямоугольников неизвестного размера в самое маленькое, содержащее прямоугольник.
Оптимальным я имею в виду с сокращением количества пробела, перенесенного в получающемся, содержащем прямоугольник.
Я хотел бы использовать это для генерации спрайтов CSS от ряда изображений.
Большое спасибо,
Ian
3 ответа
Через упаковку изображений в квадратную текстуру и ответ Саймона я попал на эту ссылку http://code.activestate.com/recipes/442299/
Я не проверял рецепт, но, кажется, он позволяет использовать неквадратные контейнеры.
Единственным способом гарантировать оптимальное решение является перебор. Это быстро становится неуправляемым для персональных компьютеров, когда у вас есть несколько прямоугольников, и вы допускаете возможность вращения.
В Википедии есть хорошая статья о проблеме упаковки http://en.wikipedia.org/wiki/Packing_problem
Я думаю, то, что вы описали, является вариантом проблемы "упаковки двумерных корзин". Разница лишь в том, что у вас есть предметы, и вы пытаетесь найти наименьший прямоугольник.
Эта обзорная статья - хорошее начало.