aldus.nexus

Voronoi city

Picking a city

Every seed claims the streets closest to it. Fortune's sweep line draws the borders one event at a time, and the Delaunay triangles come free.

Loading
Reading the list of city maps.

Tap or click to add a seed, drag one to move it, double-tap to remove it. Hover (or drag a finger) over a triangle to test its empty circle.

The numbers

events processed over the sweep
beach line arcs over the sweep
cell areaskm²
neighbours per cellinner cells

How it works

Cells and triangles

Drop some seeds on a map and give every point to the seed nearest to it. The regions you get are Voronoi cells: each one is convex, its borders are the perpendicular bisectors between neighbouring seeds, and three borders meet at a vertex that is equally far from three seeds. Join every pair of seeds whose cells touch and you get the Delaunay triangulation, the same picture turned inside out: every Voronoi vertex is the centre of one Delaunay triangle's circumcircle, and that circle has no other seed inside it (hover a triangle to check). It is the triangulation that avoids thin slivers, which is why meshes and terrain models use it. K-means draws exactly these cells around its centroids every iteration: see k-means.

Fortune's sweep

Steven Fortune's 1986 trick is to slide a line down the map. Above the line, the diagram is already settled, because nothing below the line can be nearer to those points than the line itself. The boundary of the settled part is the beach line, a chain of parabolic arcs, one per seed: each arc is the set of points equally far from its seed and the sweep line. Where two arcs meet, the breakpoint slides along the Voronoi edge between their seeds, drawing it as the line moves.

Only two things ever change the beach line. A site event happens when the sweep reaches a new seed: a needle-thin arc pops up and splits the arc above it, starting a new edge in both directions. A circle event happens when an arc shrinks to nothing between its two neighbours. At that moment its two breakpoints meet at a point equally far from three seeds and from the sweep line, so the circle through those three seeds touches the sweep at its lowest point and has nothing inside it: that point is a Voronoi vertex. The event is queued at the bottom of the circle as soon as three arcs line up, and cancelled (a false alarm, flashed red) if a new seed lands under the arc first.

There are n site events and at most 2n - 5 circle events, each handled in O(log n) with a balanced tree for the beach line and a heap for the queue, so the whole diagram costs O(n log n), as good as sorting. This page keeps the beach line as a simple list (it rarely holds more than a few dozen arcs) and records it after every event so you can scrub back and forth. Ties are handled on purpose: duplicate seeds merge, a first row of seeds at the same height gets vertical edges, a seed landing exactly under a breakpoint makes a vertex at once, and collinear seeds never queue a circle. Try the grid, the ring and the line.

Streets and settling

Cells are drawn as the crow flies, but the streets underneath say otherwise. Switch the streets to "by street" and one Dijkstra run from every seed at once (the multi-source version of shortest path, and the flow fields of the pathfinding playground) gives each junction to the seed it can reach soonest along the roads; "where they differ" lights up the streets where the two answers disagree, behind rivers, railways and one-road valleys. The crow-flies owner of each junction comes from walking downhill on the Delaunay graph, which always ends at the nearest seed. Relax runs Lloyd's algorithm: move every seed to the centroid of its cell and redraw. The cells even out into a honeycomb, a centroidal Voronoi tessellation, and the area chart narrows. With the streets on, isochrones are the same idea measured in minutes.

One line sweeping down a map turns a sort into a whole geometry: borders, corners, triangles and circles, each found exactly once.

V(sᵢ) = { p : |p - sᵢ| ≤ |p - sⱼ| for every j }the Voronoi cell of seed sᵢ
y = ((x - a)² + b² - L²) / (2(b - L))the beach line arc of a seed at (a, b) when the sweep line is at y = L (y measured down the map): every point on it is as far from the seed as from the line
L = yₒ + ra circle event fires when the sweep reaches the bottom of the circle through three neighbouring seeds; its centre (xₒ, yₒ) is the Voronoi vertex
triangles = 2n - 2 - h, edges = 3n - 3 - hEuler's formula for n seeds with h on the convex hull, so on average a cell has just under six neighbours
sᵢ ← (1 / |Vᵢ|) ∫ over Vᵢ of p dAone step of Lloyd relaxation: every seed moves to the centroid of its cell
O(n log n)n site events, at most 2n - 5 circle events, each a log n insert or delete