🕸️ Voronoi Diagrams & Lloyd's Relaxation

🕸️ What It Demonstrates

A Voronoi diagram partitions the plane into regions ("cells") according to a set of scattered points called sites: every point in a given cell is closer to that cell's site than to any other. This simulation computes the diagram directly by rasterising — for every sample point across the canvas it performs a brute-force nearest-site search over all sites and colours that sample by the winning site's index, which is the simplest possible way to build a mathematically correct Voronoi diagram without implementing a sweep-line or divide-and-conquer algorithm.

Lloyd's algorithm (also called Lloyd's relaxation) repeatedly improves the layout of the sites: for each cell, it computes the centroid (average position) of every raster sample currently assigned to that cell, then moves the site to that centroid. Recomputing the diagram after each move and repeating this process causes the tessellation to converge toward a centroidal Voronoi tessellation (CVT) — a configuration where every site sits exactly at its own cell's centre of mass, producing cells that are more uniform in size and closer to regular hexagons.

How to Use

• Drag the Point Count slider (10–150) to change the number of random sites; click Randomize Points to generate a fresh set at any time (this also resets the iteration count).
• Set Iterations / Click and press Run Lloyd's Relaxation to perform that many centroid-relaxation steps at once.
• Toggle Auto-relax to continuously run one relaxation step per animation frame and watch the cells settle live; toggle it off at any time.
• Enable Show Delaunay triangulation overlay to draw the dual graph: a line is drawn between two sites whenever their cells share a raster boundary, revealing the Delaunay triangulation that is mathematically dual to the Voronoi diagram.
• Watch the Uniformity statistic — the coefficient of variation of cell areas — trend toward zero as more relaxation iterations run, indicating the cells are becoming more equal in size.

Did You Know?

Lloyd's relaxation has real applications far beyond pretty patterns. In computer graphics and finite-element meshing it is used to generate well-shaped triangular or polygonal meshes with fewer slivers and more uniform element sizes, which improves numerical stability. In image processing, weighted Voronoi stippling (popularised by Adrian Secord in 2002) uses Lloyd's relaxation to scatter stipple dots so that denser regions of an image get more dots while every dot ends up evenly spaced from its neighbours, mimicking the look of hand-drawn pointillist art. Perhaps most surprisingly, Stuart Lloyd described essentially the same iterative scheme — assign points to the nearest centre, recompute each centre as the mean of its assigned points, repeat — for both continuous Voronoi relaxation and for what became known as the k-means clustering algorithm, in a 1957 Bell Labs technical report on pulse-code modulation quantisation (not widely published until 1982). Voronoi relaxation and k-means are, at their core, the same algorithm applied to different kinds of data.

About this simulation

This simulator computes Voronoi diagrams by rasterising the canvas and, for every sample, brute-force searching for the nearest of up to 150 random sites. Pressing Run Lloyd's Relaxation moves every site to the true centroid of the raster samples currently assigned to it — a genuine implementation of Lloyd's algorithm — and repeating this drives the layout toward a centroidal Voronoi tessellation with more uniform, hexagon-like cells.

Frequently asked questions