An algorithm to randomly place circles at least D distance apart

I'm trying to work out how to write an algorithm to randomly place circles of R radius, in a 2d rectangle of arbitrary dimensions, such that each placed circle is at least D distance away from other circles in the rectangle,

The rectangle doesn't need to be filled, t开发者_JAVA百科o be more specific older circles may be destroyed, so I need to be able to place a new circle that respects the positions of the last N circles I've already placed (say 5 for eg), if it can't satisfy these conditions then I could handle it seperately.

Can anyone help me how to deduce such an algorithm, or perhaps point to some research that may cover this?

---

1 Place circle at random location
2 Loop over previous circles
3     if too close
4        delete new circle
5        goto 1
6 if need more circles
7     goto 1

To determine if there is room

Choose resolution required, say delta = D/100
for( x = 0; x < rectangle_size x += delta )
   for( y = 0; y < rectangle_size y += delta )
      unset failed
      loop over circles
           if x,y less than 2D from circle
              set failed
              break from circle loop
       if not failed
            return 'yes there is room'
return 'no, there is no room'

If you expect to have so many circles that there only a few holes left with room for new circles, then you could do this

clear candidates
Choose resolution required, say delta = D/100
for( x = 0; x < rectangle_size x += delta )
   for( y = 0; y < rectangle_size y += delta )
      unset failed
      loop over circles
           if x,y less than 2D from circle
              set failed
              break from circle loop
       if not failed
            add x,y to candidates
if no candidates
    return 'there is no room'
randomly choose location for new circle from candidates

---

1. Pick random startingspot.
2. Place circle
3. Move in random direction at least D
4. Goto 2 until distance to edge is < D or the distance to another circles center is < 2D

---

The first algorithm to come to mind is simulated annealing. Basically, you start out with the easiest solution, probably just a grid, then you "shake the box" in random ways to see if you get better answers. First you do large shakes, then gradually make them smaller. It sounds a little chaotic, and doesn't always produce the absolute best solution, but when something is computationally intensive it usually comes pretty close in a lot shorter time.

---

It really depends on what you mean by "random". Assuming that you want as close to a uniform distribution as possible, you will probably have to use an iterative solution like the one ravenspoint suggested. It may be slightly faster to place all of the circles randomly and then start replacing circles that don't meet your distance condition.

If the randomness isn't that important - i.e. if it just has to "look" random (which is probably fine if you're not doing something scientific), then grid your space up and place your N circles by choosing N indices in the grid. You could make it slightly more "random" by adding some noise to the location that you place the circle inside the grid. This would work really well for sparse placement.