Delaunay Triangulation
Click to place points and watch the Delaunay triangulation form in real time. Toggle the dual Voronoi diagram, inspect circumcircles, and step through the Bowyer-Watson algorithm to see how it works.
About this lab
What is Delaunay triangulation?
Given a set of points in the plane, a Delaunay triangulation connects them into triangles such that no point lies inside the circumcircle of any triangle. This is equivalent to maximizing the minimum angle across all triangles — the resulting mesh avoids skinny, degenerate triangles whenever possible. For points in “general position” (no four points cocircular), the Delaunay triangulation is unique.
The empty circle property
The defining property of a Delaunay triangulation is the empty circumcircle condition: for every triangle in the mesh, the circle passing through its three vertices contains no other point in its interior. Hover over triangles in the canvas above to inspect their circumcircles and verify this property visually. When you add a point inside a circumcircle, the triangulation must be updated — the affected triangles are “bad” and must be removed and replaced.
Bowyer-Watson algorithm
This lab implements the Bowyer-Watson algorithm for incremental Delaunay triangulation. The algorithm starts with a “super-triangle” large enough to contain all points. For each new point:
1. Find all triangles whose circumcircle contains the new point 2. Remove those "bad" triangles, leaving a polygonal hole 3. Connect the new point to each edge of the hole 4. After all points are inserted, remove triangles sharing vertices with the super-triangle
The expected time complexity is O(n log n) for randomly distributed points,
though the worst case is O(n²). Use the “Step-by-step” button
to watch each phase of the algorithm unfold.
Voronoi duality
Every Delaunay triangulation has a dual structure called the Voronoi diagram. The Voronoi diagram partitions the plane into cells, one per point, where each cell contains all locations closer to that point than to any other. The duality is elegant: Delaunay vertices become Voronoi cells, Delaunay edges become Voronoi edges, and Voronoi vertices are the circumcenters of Delaunay triangles. Toggle the Voronoi overlay (shown in gold) to see both structures simultaneously.
Applications
Delaunay triangulation is fundamental to computational geometry and has wide applications: mesh generation for finite element methods (FEM) in engineering simulation; terrain modeling from scattered elevation data (TINs); nearest-neighbor queries through the Voronoi dual; path planning in robotics and game AI; and natural neighbor interpolation for scattered data. The Voronoi diagram alone appears in ecology (animal territories), crystallography (Wigner-Seitz cells), and network design (optimal facility placement).