Sketch · 2026-09-09
Delaunay, by Bowyer-Watson.
A Delaunay triangulation is the one triangulation of a point set in which no point sits inside the circumcircle of any triangle. Bowyer and Watson published the same incremental algorithm in 1981 in different journals: insert one point, delete every triangle whose circumcircle now contains it, retriangulate the hole. Repeat.
Click empty space to add a point. Drag a point to move it. Shift-click or right-click a point to remove it. On touch, tap to add, drag to move, and long-press to remove.
Note
The empty-circle property is the whole definition. Turn on the circumcircles and you can watch it hold: every circle drawn is empty of the other points. Any triangulation that fails this test is not Delaunay, and every triangulation that passes it is.
The Voronoi diagram is the geometric dual. Each Voronoi vertex is the circumcentre of a Delaunay triangle; each Voronoi edge connects the circumcentres of two triangles that share a Delaunay edge. Turn on the overlay and both structures fall into place at once.
The implementation here is the plain incremental form: seed with a super-triangle far larger than the point cloud, insert points one at a time, and strip the super-triangle out at the end. It runs in O(n²) in the worst case because bad-triangle discovery scans the whole triangle list on each insertion. That is fine for a few hundred points; production implementations swap in a spatial index or use Fortune's sweep for Voronoi directly.
Sources
Bowyer, A. (1981). Computing Dirichlet tessellations. The Computer Journal 24 (2): 162–166.
Watson, D. F. (1981). Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes. The Computer Journal 24 (2): 167–172.