Poisson disc sampling

Poisson disc sampling places points at random in an area, with one rule: no two points may be closer than a chosen distance r. The result looks random but even, without clumps and without large gaps.¹ In computer graphics such patterns are used to decide where to sample an image. A simple fast method was published by Robert Bridson of the University of British Columbia in 2007.¹

Why plain randomness looks wrong

If each point is placed by choosing its x and y at random, every point ignores all the others. As Mike Bostock puts it, "many samples are densely-packed, even overlapping, leading to large empty areas".² In the image at the top, each point has a circle of half the minimum distance around it. On the left, where the points are simply random, the red circles overlap; on the right, made by Bridson's algorithm, the circles may touch but never overlap.

Point patterns of the second kind are called blue noise, and Bridson notes that they are "generally considered ideal for many applications in rendering", pointing to Cook's "landmark paper" of 1986.¹

Bridson's algorithm

The simplest method, "dart throwing", keeps choosing random points and throws away any that land too close to an existing one. Bridson calls it "impractically inefficient".¹ His version looks for new points only next to points already placed:

1. A grid. Cover the area with square cells of side r/√2. A cell that size can hold at most one point, so checking for neighbours means looking at only a few cells.
2. A first point, anywhere at random. Put it on an "active list".
3. Grow. Pick a random point from the active list. Try up to k random candidates (typically 30) in the ring between distance r and 2r around it. Keep the first candidate that has no point within r, and add it to the active list. If none of the k fits, remove the point from the list: there is no room left around it.
4. Stop when the active list is empty.¹

Each round either adds a point or retires one, so the running time grows in proportion to the number of points.^1, 2 Bridson's point was that the same steps work in three or more dimensions.¹

New drawing

In drawings

For a drawing, the method gives positions for dots or small marks that are spread evenly without lining up in a grid. The points can also be the sites of a Voronoi diagram, and evenly spread dots are the aim of weighted Voronoi stippling. See also Generative art.