Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Mark Bennet Sep 11 '11 at 17:46
    
Yes that is exactly what I meant, thanks for the clarification –  Paul Newman Sep 11 '11 at 17:49
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...) –  Rahul Sep 11 '11 at 18:07
1  
Echoing @Rahul, see cs.virginia.edu/~gfx/pubs/antimony for instance. –  lhf Sep 11 '11 at 19:43
    
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. –  Greg Martin Nov 11 '11 at 2:27

2 Answers 2

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.

share|improve this answer

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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.