Random rectangles placement with minimal overlap and good dispersion

Question

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 82x176 pixels).

Now I have a Small Rectangle which is outside and I have to put it inside the Big Rectangle such that it is: - Randomly placed; - Not overlapping other Small Rectangles unless necessary due to lack of space (and, in this case, with the minimum 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.

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

Does anyone have any good ideas (code or pseudo-code is better, if possible, as normally my brain crashes when I see maths formulas)?

Answer 1

Your question is far too vague and far too difficult for anyone to post a solution; this isn't a solution. Rather, it is a lesson in how to attack this sort of problem. Start by reading this:

http://en.wikipedia.org/wiki/How_to_Solve_It

And maybe pick up a copy of the book while you're at it.

As Polya wisely says

If you can't solve a problem, then there is an easier problem you can solve: find it.

Here is a far easier version of your problem:

I have a straight line. On this line I have a collection of line segments. The start and end points of each line segment in the collection are both between 0 and some parameter n, inclusive. Some of the line segments might overlap each other.

Given the length of a new line segment, less than n, randomly place the new line segment such that its start and end points are both between 0 and n, and it does not "overlap" any line segment in the collection. If doing so is not possible then compute the start and end coordinates of the new line segment that minimize the amount it overlaps.

Can you write me a solution to that problem in C#? Believe me, if you can't solve the easier problem, then you'll never solve the rectangle version.

If you can't solve that problem then again make it easier until you can solve it. What if n is never bigger than 200? What if the collection of existing segments only has zero, one or two elements? What if the length of the new segment is always three? What if you get rid of the requirement of randomness? What if you get rid of the minimization problem? And so on. Keep on making the problem simpler until you can solve it. Once you have a solution to the simpler problem, try to adapt it into a solution to the larger problem. By practicing solving simpler problems you'll gain insight into solving the harder problem.

Answer 2

Depending on what you need it for, something may already exist. For example, if you are developing a web app, then look at jQuery Masonry: http://masonry.desandro.com/demos/basic-multi-column.html.

If that code serves your needs, but you're not doing a web app, then maybe you can inspect the source code to get what you need.

Hope this helps.