A
A
Alexey Christ2016-04-30 05:20:04
Algorithms
Alexey Christ, 2016-04-30 05:20:04

Is there an algorithm for optimal placement of multiple rectangles?

Friends, is there already such an algorithm with which you can manually or automatically arrange N given rectangles in such a way that when they are arranged on a plane, there are as few "gaps" as possible?
Examples:
• Tiles in Windows Metro style
cs406122.vk.me/g43446579/a_ec85082c.jpg
• A game similar to 15, only with tiles with different sides
1. iphonec.ru/files/iphonec/reg_images/unblock_me_1.png
2. static -5.app4smart.me/uploads/posts/thumbs/7251/f-...
• Illustration of the "golden ratio"
principle photo-element.ru/analysis/aks/image017.jpg
• Johanness Itten, illustration for task
lh4.ggpht .com/_rnO4JWKuX8U/TGgrc2ooPhI/AAAAAAAAAUU...
The last illustration is closest to the goal. That is, there are several rectangles with different sides, it can be both squares and rectangles, in any number and with known sides.
The point is to place them on the plane as closely as possible to each other, with a minimum number of gaps or without them at all, however, in the end, the "assembled" figure had a shape as close as possible to a rectangle and the area of ​​the final figure was as close as possible to the sum of the areas of the original rectangles.
Ffuuh, I hope I wrote it clearly :)
UPD: I fixed the links.

Answer the question

In order to leave comments, you need to log in

3 answer(s)
M
mamkaololosha, 2016-04-30
@mamkaololosha

Or they write dynamic programming with combinatorial optimization. Either they have a base tile that scales proportionally x2 x4 x0.5 x0.25. They calculate the sum of the areas of all tiles, and if it is less than the screen, they are shamanizing.

V
Vasily, 2016-04-30
@Foolleren

floor task but in 3d
https://habrahabr.ru/post/274527/

A
Alexey Christ, 2016-04-30
@Chrizt

A friend suggested:
"It looks like this"
https://m.habrahabr.ru/post/136225/

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question