The idea: no point inside any circle

A set of points can be split into triangles in many ways. Some ways give long, thin slivers; others give fat triangles close to equilateral. The Delaunay triangulation is the one with a simple rule: draw the circle through the three corners of each triangle (its circumcircle), and no other point may lie inside any of those circles. This is the empty-circle rule.

Left: kite A, B, C, D split by the diagonal BC; the circle through A, B and C contains D, so BC is illegal. Right: the diagonal AD instead; the circles of ABD and ACD hold no other point.
Four points, two ways to cut them: only the cut whose circles stay empty is Delaunay.

When no four points lie on one circle, the Delaunay triangulation is unique. Among all triangulations of the points it has the largest smallest angle, so it avoids slivers. That is why meshes for simulations, terrain models and interpolation start from it.

The circle test

Is point d inside the circle through a, b and c? With a, b, c in counter-clockwise order, d is inside exactly when this determinant is positive:

| ax−dx  ay−dy  (ax−dx)²+(ay−dy)² |
| bx−dx  by−dy  (bx−dx)²+(by−dy)² |  > 0
| cx−dx  cy−dy  (cx−dx)²+(cy−dy)² |

It uses only multiplication and subtraction, so with whole-number coordinates it is exact. The page decides with this determinant and shows the same answer in a form you can check by eye: the distance from the point to the circle's centre O against the radius R.

Bowyer–Watson: insert, delete, re-connect

Bowyer–Watson adds the points one at a time and keeps the triangulation Delaunay after each one:

  1. Start with a super triangle X Y Z big enough to hold every point.
  2. For a new point P, find the triangle that contains it. Its circle certainly holds P.
  3. Walk to the neighbours across each edge and test their circles. A triangle whose circle holds P is bad, and the walk goes on through it. A triangle whose circle is empty stays, and the walk stops there.
  4. Delete the bad triangles. They form one connected hole (the cavity), and P can see every corner of it.
  5. Join P to every corner of the hole. The new triangles all have empty circles.
  6. After the last point, delete every triangle that uses X, Y or Z.
Three panels for inserting point I: five red circles hold I and their triangles are shaded; after deleting them an orange hole with 7 edges remains; I is joined to the 7 corners with blue edges.
Inserting the 9th point: 5 circles hold I, their triangles leave a 7-edge hole, and 7 new triangles fill it.

On the page's 9 points, most insertions delete 1 to 3 triangles. The last one, I at (13,2), deletes 5 and makes 7 (Demo: a big cavity). Watch the circle panel: each tested triangle is listed with |PO| and R, red when bad and green when empty (Demo: Bowyer-Watson on 9 points).

Counting triangles

A hole with k edges was made of k − 2 triangles, and it is refilled with k triangles. So every insertion adds exactly 2 triangles: 1, 3, 5, …, 19 with the super triangle after 9 points. Removing the 10 triangles that touch X, Y or Z leaves 9. In general a triangulation of n points with h of them on the convex hull has 2n − 2 − h triangles: here 2·9 − 2 − 7 = 9.

The work per insertion is the size of the hole, which is small on average. With the points inserted in random order and a fast way to find the containing triangle, Bowyer–Watson runs in O(n log n) expected time; a bad order can make it O(n²).

Edge flips

Two triangles that share an edge form a quadrilateral. If the far corner of one triangle lies inside the circle of the other, the shared edge is illegal. Flipping it swaps the quad's diagonal: the 4 corners stay, the other diagonal is used, and both new circles are empty of the opposite corner (Demo: one edge flip on 4 points).

Lawson's algorithm starts from any triangulation and flips illegal edges until none is left; the result is the Delaunay triangulation. The page starts from a sweep triangulation (points taken left to right, each joined to the hull edges it can see). It has a 6.0° sliver; 3 flips (BF → AC, DF → AI, DI → AG) give the same 9 triangles Bowyer–Watson built, with a smallest angle of 17.7° (Demo: Lawson flips from a sweep triangulation). Each flip makes the smallest angle of its quad larger, which is why the end result has the largest smallest angle.

MethodStarts fromFix stepOn the 9 points
Bowyer–Watsonsuper triangledelete bad triangles, join P to the hole48 circle tests, 9 triangles
Lawson flipsany triangulationflip an illegal edge3 flips, 9 triangles

Where it is used

Finite-element meshes, terrain models (TINs) built from survey points, interpolation of scattered data, and nearest-neighbour graphs all start from a Delaunay triangulation. Its dual, which joins the circumcentres of neighbouring triangles, is the Voronoi diagram: each region holds the places closest to one point. The same orientation test drives the convex hull, and the circumcentre is the point where the perpendicular bisectors meet in triangle centres. A GPU then fills such triangles pixel by pixel, as in rasterization.

The dual of this triangulation: see Voronoi Diagram.

What the page leaves out

The page uses whole-number points in general position: no four on one circle (then the triangulation is not unique) and no point on an edge. It finds the containing triangle by checking them all, where real code walks from the last triangle or keeps a point-location structure, and it inserts in a fixed order rather than a random one. A super triangle that is too small can lose hull edges; the page's one was checked against a brute-force search. Constrained Delaunay triangulations (forced edges), mesh refinement (Ruppert, Chew), 3D tetrahedra, divide and conquer, the sweep-line algorithm of Fortune and floating-point robustness are not shown.