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

Question

[Алексей Крайст]

Друзья, а есть ли уже такой алгоритм, с помощью которого можно вручную или автоматически расположить 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: Починил ссылки.

Comments

[Алексей Крайст]

В моём случае, плоскость, на которой необходимо расположить тайлы не ограничена. А в приведённых ниже примерах всё упирается в полосу.

Answer 1

[mamkaololosha]

Либо там пишут динамическое программирование с комбинаторной оптимизацией. Либо у них есть базовый тайл, который скейлится пропорционально x2 x4 x0.5 x0.25. Считают сумму площадей всех тайлов и если она меньше экрана - шаманят.

Answer 2

[Василий]

этаже задача но в 3d
https://habrahabr.ru/post/274527/

Answer 3

[Алексей Крайст]

Друг подсказал:
"Похоже на это"
https://m.habrahabr.ru/post/136225/