Chrizt
@Chrizt
Люблю Python, математику, BMX, MTB Street и жену;)

Существует ли алгоритм оптимального расположения нескольких прямоугольников?

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

Примеры:
• Тайлы в Metro стиле Windows
cs406122.vk.me/g43446579/a_ec85082c.jpg
• Игра, похожая на 15, только с тайлами с разными сторонами
1. iphonec.ru/files/iphonec/reg_images/unblock_me_1.png
2. static-5.app4smart.me/uploads/posts/thumbs/7251/f-...
• Иллюстрация принципа "золотого сечения"
photo-element.ru/analysis/aks/image017.jpg
• Йоханнесс Иттен, иллюстрация к заданию
lh4.ggpht.com/_rnO4JWKuX8U/TGgrc2ooPhI/AAAAAAAAAUU...

Ближе всего к цели именно последняя иллюстрация. То есть, имеется несколько прямоугольников с разными сторонами, это могут быть как квадраты, так прямоугольники, в любом количестве и с известными сторонами.
Смысл - разместить их на плоскости максимально плотно друг к другу, с минимальным количеством зазоров или вовсе без них, однако в конечном итоге, "собранная" фигура имела форму, максимально близкую к прямоугольнику и площадь итоговой фигуры была максимально близка к сумме площадей исходных прямоугольников.

Ффуух, надеюсь, понятно написал :)

UPD: Починил ссылки.
  • Вопрос задан
  • 6813 просмотров
Пригласить эксперта
Ответы на вопрос 3
@mamkaololosha
Либо там пишут динамическое программирование с комбинаторной оптимизацией. Либо у них есть базовый тайл, который скейлится пропорционально x2 x4 x0.5 x0.25. Считают сумму площадей всех тайлов и если она меньше экрана - шаманят.
Ответ написан
Комментировать
Foolleren
@Foolleren
Компас есть, копать не люблю...
этаже задача но в 3d
https://habrahabr.ru/post/274527/
Ответ написан
Комментировать
Chrizt
@Chrizt Автор вопроса
Люблю Python, математику, BMX, MTB Street и жену;)
Друг подсказал:
"Похоже на это"
https://m.habrahabr.ru/post/136225/
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы