Settling Cells

What it is

Points are scattered at random. Each one owns the territory closer to it than to any other point, its Voronoi cell. Every frame, each point steps towards the centre of its own cell, which changes all the territories, which moves all the centres.

Watch the readout. The spread of cell areas falls from around 60% to under 10%, and the mosaic turns into a honeycomb without anything ever being told to make hexagons.

How it works

This is Lloyd’s algorithm and it’s two lines of idea. Label every point in the space with its nearest site, then move each site to the average position of everything labelled with it. Repeat.

Cells are computed on a 150×150 grid rather than constructed exactly. For ninety sites that’s about two million distance comparisons per frame, which is fine, and it means the whole thing is nearest-site lookups and averages rather than a real Voronoi diagram with edges and vertices.

Drawing it needed one adjustment. Filling 22,500 individual rectangles per frame is slow enough to notice, so cells are batched into one Path2D per site. 90 fills instead of 22,500.

What surprised me

The convergence isn’t monotonic, and I’d assumed it would be.

I wrote a test asserting the area spread falls at every step and it failed. The cause is the grid. A site’s cell is a count of grid cells, so a site shifting a fraction of a grid cell can gain or lose a whole row of them at once. The underlying continuous quantity is falling smoothly, but the measured one occasionally ticks upward by a hair.

The test now allows up to two upward steps in ten and requires the total to fall by nearly half, which is the honest version of the claim. This converges, but what I am measuring is a quantised shadow of the thing that converges.

What I would do next

Weight the space so cells settle at deliberately different sizes, the way a dartboard or a treemap wants them.