Weighted Voronoi Stippling

After watching Dan Shiffman’s YouTube video ¹ on the paper², I had to try it for myself.

Lloyd’s Relaxations

The algorithm builds on Lloyd’s Relaxations, which uses properties of Voronoi diagrams in a clever way. The goal of Lloyd’s Relaxations is to spread a point set so that all points even out their distance to their direct neighbours. Each iteration goes something like this:

1. Generate N random points
2. Update the Points in each iteration like so
   1. Calculate the Voronoi diagram of those points
   2. Find the centroid of each cell (d3’s polygonCentroid works well here)
   3. Move each point to its cell’s centroid

Maybe just me, but I find it highly satisfying when it converges.

Weighted Relaxations

Just one change to the loop above: instead of moving each point to the geometric centroid of its cell, move it to the weighted centroid — pulled toward the darker pixels so dots cluster where the image is darkest.

For each pixel (or subsample):

1. Find its containing cell
2. For each pixel of the cell
   1. Take its weight (brightness)
   2. Multiply pixel position by weight
   3. Add that to a running total
3. That sum is the weighted centroid
4. Move the point to the weighted centroid

Think of it as every pixel pulling the point toward itself with a force proportional to its weight — the weighted centroid is just where those forces reach equilibrium.

My implementation is not without its flaws. The effect works best on images with high contrast, large areas of low light and on edges. Areas of uniform value often lack uniform distribution with clusters forming randomly. It’s probably unavoidable to tweak those weights or add some brightness curves via the controls panel.

Hero: Based on Photo by Alexander Krivitskiy on Unsplash