Bridson's One-Page Algorithm for Poisson Disk Sampling, Made Faster

Poisson disk sampling solves a recurring problem in computer graphics and simulation: scattering points randomly while guaranteeing a minimum distance between any two of them — think placing trees in a procedurally generated forest without letting them overlap. Naive rejection sampling degrades badly as space fills up, since collision checks run in linear time and nearly every dart thrown gets rejected. Robert Bridson’s 2007 paper, a single page with close to 1,000 citations, fixes this by partitioning space into a grid whose cell size guarantees at most one point per cell, then growing the point set from an ‘active’ list: repeatedly pick an active point, sample its surrounding annulus a fixed number of times (Bridson suggests 30), and use the grid for constant-time collision checks. Points that can’t spawn a valid neighbor get retired. The author frames the algorithm as a deliberate counterpoint to the recent 1,000-page geometric Langlands proof — a reminder that some of the most useful ideas are the ones you can fully grasp in ten minutes.