Оптимальное размещение
Задача: есть набор прямоугольников и один Большой Прямоугольник.
Необходимо разместить прямоугольники (можно вращать их) т.о., чтобы как можно большая часть БП осталась незанятой (подогнать максимально плотно). Продолжение задачи - БП несколько штук (т.е. все прямоугольники на одном БП априори не разместятся). Идеи есть. Но может быть - это всем известный алгоритм и нефиг придумывать велик? |
Ответ: Оптимальное размещение
Вложений: 1
Велосипед придумывать незачем. Прикрепил к посту доку, не помню где нашел. В ней описано множество алгоритмов. Практически во всех них предусмотрены повороты прямоугольников только на 90 градусов.
В графике эта задача может возникнуть при создании текстурных атласов. Для такого случая есть существующие решения. Одна из самых навороченных утилит -- http://www.texturepacker.com. Можно нагуглить и парочку опенсорсных проектов. |
Ответ: Оптимальное размещение
|
Ответ: Оптимальное размещение
Документ от alcoSHoLiK утомил теорией, поэтому перешёл к коду .Squid. Автор заметки в "C++ pseudocode hybrid" родил настоящий брейнфак (порождая новые интерфейсы функций и опуская описания, допустив несколько ошибок и неоднозначностей), но вроде прототип на Блитце (после исправлений) работает на простых* примерах. Однако код угнетает.
Поскольку данным алгоритмом я интересуюсь в отрыве от какой-либо задачи, то я буду продолжать сидеть на стуле в ожидании лучших примеров =) |
Ответ: Оптимальное размещение
Если тебя не устраивает реализация, а не сам алгоритм, то почему бы просто не реализовать его по-своему?
|
Ответ: Оптимальное размещение
Самый простой алгоритм работает по такому принципу:
считает коэффициент для приоритета размещения на основе размера наибольшего из размеров. Потом картинки размещают в требуемый прямоугольник, начиная с картинки с наивысшим рейтингом, начиная с угла, так чтобы картинка была размещена как можно ближе к этому углу впоследствии. Вот примерно так с некоторыми оптимизациями и дополнительными правилами почти везде и сделано. |
Часовой пояс GMT +4, время: 17:00. |
vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot