|
Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения |
28.08.2011, 00:09
|
#1
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Оптимальное размещение
Задача: есть набор прямоугольников и один Большой Прямоугольник.
Необходимо разместить прямоугольники (можно вращать их) т.о., чтобы как можно большая часть БП осталась незанятой (подогнать максимально плотно).
Продолжение задачи - БП несколько штук (т.е. все прямоугольники на одном БП априори не разместятся).
Идеи есть. Но может быть - это всем известный алгоритм и нефиг придумывать велик?
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
28.08.2011, 01:31
|
#2
|
Дэвелопер
Регистрация: 17.01.2006
Сообщений: 1,512
Написано 78 полезных сообщений (для 110 пользователей)
|
Ответ: Оптимальное размещение
Велосипед придумывать незачем. Прикрепил к посту доку, не помню где нашел. В ней описано множество алгоритмов. Практически во всех них предусмотрены повороты прямоугольников только на 90 градусов.
В графике эта задача может возникнуть при создании текстурных атласов. Для такого случая есть существующие решения. Одна из самых навороченных утилит -- http://www.texturepacker.com. Можно нагуглить и парочку опенсорсных проектов.
|
(Offline)
|
|
Эти 3 пользователя(ей) сказали Спасибо alcoSHoLiK за это полезное сообщение:
|
|
28.08.2011, 02:25
|
#3
|
Дэвелопер
Регистрация: 06.04.2009
Адрес: Запорожье
Сообщений: 1,500
Написано 1,011 полезных сообщений (для 4,642 пользователей)
|
Ответ: Оптимальное размещение
__________________
|
(Offline)
|
|
Эти 2 пользователя(ей) сказали Спасибо .Squid за это полезное сообщение:
|
|
28.08.2011, 15:44
|
#4
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Ответ: Оптимальное размещение
Документ от alcoSHoLiK утомил теорией, поэтому перешёл к коду .Squid. Автор заметки в "C++ pseudocode hybrid" родил настоящий брейнфак (порождая новые интерфейсы функций и опуская описания, допустив несколько ошибок и неоднозначностей), но вроде прототип на Блитце (после исправлений) работает на простых* примерах. Однако код угнетает.
Поскольку данным алгоритмом я интересуюсь в отрыве от какой-либо задачи, то я буду продолжать сидеть на стуле в ожидании лучших примеров =)
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
28.08.2011, 21:03
|
#5
|
Дэвелопер
Регистрация: 06.04.2009
Адрес: Запорожье
Сообщений: 1,500
Написано 1,011 полезных сообщений (для 4,642 пользователей)
|
Ответ: Оптимальное размещение
Если тебя не устраивает реализация, а не сам алгоритм, то почему бы просто не реализовать его по-своему?
__________________
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
28.08.2011, 22:44
|
#6
|
Злобный Админ
Регистрация: 04.09.2005
Сообщений: 5,926
Написано 3,415 полезных сообщений (для 9,330 пользователей)
|
Ответ: Оптимальное размещение
Самый простой алгоритм работает по такому принципу:
считает коэффициент для приоритета размещения на основе размера наибольшего из размеров. Потом картинки размещают в требуемый прямоугольник, начиная с картинки с наивысшим рейтингом, начиная с угла, так чтобы картинка была размещена как можно ближе к этому углу впоследствии. Вот примерно так с некоторыми оптимизациями и дополнительными правилами почти везде и сделано.
__________________
|
(Offline)
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 02:53.
|