0
$\begingroup$

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.

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

Thanks in advance!

  • 0
    Not quite sure what you mean by distance here, but assuming you want the nearest points on the circumferences of your circles to be $D$ apart for each pair of circles, you need the centres to be at least $2R+D$ apart.2011-09-11
  • 0
    Yes that is exactly what I meant, thanks for the clarification2011-09-11
  • 3
    In computer graphics, this is known as Poisson-disk sampling. Google will find you lots of references to efficient algorithms, though the easiest (and slow) way is to just keep placing disks randomly on the domain one by one, rejecting those that are too close to previously placed disks. (Of course, you need a termination criterion, but that's only hard if you want to guarantee that the arrangement is maximal...)2011-09-11
  • 1
    Echoing @Rahul, see http://www.cs.virginia.edu/~gfx/pubs/antimony/ for instance.2011-09-11
  • 0
    You should specify if you simply want any random distribution, or if you want an algorithm that yields a pre-specified distribution on the set of all such configurations.2011-11-11

2 Answers 2