Расстановка прямоугольников на плоскости

 
0
 
Algorithms
ava
vivalaakam | 03.10.2013, 09:42
Есть 5 прямоугольников (A B C D E), расположенных на полскости, необходимо подобрать увеличить/уменьшить их так, чтобы они полность занимали определенную площадь (см. рисунок). Высоту и ширину можно менять в любую сторону, главное чтобы сохранялись пропорции прямоугольников. Подскажите алгоритм, как это расставить, или хотя бы в каком направлении двигаться.
[img]http://s1.ipicture.ru/uploads/20131003/oXoFU2fP.png[/img]
Comments (3)
ava
_Y_ | 03.10.2013, 12:03 #
Наверное ест' готовые алгоритмы, которых я не знаю. Если же лепит' самому, я бы начал скрещиват' алгоритм заполнения рюкзака с каким-либо алгоритмом случайной мутации размеров прямоугол'ников. Т.к прямоугол'ников мало, можно даже и обычный Монте-Карло; ну а хочется покрасивее - генетический алгоритм какой.

В целом промерно так:
1. Выбираем исходные размеры прямоугол'ников случайно или еще как. Но так, чтобы всe поместилис', хот' и с запасом.
2. Заполняем рюкзак.
4. Генетическими мутациями улучшаем заполнение, мутируя как размеры, так и последовател'ност' расположения. Упаковку каждого потомка делаем пакуя рюкзак. Критерий - наимен'шая незаполненная площад'. Потомки, не помещающиеся в рюкзак считаются метрворожденными.

Наворочено, конечно, зато прикол'но smile 
ava
ksnk | 03.10.2013, 16:55 #
_Y_, Заполнение рюкзака - не сюда. Тут можно свободно менять размеры, а все алгоритмы заполнения первым делом сортируют по размерам объектов ;)

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

Например для имеющейся в первом посте картинки, получим такую систему уравнений (Первая буква переменой - имя объекта, вторые: k - коэффициент уменьшения, h- высота, w - ширина. 0 - рамка габаритного размера):
-- Ak*Aw+Bk*Bw=0w
-- Ak*Aw+Ck*Cw+Ek*Ew=0w
-- Dk*Dw+Ek*Ew=0w
-- Ak*Ah+Dk*Dh=0h
-- Bk*Bh+Ck*Ch+Dk*Dh=0h
-- Bk*Bh+Ek*Eh=0h

6 уравнений - 5 неизвестных. Задача может не иметь решения.

Вероятно, такая избыточность получится для любой другой "картинки расположения". Так что решения можно и не найти.
Нужно вводить "дырку" в картинке, чтобы решение находилось всегда.
ava
_Y_ | 03.10.2013, 21:05 #
Цитата (ksnk @  3.10.2013,  16:55 findReferencedText)
_Y_, Заполнение рюкзака - не сюда. Тут можно свободно менять размеры, а все алгоритмы заполнения первым делом сортируют по размерам объектов ;)

Ну так и ладно. Генетическому алгоритму и проще. Пусть мутирует только размер объектов, а их расположение определяется рюкзаком.

ЗЫ: Я не настаиваю на оптимальности моего решения. Даже наоборот. Просто пришло в голову и наверняка будет работать. smile 
Please register or login to write.
Firm of day
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Contributors
  ksnk   vivalaakam   _Y_
advanced
Submit