|
Название: Упаковка прямоугольников в прямоугольник Отправлено: CuteBunny от Июнь 13, 2012, 15:38 Задача: дан прямоугольник с w, h. Его нужно заполнить максимальным кол-вом маленьких прямоугольников из n, с wi, hi, где i >=1 && i <= n, используя все имеющееся пространство, при чем маленькие прямоугольники не должны пересекаться внутри большого.
Как это сделать без трансформаций, без оптимизаций, самым прямым и доступным алгоритмом? Спасибо. Название: Re: Упаковка прямоугольников в прямоугольник Отправлено: Igors от Июнь 13, 2012, 16:20 Здесь трудности с understand'ом
Может быть все таки "куб" с размерами по осям (c, w, h) если у этих размеров 3 и Вы говорите о пространстве? Если "наибольшим количеством" значит "оптимальное заполнение" то задача выглядит слишком сложной. Наверное речь идет просто о заполнении большого куба непересекающимися кубиками из набора. А уж "наибольшим" или нет - как получится - извлекаем наибольший куб из набора и с ставим его в угол вмещающего. Не влезает - пробуем другой. В результате получается несколько новых свободных кубов. Для них повторяем процедуру расстановки рекурсивно. Ну вот и все Название: Re: Упаковка прямоугольников в прямоугольник Отправлено: CuteBunny от Июнь 13, 2012, 16:51 Да мне бы с прямоугольниками разобраться для начала...:)
Название: Re: Упаковка прямоугольников в прямоугольник Отправлено: Igors от Июнь 13, 2012, 17:06 Все то же самое, только 2 размера вместо 3
Название: Re: Упаковка прямоугольников в прямоугольник Отправлено: CuteBunny от Июнь 15, 2012, 11:40 Вроде сделал...
Правда без рекурсий. Пытаемся расположить прямоугольник справа рядом с любым прямоугольником на большом прямоугольнике, если он не пересекается с другими и находится в большом, то кладем его, иначе пытаемся вставить снизу от любого другого. Не самый наверное все-таки оптимальный вариант, т.к. я два раза делаю полный перебор всех имеющихся прямоугольников, т.е. сложность алгоритма в худшем случае составит O(n^2). В принципе можно как-то оптимизировать определения подходящего места - не делать весь перебор всех маленьких прямоугольников и проверять на пересечение с новым, но я пока не знаю, как сделать по-другому. На моей машине прямоугольник 300x300 заполняется рэндомными прямоугольниками ~1с. |