Voronoi- und Delaunay-Spielwiese

An interactive playground for the two structures at the heart of computational geometry. Place points and watch the Voronoi diagram (which region of the plane is closest to which point) and the Delaunay triangulation (its dual graph) update as you move them.

Interaction: click empty space to add a point, drag a point to move it, Alt+click or right-click to delete one. On a touch screen, tap to add and long-press is not needed — dragging is reserved for scrolling the page. The generator offers random, jittered grid, circle, clustered and spiral layouts.

What the overlays mean

• Voronoi cells — every location inside a cell is closer to that cell's site than to any other. Cell walls are perpendicular bisectors between neighbouring sites; a corner is equidistant from three sites.
• Delaunay triangulation — two sites are joined when their cells share a wall. It maximises the smallest angle over all possible triangulations, which is why it is the default mesh for interpolation and finite elements: thin slivers are avoided where possible.
• Circumcircles — the defining property. A triangle belongs to the Delaunay triangulation exactly when its circumcircle contains no other site. The circumcentres are the Voronoi corners.
• Convex hull — the outer boundary of the Delaunay triangulation, and the smallest convex polygon containing every point.

Lloyd relaxation moves every site to the centroid of its own cell. Repeat it a few times and the point set turns into a centroidal Voronoi tessellation: cells become similar in size and roughly hexagonal. The cell area spread readout falls with each step, which is the numeric version of the same story. This is how blue-noise sample sets, stippling patterns and good meshes are generated.

Readouts: point, triangle, edge and hull-vertex counts, the smallest angle anywhere in the triangulation, the total edge length, and the mean, spread, minimum and maximum cell area. Areas are in the square units of the 600 × 400 canvas.

Algorithms: the triangulation is incremental Bowyer-Watson; each Voronoi cell is the view rectangle clipped by the perpendicular bisector against every other site. Both are quadratic in the number of points, which is fine up to the 250-point limit here — production libraries use Fortune's sweep or a divide-and-conquer method instead.

Limitations: cells are clipped to the canvas, so the unbounded outer cells appear finite. Near-degenerate input (four sites on a common circle, many collinear points) can make the triangulation flip between equally valid answers.