Sign in to follow this  
bnf

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

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this