I'd like to place as many random points as possible in a 2D square $S=[0,1]x[0,1]$ such that the euclidean distance $d$ between any two points $d$ is greater than a given value $b$ (b is small). I'm interested in an iterative construction algorithm that successively limits the remaining space where points can be placed. In such a case, I'm curious how to efficiently characterize the available space and how to check the stopping criteria "until no more points can be placed". Any help would be greatly appreciated.
3
$\begingroup$
$\endgroup$
4
$\begingroup$
$\endgroup$
This is called Poisson disk sampling, and there are a lot of papers on the subject. Here are a few:
- D Dunbar, G Humphreys (2006). A spatial data structure for fast Poisson-disk sample generation.
- L. Wei (2008). Parallel Poisson disk sampling.
- R. Bridson (2007). Fast Poisson disk sampling in arbitrary dimensions.
- M. Ebeida et al. (2011). Efficient maximal Poisson-disk sampling
The last one appears to be what you what.
-
$\begingroup$ Yes, I think this is exactly what I was looking for! I didn't even realize it had a technical name: Poisson disk sampling. Thanks, Geoffrey! $\endgroup$ – Paul♦ Aug 27 '12 at 15:09
