Voronoi Relaxation — Lloyd's Algorithm

March 2026

Start with random scattered points. Each frame, compute the Voronoi diagram — the partition of space where each cell contains all points closer to one seed than any other. Then find each cell's centroid and move its seed there. Repeat. What emerges from chaos is order: cells become more equal, more regular, more organic. This is Lloyd's algorithm, and it converges toward a beautiful centroidal Voronoi tessellation.

Live Demo

Number of Points 40

Relaxation Speed 0.15

Display Mode

Show Centroids Animate

Click "Randomize" to restart with new random points. Toggle "Show Centroids" to see where each point is moving.

What Is a Voronoi Diagram?

Given a set of seed points, the Voronoi diagram partitions the plane into cells. Each cell contains exactly those points that are closer to one seed than to any other. The boundaries between cells are equidistant from two seeds — they're perpendicular bisectors of the line connecting neighboring seeds.

function findCell(x, y, seeds) {
    let closest = 0;
    let minDist = distance(x, y, seeds[0]);
    for (let i = 1; i < seeds.length; i++) {
        let d = distance(x, y, seeds[i]);
        if (d < minDist) {
            minDist = d;
            closest = i;
        }
    }
    return closest;
}

For each pixel, we ask: "Which seed is closest?" That seed "owns" this pixel. The result is a mosaic of irregular polygons, each containing one seed.

Lloyd's Algorithm

Lloyd's algorithm is beautifully simple:

Start with seed points (randomly placed, in our case)
Compute the Voronoi diagram
Find the centroid (center of mass) of each cell
Move each seed toward its cell's centroid
Repeat until convergence

Each iteration makes cells more uniform. Over time, the seeds converge to a configuration where each seed is the centroid of its own cell — a "centroidal Voronoi tessellation."

Computing Centroids

For polygonal cells, we compute centroids using the shoelace formula for area:

function computeCentroid(polygon) {
    let area = 0;
    let cx = 0, cy = 0;
    let n = polygon.length;
    
    for (let i = 0; i < n; i++) {
        let j = (i + 1) % n;
        let cross = polygon[i].x * polygon[j].y - polygon[j].x * polygon[i].y;
        area += cross;
        cx += (polygon[i].x + polygon[j].x) * cross;
        cy += (polygon[i].y + polygon[j].y) * cross;
    }
    
    area /= 2;
    cx /= (6 * area);
    cy /= (6 * area);
    
    return {x: cx, y: cy};
}

This weighted average accounts for the cell's shape, giving us the true center of mass. The seed then moves toward this point.

Computing Voronoi Cells

For each seed, we compute its cell by intersecting half-planes. The cell is the intersection of all half-planes that are closer to this seed than to any other:

function computeCell(seed, allSeeds, bounds) {
    // Start with the bounding polygon (canvas bounds)
    let cell = [bounds];
    
    // Clip by each half-plane
    for (let other of allSeeds) {
        if (other === seed) continue;
        cell = clipByBisector(cell, seed, other);
        if (cell.length === 0) break; // Empty cell
    }
    
    return cell;
}

The clipping operation cuts the polygon by the perpendicular bisector between two seeds. Points on one side are closer to this seed; points on the other are closer to the other. We keep only the closer side.

The Relaxation Step

Once we have every cell's centroid, we move each seed partway toward it:

function relaxSeeds(seeds, centroids, speed) {
    for (let i = 0; i < seeds.length; i++) {
        let dx = centroids[i].x - seeds[i].x;
        let dy = centroids[i].y - seeds[i].y;
        seeds[i].x += dx * speed;
        seeds[i].y += dy * speed;
    }
}

The speed parameter controls how aggressively points move. Low speed (~0.1) creates smooth convergence. High speed (~0.8) reaches equilibrium faster but may overshoot.

Convergence

Under Lloyd's algorithm, the sum of squared distances from points to their cell centroids always decreases. This monotonic decrease guarantees convergence — the algorithm won't oscillate or diverge. Eventually, every seed becomes the centroid of its cell, and further iterations change nothing.

In practice, cells become more equal in area and more regular in shape. A random scatter of points transforms into something like a honeycomb — organic but ordered, irregular but balanced.

Applications

Centroidal Voronoi tessellations appear in many fields:

Data compression: k-means clustering is Lloyd's algorithm in discrete space
Mesh generation: creating optimal triangular/quadrilateral meshes for FEM
Sampling: distributing points evenly across a domain (blue noise)
Territory division: optimal placement of facilities to serve regions
Computer graphics: stippling, halftoning, and artistic rendering

The same algorithm underlies k-means clustering in machine learning — each iteration is one pass of Lloyd's algorithm, where "cells" are clusters in high-dimensional space rather than polygons in the plane.

nucleic.se