⚪ Lloyd's Relaxation

A Voronoi diagram partitions a plane into regions, one per seed point, where every location in a region is closer to that region's seed than to any other seed. In this simulation the partition is computed directly on pixels: for every point on the canvas the algorithm finds the nearest seed by brute-force distance comparison and colours that pixel accordingly, building the diagram up as a pixel-owner grid rather than as explicit polygon edges.

Each step it computes the current Voronoi diagram, finds the centroid (density-weighted centre of mass) of every cell, and moves each seed 85% of the way from its current position toward that centroid rather than jumping straight there. Doing this repeatedly is a form of gradient descent on the quantization energy E = Σ ρ·|x − c|², so the seeds gradually settle into positions where they already sit at their own cells' centroids.

A centroidal Voronoi tessellation (CVT) is the fixed point of Lloyd's algorithm: a partition where every seed is exactly the centroid of its own Voronoi cell. At that state there is no more net force pulling seeds around, and the energy stops decreasing. CVTs tend toward cells of similar size and roughly hexagonal shape because that configuration locally minimises the quantization energy for a uniform density.

The density field ρ(x,y) weights how much each pixel contributes when a cell's centroid is computed. Under Uniform density every pixel counts equally and cells converge to equal areas; under Radial or Gradient density, pixels in denser regions pull centroids toward themselves harder, so converged cells are smaller and more numerous where density is high. Paint mode lets you draw an arbitrary density field with the mouse, which is read back from an offscreen canvas each time the grid is rebuilt.

The energy E = Σ ρ·|x − c|² measures the total (density-weighted) squared distance from every pixel to its seed. Because each Lloyd step moves seeds toward their cells' centroids — the points that minimise exactly this sum for a fixed partition — every step can only decrease or maintain E, never increase it. As the tessellation approaches a centroidal Voronoi tessellation the improvements shrink and the energy curve flattens out, which is visible in the on-canvas energy plot.