Placing random circles without overlap (and without using brute force)?

Question

I've just submitted a Java assignment in which I needed to draw some circles randomly on the screen as part of a game. One of the challenges given to us was to make sure none of the circles overlapped. I ended up going with a strange approach (because I wanted to :D) that basically just created a pattern from the center of the screen using trig, which was fun. Although the circles in this method never overlap, it's not ideal... the distribution of circles is fairly packed around the middle of the screen with very little space being used in the corners.

I also created a (commented out) brute force approach that simply rerolled new coordinates if a proposed circle's x,y coordinates intersected an already-created circle, which while theoretically capable of looping to infinite, most likely wouldn't exceed ten intersections.

After discussing solutions with a friend (and after a TON of googling), we're actually very interested to see how this could have been done without brute force. The requirements:

• 20 circles with ten units radius to be drawn on a 640x480 window
• absolutely no overlapping of circles
• otherwise random distribution across the screen

Possible, using the standard library?

Answer 1

1. Make a list of 640x480 entries and put consecutive numbers from 1 to 307.200 (640x480) in them. Each entry represents one pixel on the screen.
2. Randomly pick a number from 1 to 307.200, which represents a pixel on screen. Draw circle there.
3. Calculate all pixels that fall within 10 pixer radius of this circle. Remove all entries representing those pixels from list.

Repeat ten times.

Answer 2

Make a grid covering the whole screen; put the grid in a set. Each grid section should be ten units (the size of your circles).

1. for-loop 1-20.
2. Draw one grid tile from the set, randomly.
3. Place a circle in that grid tile; the center of the circle is the center of the grid tile.
4. Remove that grid tile from the set.
5. Next for-loop.

You now have twenty circles placed randomly that cannot overlap.

Now, what other spatial partitioning systems would be useful here and how?

Answer 3

1. Define a set containing valid coordinates.
2. Find a random element from that set.
3. Exclude from the set all coordinates that are no longer valid.
4. Go to 2.

Answer 4

This is something I have been looking for. I'm doing basically the same but in HTML5. Fortunately, I just needed to layout 100 circles with 20px radius on a 800px by 400px canvas. Using a brute force approach is working for up to 120 circles.

Here is my solution.

I'd like to try Peter's elegant approach using an array. I'm not sure how to yet but I will post here once I have it.