Sign in to follow this  
Zarathos

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

Recommended Posts

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.

 

4J369.png

 

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)?

 

Thanks.

Edited by Zarathos

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