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

2

This (if I understand it right: all permissible configurations are equiprobable) would be equivalent, in a statistical physics context, to generating samples from a Canonical ensemble of "hard disks" (2D version of the "hard spheres" system).

The standard procedure is Montecarlo simulation, via Metropolis algorithm: starting from a permisible configuration (you can find it by hard trying), you make small random displacements and either accept it (if the disks do not overlap), elsewhere keep ("repeat") the previous position. It is shown that, in the long run, the generated samples follow the desired distribution (though, of course, the succesive samples are not independent).

  • 0
    Not strictly true, as the set of permissible configurations of $n$ disks may not be connected (as a subset of $\mathbb{R}^{2n}$). For instance, in a rectangle just over $2$ disks wide and just high enough to hold a third disk, you can't get from a right-side-up triangle to an upside-down triangle. But when the disks aren't frozen, this is definitely the way to go.2015-06-20
1

It's not clear precisely what you mean by "random" here, but one interpretation is that the congiguration (the list of centres of the $N$ circles) should be uniformly distributed in the set of allowed configurations (a subset of ${\mathbb R}^{2N}$, presumably of positive measure). One algorithm to do this would be to generate a random $N$-tuple of points in the rectangle, accept it if all the distances between the centres are at least $2R+D$, otherwise reject it and generate a new $N$-tuple, continuing until you accept an $N$-tuple.