# What's a good way to calculate a subdivided square?

This topic is 4851 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

The title for this post was hard to word. Here's what I'm trying to do. I have a collection of rectangles, their sum of their area equals 100% and should fit inside a parent square. How can I figure out the position and dimensions of all these squares so that they fit inside the master square, perfectly filling it up with no gaps, so that there is adjecency between all squares? The percentages that these squares represent will change over time so I need to keep updating their size in length and width along with the neighboring square. Am I making sense?

##### Share on other sites
It is not completely obvious to me that what you are trying to do is even possible. Could you clarify whether the internal objects are squares or rectangles? You've used both words in your OP. If they are squares, the problem is just plain impossible in general : Consider three squares each of one-third the original area - once you've fit two of them in, there's no room for the third. If rectangles, the problem is trivial unless I misunderstood something : Just make each rectangle the height of your original, and the width x% of the original width, and place them next to each other. But maybe this contradicts your 'adjacency between all squares' requirement? Do you mean that each shape should touch each other shape? Again it is not obvious that this is possible, think of the four-colour theorem for maps.

##### Share on other sites
I meant rectangles because yeah you'd need to change the sides of them to even get close to having no gaps, but it sounds like its not possible or if it is it would be a problem that could take a very long time to solve with large sets of rectangles.

##### Share on other sites
Just because the sum of the areas of the rectangles is exactly the same as the area of the "master" square does not mean you could place all the rectangles in the master square.

Trivial example, a "master" square that is 3 by 3 then try to fit in 2 squares that are 2 by 2 and a square that is 1 by 1.

##### Share on other sites
Also to decide if it would even be possible to place the rectangles into the square would probably be a np-complete problem. Maybe someone smart could show us a reduction if it is, maybe to the subset sum problem or something. There is a challenge for you =p

##### Share on other sites
is this what ure talking about?

http://www.blackpawn.com/texts/lightmaps/default.html

1. 1
2. 2
Rutin
18
3. 3
4. 4
5. 5

• 9
• 9
• 14
• 12
• 10
• ### Forum Statistics

• Total Topics
633273
• Total Posts
3011168
• ### Who's Online (See full list)

There are no registered users currently online

×