| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Оптимальное размещение прямоугольников |
| Автор: Coriolis 22.8.2005, 14:27 |
| Здравствуйте, люди. Эту тему можно разместить и в разделе про графику, т.к. под прямоугольниками я понимаю текстуры. Задача: Имеется набор прямоугольников с известными размерами. Имеется прямоугольник определённых размеров. Необходимо оптимально разместить первые во втором, т.е. таким образом, чтобы поместилось как можно больше. Прямоугольники можно вращать на 90 градусов. На выходе координаты левого верхнего угла каждого прямоугольника и угол поворота. Я поискал по форуму – ничего подобного не встретил. |
| Автор: DENNN 22.8.2005, 14:39 |
| Наврное стоиттнаписать о том, можно ли вращать прямоугольники и как они сами могут быть ориентированны относительно большого. |
| Автор: Akina 22.8.2005, 14:51 |
| "Задача о рюкзаке". В поиск тебе... |
| Автор: Coriolis 22.8.2005, 16:13 |
| to DENNN Да-да, мне эта мысль пришла, правда поздно. Вращать можно, но только на 90 градусов. Т.е. стороны малых прямоугольников параллельны сторонам прямоугольника-контейнера. Вот, и на выходе - это координаты левого верхнего угла и угол поворота каждого прямоугольника. to Akina Я так понял, задача о рюкзаке оперирует одной составляющей. А в моей задаче их две - длинна и ширина. |
| Автор: Akina 22.8.2005, 16:20 |
| Coriolis Ты неправильно понял. Одномерный рюкзак - всего лишь частный случай. |
| Автор: Coriolis 22.8.2005, 16:24 |
| А! О! Я на форуме (здесь где-то рядом) встретил тему про рюкзак, и решил что это не моё (хотя очень похоже было). А подробное описание алгоритма здесь нигде не обсуждалось? Добавлено @ 16:30 АААААААА!!!! Бейте меня ногами!!! Пропустил-таки нужную тему, наплодил новую! вот, человек уже спрашивал: http://forum.vingrad.ru/index.php?showtopic=9160 |
| Автор: Coriolis 22.8.2005, 17:05 |
| В той теме отправили на matlab.ru - честно там поискал. Ниччего не нашёл. А вот Матлаб не у каждого стоит.  (это podval посоветовал )По ссылке http://algolist.manual.ru/maths/combinat/index.php скачал пдф-ку на инглийском (там в основном формулы) - мало чего понял. Видимо, придётся таки ковырять MatLab. Просто времени уйдёт уйма. (с учётом что я его в глаза не видел). |
| Автор: Гость_Программер 8.12.2005, 13:22 |
| Coriolis попробуй методом построения годографов. Для прямоугольников это не так уж и сложно. Я прогал так но без вращения. |
| Автор: laimerok 10.12.2005, 08:13 |
| Размещай в заданом прямоугольнике сначала маленькие , потом больше и больше по размерам |
| Автор: bsa 6.4.2006, 22:24 |
| Мне тоже нужна была данная прога. Думал, что смогу найти в инете (кстати, наткнулся на это форум). Не нашел. Зато нашел несколько идей по этому поводу, в т.ч. и почти готовый алгоритм, который я привожу ниже... Хочу описать данный алгоритм. Но сначала о терминах: ФОРМА - большой прямоугольник, на котором размещаются маленькие. МАТРИЦА - двумерный булевый массив, размеры которого совпадают с ФОРМОЙ (используется для определения пустого места). ДОСТУПНЫЙ/ИСХОДНЫЙ ПРЯМОУГОЛЬНИК - "маленький" прямоугольник, который надо разместить на форме Если требуется найти прямоугольник, одна из размерностей которого максимальна, то подразумевается, что среди прямоуг. с равными этими размерностями будет выбираться с наибольшей площадью. Кстати, рекомендуется перед началом выполнения алгоритма отсортировать исходные прямоугольники по убыванию высоты. Самое начало: задаем размер формы равным <ширина> x <высота = 0>. 1. Находим максимальный размер свободного прямоугольника на форме 2. Находим наиболее подходящий для него доступный прямоугольник. 2.1. Такой не существует - находим прямоугольник, высота которого максимальна, увеличиваем высоту формы на соответствующее значение (чтобы он влез) и переходим на п.1. 2.2. Такой существует - размещаем его на форме и помечаем в матрице, что соответствующее место занято и удаляем из доступных. 3. Находим все свободные прямоугольники на форме, ограниченные с 3-х сторон занятым пространством, ширина которых меньше, чем у наименее широкого из доступных. 4. повторяем п. 1. Самое сложное в данной программе было - это определить свободное место. Эту задачу я решил с помощью этой самой булевой матрицы. В ней все неподходящие прямоугольники просто помечаются, как занятые... В результате работы данного алгоритма в моей реализации ( http://sourceforge.net/projects/texpack ) упаковка получается порядка 80% - 98% (меньше бывает, если много крупных картинок, а размеры результирующих файлов не сильно больше). Скорость могу указать лишь приблизительно (на глаз): 411 картинок размерами от 32х32 до 300х300 были размещены на двух формах 2048х2048 (заполнение 98% и 86%) примерно за 5 секунд на машине AMD Athlon 64 3000+ 1024Mb под управлением Gentoo Linux с ядром 2.6.15. |
| Автор: Coriolis 7.4.2006, 10:30 |
| Не, для меня 5 сек много. Тем более для такой машины. Я исчу место по другому: Т.к. прямоугольники должны лежать вплотную друг к другу, то я для того чтобы определить, поместится ли данный прямоугольник, пробую поместить его с каждым уже находящимся на форме прямоугольником каждым углом к каждому углу, т.е. 12 комбинаций + 12 для повёрнутого. |
| Автор: bsa 7.4.2006, 17:21 |
| И что, быстрее?!? У меня больше всего времени уходит на фактическое размещение картинок. Кстати, а с чего ты взял, что прямоугольники ложатся вплотную?!? Программа работала 4.46 сек. Прогнал через профилер: 12% загрузка картинок. 82% сохранение картинок 1.11% собственно размещение картинок (определение что и куда нужно поместить). все остальное - тоже связано с фактическим размещением картинок. Так что, скорость работы - 411 прямоугольников за 0.0446 сек. или по-научному 9,22 прям/мс. А у твоего алгоритма какая скорость? Кстати, хотелось бы и на него взглянуть. |
| Автор: Coriolis 9.7.2007, 12:57 |
| bsa, сорри что долго не отвечал - система уведомлений на этом форуме как всегда на высоте. У меня вышел дуратский алгоритм, хоть и рабочий. Я потом наткнулся на статью англоязычную, с отличным алгоритмом, и сделал перевод. http://www.gamedev.ru/users/coriolis/articles/Packing_Lightmaps Тема закрыта. |