Weighted Voronoi Stippling

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

Lloyd’s algorithm

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

1. Generate N random points
2. Then, in each iteration:
   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.

General Voronoi

Point Next Point

Reset Iterate Play

Weighted relaxation

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.

In each iteration, go over every pixel (or a subsample):

1. Find the cell it belongs to, which is the cell of its nearest point
2. Take its weight (its darkness)
3. Add its position times its weight, and the weight itself, to that cell’s running totals

Then for each cell, its position total divided by its weight total is the weighted centroid. Move the cell’s point there.

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.

pixel 0 / 35

Initial Point weighted centroid pixel weight

Reset Step Play

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. Tweaking those weights should help, so the controls have a weight curve: it reshapes how much ink each tone gets, and moving its first point to the right cuts off everything below a tone. I have not yet tested whether it cures the clustering.

Hero: Based on Photo by Dawn Casey on Unsplash