Poisson disk scattering or sampling has points more or less evenly distributed within the minimum distance r from each other. This distribution is similar to the receptor cells in the eyes of humans and other animals [Cook 1986]. Previously to this method I have implemented random placement based on jittering as described by Cook.
Bridson introduces a grid for growing distribution and also spacial indexing, which contains indices to samples or -1 for emtpy cells. Each cell should accommodate at most one point, that means that diagonal – largest distance – should be less (or equal) to the minimal radius, or r / sqrt(2) (r / sqrt(n) for n dimensions as described in the paper). Algorithm starts with a single point and grows around it. References to the current ‘grow’ points are stored in a separate array and points which may no longer accommodate new neighbours (e.g. internal) are removed from this array. When the grow array is empty algorithm terminates. Sampling is performed in annulus of radii r and 2r.
I have created a class using GML vector types (instead of boost geometry this time ;)) and using uniform distribution of boost libraries. I normalise the random value closer to the outer radius of annulus, or r*(2-rnd^2), where rnd is a uniform random value in range [0..1]. Neighbours are searched up to second edge away (e.g. (2, -1), (-1, -2)).
