Jason Davies

Poisson-Disc Sampling

Poisson-disc sampling produces points that are tightly-packed, but no closer to each other than a specified minimum distance, resulting in a more natural pattern.

The animation above uses an efficient O(n) algorithm due to Robert Bridson.

In Random Points on a Sphere, I used Mitchell’s best-candidate algorithm to obtain a poisson-disc distribution on a sphere.

Further Reading

• Mitchell’s best-candidate algorithm by Mike Bostock.
• A Spatial Data Structure for Fast Poisson-Disk Sample Generation, Daniel Dunbar and Greg Humphreys.
• Fast Poisson Disk Sampling in Arbitrary Dimensions, Robert Bridson, University of British Columbia.
• Adaptive Sampling with Polyominoes.
• Recursive Wang Tiles for Real-Time Blue Noise.

Thanks to Mike Bostock for fixing some bugs!