Jump to content
  • Advertisement
Sign in to follow this  
bnf

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

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

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!