How to randomly place rectangle with minimal overlap and nice dispersion

Question

I'd like to place an arbitrary number of rectangles into a fixed size parent such that they are:

1. Randomly placed
2. Randomly rotated to within a give degree range
3. Nicely dispersed around the center point (not all clumped into one corner)
4. Not overlapping unless necessary due to lack of space
5. With minimum overlap when it's necessary

To help you visualize the problem, I would like to scatter images inside a window for the user to choose one.

Googling had led me do various algorithms for packing etc, but nothing really addresses my requirements.

Does anyone have any good ideas?

Answer 1

It shouldn't be much more complicated than:

1. Place new rectangle in random location with random rotation. Simply using three random values (x, y, r) should do it, unless you want random size as well (in which case you'd need w and h too). This shouldn't give any corner-clumping (through random is random).
2. For every rectangle already placed, check for collisions. Here's one way. Also check for collisions with the side of the window (if you don't want things to extend past the screen); putting four dummy rectangles around the border may be a cheap way to do this.
3. If there are any collisions, then there are two choices: either move the new rectangle to a new random location or move both the new rectangle and the blocking rectangle away from each other until they no longer touch. Both have yays and nays - moving the new one only is faster and easier though it might not ever find a place where it fits if the page is really full; moving both is almost sure to be successful but takes longer and may result in chain-reaction collisions that would all have to be sorted out recursively.

In any case you'll want to try and keep the number of rectangles small, because the number of comparisions can quickly get really big. Using a short-circuit (such as "if they're halfway across the screen then don't bother looking closely") may help but isn't guarenteed.

EDIT: Okay, so requirement #5. Chances are that the push-both-rectangles-until-they-no-longer-collide-recursively method of adding new rectangles will end up being the simplest way to do this - just cut off the loop after a few thousand iterations and everything will have attempted to move as far away from everything else as possible, leaving minimum overlap. Or, leave the method running in a seperate thread so that the user can see them spreading out as more are added (also stopping it from looking like it's locking up while it's thinking), stopping once no rectangle has moved more than X units in one iteration.

Answer 2

How about this? Consider the rectangles you have to place as shaped, charged particles which repel one another and are also repelled by the walls of the container. You could start by (randomly) distributing them (and giving them random angles) in the container, then running a simulation where each "particle" moves in response to the forces acting on it (angles will change according to the turning moments of these forces). Stop when you hit a configuration within your tolerances.

You could simplify the calculations by treating each rectangle as an ellipse, which can be further simplified by treating each ellipse as a circle which has undergone scaling and rotation.

Answer 3

I don't understand requirement 2. Are you saying that the rectangles themselves are rotated around the rectangle center point, or that the rectangles only cover part of the 360 degree circle around the center point of all the rectangles.

I'm not sure that random is the way to go.

Simply divide the number of rectangles desired by 360 degrees. That's the number of degrees to offset each rectangle as it's being drawn. This should cover requirements 3, 4, and 5.