Triangulating a point set
A triangulation connects a set of points into triangles that cover their convex hull. Many triangulations exist, but the Delaunay triangulation is special and is the dual of the Voronoi diagram.
The empty circle property
The defining rule is the empty circumcircle condition. For every triangle, the circle passing through its three vertices contains no other point inside it.
- This forbids skinny, awkward triangles where possible.
- It is verified with an in circle orientation test.
Why it is preferred
Among all triangulations of the points, the Delaunay one maximizes the smallest angle. Fat, well shaped triangles are exactly what numerical methods and interpolation want, which is why it dominates meshing.
- It produces the nicest mesh for finite element work.
- It connects each point to its natural neighbors.
Building it
The edge flip approach starts from any triangulation and repeatedly flips an edge whenever the in circle test fails for the two triangles sharing it, converging to the Delaunay result. Incremental insertion and the Voronoi dual are alternatives.
Key idea
The Delaunay triangulation keeps every triangle circumcircle empty of other points, which maximizes the smallest angle and yields the fattest, most numerically friendly mesh, often built by flipping illegal edges.