// HACKER NEWS — CYBERSECURITY
Poisson Disk Sampling
In 2024, a team of nine mathematicians released a monstrous, nearly 1,000 page proof of the geometric Langlands conjecture. It is a crowning achievement in pure mathematics, and I have accepted that I will never understand even the statements that they proved, much less the proof itself.
On the total opposite end of the spectrum, in 2007, Robert Bridson published a one page paper that has nearly 1,000 citations and takes less than 10 minutes to fully understand. It presents a simple solution to a problem that commonly arises in computer graphics and simulations: placing things randomly, but not too close together.
Say you’re trying to procedurally generate a forest and need a way to place the trees. The problem with plain random sampling is obvious:
Some of the trees would be on top of each other! What we need is the ability to set a minimum distance between any two trees. A distribution of trees that obeys this rule is called a Poisson disk distribution. We can try a naive rejection sampling approach where we throw random darts and reject any point that falls within that minimum distance of any other point, but without a more clever data structure, it takes linear time to check collisions for each sample and the rejection rate quickly approaches one. Bridson’s algorithm gives us an efficient way to do this.
Suppose the desired minimum distance between points is rrr and we are working in a ddd-dimensional space. Bridson’s algorithm goes as follows:
The easiest way to uniformly sample the annulus is to generate a random unit vector v⃗∈Rd\vec{v} \in \mathbb{R}^dv∈Rd and a number xxx chosen uniformly from the interval [12d,1)\left[\frac{1}{2^d}, 1\right)[2d1,1), and then your final sample is 2rx1/d⋅v⃗2rx^{1/d}\cdot\vec{v}2rx1/d⋅v. A few years ago, I made a video that explains why this works. In two dimensions, picking a unit vector is equivalent to picking an angle θ∈[0,2π)\theta \in [0, 2\pi)θ∈[0,2π). In higher dimensions, you can normalize a vector where each component is sampled from a normal distribution.
There are two simple improvements to Bridson’s algorithm that I have found drastically reduce the number of iterations required to generate the same number of points. The first works in two dimensions, but the second works in higher dimensions as well.
Let’s start with the two dimensional improvement. Consider when the algorithm places a point ppp and then samples its annulus to get a new point qqq. We call ppp the parent of qqq. There is valuable information stored in the relation between these points. When we inevitably sample the annulus centered at qqq, there is an entire range of angles that we need not consider because the points within them would be too close to ppp. This range is represented by the dotted lines in the following figure.
While the visual intuition is easy to grasp, translating it into a formula is a tedious trigonometry exercise. I’ll spare you the details and claim without proof that the cone formed by the dotted lines is centered at angle α\alphaα and its width is 2β2\beta2β where
The only interesting part of this formula is the minimum that appears in the equation for β\betaβ. This accounts for the fact that either the inner or outer circle of the annulus can bound the cone, depending on the distance between ppp and qqq. We have to pick the minimum to guarantee that the intersection of the cone and the annulus is entirely contained in the circle. Note how the boundary points of the cone jump from the outer circle to the inner when the distance between the points crosses 3⋅r\sqrt{3} \cdot r3⋅r. The first term in the minimum is the angle of intersection with the outer circle and the second term is that with the inner circle.