How do I generate non overlapping circles in a fixed region?

Question

What's the best way to generate a known number of non overlapping fixed radius circles in a limited space?

Answer 1

You could split the screen as a grid, and draw a circle in each "square" :)

Answer 2

If you just want as many circles in a small area as possible, use hexagonal close packing.

Answer 3

The way to do this with the least leftover space is to put the centers of the circles on a hexagonal grid, like the pattern you'd get if you were making a pyramid of coins.

Answer 4

See Circle packing theorem on wikipedia

Answer 5

This will depend on the shape of the space and other restrictions on the nature of the circles, which you didn't specify. For example, to generate N non-overlapping circles in a rectangle with height Y and length X, let the diameter of each circle be either X/10*N or Y/10*N, whichever is smaller, and let each center be spaced evenly on a horizontal line dividing the rectangle, spanning half its length.

Answer 6

I don't think your problem is well specified. Any constrains on the generation?

Here's a rejection algorithm for a random collection of non-overlapping circles of fixed radius:

1. Maintain a list of all circles
2. generate a candidate by
   1. generate a random center in the allowed region
   2. Test each existing circle in your list for a collision with the candidate, and reject if any collision is found. If all pass, add this candidate to your list.
3. Goto #1 until you're satisfied with the number generated

Edit: read the question more closely, the radius is specified...