Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 19 Mar 2013
Offline Last Active Mar 19 2013 04:39 PM

Topics I've Started

Placing rectangles with minimal overlap and nice dispersion inside a bouding rectangle.

19 March 2013 - 11:36 AM

I have a Big Rectangle (axis-oriented) containing a lot of Small Rectangles (with the same orientation of the parent and with a fixed size of 176H/82W pixels).


Now I have a Small Rectangle which lays outside the bounding box and I have to put it inside the Big Rectangle such that it is:

- Centered in the largest empty space if that space size in bigger than the Small Rectangle size.

- Not overlapping other Small Rectangles unless necessary due to lack of space (and, in this case, with the minimum possible overlap).


The algorithm, which will be used multiple times during my code execution, also needs to include a good distibution so that Small Rectangles will be nicely dispersed around the center of the Big Rectangle and not all clumped into one corner. The Big Rectangle can contain a large amout of Small Rectangles, but that number is unpredictable so grids are not a good solution.


Googling, I found several algorithms concerning rectangles packing, largest empty rectangle, random distributions... but nothing really addresses my requirements nor shows any code or pseudo-code implementation.




This image should bring you more into the problem.


Does anyone have a solution to suggest me for this? But first... is what I'm trying to do the right way to proceed? Which kind of approach is normally used by developers in this case? Is there any easier way to solve the problem using, for example, premade slots (which I don't really like)?