Оптимальное размещение

[impersonalis]

Задача: есть набор прямоугольников и один Большой Прямоугольник.
Необходимо разместить прямоугольники (можно вращать их) т.о., чтобы как можно большая часть БП осталась незанятой (подогнать максимально плотно).
Продолжение задачи - БП несколько штук (т.е. все прямоугольники на одном БП априори не разместятся).

Идеи есть. Но может быть - это всем известный алгоритм и нефиг придумывать велик?

[alcoSHoLiK]

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

В графике эта задача может возникнуть при создании текстурных атласов. Для такого случая есть существующие решения. Одна из самых навороченных утилит -- http://www.texturepacker.com. Можно нагуглить и парочку опенсорсных проектов.

[.Squid]

http://www.blackpawn.com/texts/lightmaps/default.html

[impersonalis]

Документ от alcoSHoLiK утомил теорией, поэтому перешёл к коду .Squid. Автор заметки в "C++ pseudocode hybrid" родил настоящий брейнфак (порождая новые интерфейсы функций и опуская описания, допустив несколько ошибок и неоднозначностей), но вроде прототип на Блитце (после исправлений) работает на простых* примерах. Однако код угнетает.
Поскольку данным алгоритмом я интересуюсь в отрыве от какой-либо задачи, то я буду продолжать сидеть на стуле в ожидании лучших примеров =)

[.Squid]

Если тебя не устраивает реализация, а не сам алгоритм, то почему бы просто не реализовать его по-своему?

[SBJoker]

Самый простой алгоритм работает по такому принципу:
считает коэффициент для приоритета размещения на основе размера наибольшего из размеров. Потом картинки размещают в требуемый прямоугольник, начиная с картинки с наивысшим рейтингом, начиная с угла, так чтобы картинка была размещена как можно ближе к этому углу впоследствии. Вот примерно так с некоторыми оптимизациями и дополнительными правилами почти везде и сделано.