About Delaunay Triangulation & Voronoi Diagram
This simulation demonstrates Delaunay triangulation, a method of connecting a set of points into non-overlapping triangles such that no point lies inside the circumcircle of any triangle. The construction is performed using the Bowyer-Watson incremental algorithm, which inserts each point one at a time and repairs the triangulation by removing and re-connecting any triangles whose circumcircles contain the new point. You can add, drag, and remove points interactively while watching the mesh update in real time, and optionally reveal the Voronoi diagram — the geometric dual of the Delaunay triangulation.
Delaunay triangulation was introduced by Boris Delaunay in 1934 and is now a cornerstone of computational geometry, used in mesh generation for finite-element analysis, terrain modelling, computer graphics, robot path planning, and geographic information systems.
Frequently Asked Questions
What is the Delaunay triangulation?
The Delaunay triangulation of a point set is the unique triangulation (for points in general position) in which the circumcircle of every triangle contains no other point from the set in its interior. This "empty circumcircle" property ensures that the triangulation maximises the minimum angle across all triangles, producing the "most equilateral" possible mesh for a given point set.
How do I interact with this simulation?
Click anywhere on the canvas to add a new point and watch the triangulation rebuild instantly. Drag existing points to reshape the mesh dynamically. Right-click a point to remove it. Use the Controls panel to switch between random, grid, and circle point layouts, toggle the Voronoi dual overlay, show circumcircles on hover, highlight the convex hull, and colour-shade individual triangles. The "Animate construction" button replays the Bowyer-Watson insertion sequence step by step.
What does the "empty circumcircle" property mean and why does it matter?
Every triangle in a Delaunay triangulation has a unique circumscribed circle (circumcircle) passing through its three vertices. The Delaunay condition requires that no other input point falls strictly inside that circle. Enable "Circumcircle on hover" and move the mouse over triangles to verify this: the overlay reports "Empty circumcircle checkmark" when the condition holds. This property directly implies that the minimum angle in the triangulation is as large as possible, which makes numerical computations on the mesh more stable and accurate.
How does the Bowyer-Watson algorithm work?
The Bowyer-Watson algorithm inserts points one at a time into an existing triangulation. It starts with a large "super-triangle" that contains all input points. For each new point it finds every triangle whose circumcircle contains the point (the "bad" triangles), removes them to form a star-shaped polygonal cavity, then connects the new point to every edge of that cavity to create new triangles. Finally, all triangles sharing a vertex with the super-triangle are discarded. The algorithm runs in O(n log n) expected time for random point sets and O(n^2) in the worst case.
What is the Voronoi diagram and how is it related to Delaunay triangulation?
The Voronoi diagram partitions the plane into regions, one per input point, where each region contains all locations closer to that point than to any other. The Delaunay triangulation and the Voronoi diagram are geometric duals: the circumcentre of each Delaunay triangle becomes a Voronoi vertex, and connecting circumcentres of adjacent triangles (triangles sharing an edge) traces out Voronoi edges. Toggle "Voronoi diagram" in the simulation to overlay both structures simultaneously and observe how each Voronoi vertex sits exactly at the circumcentre of a Delaunay triangle.
Where is Delaunay triangulation used in the real world?
Delaunay triangulation underpins finite-element mesh generation in structural and fluid-dynamics simulations, where well-shaped triangles improve solver accuracy. It is used in geographic information systems to build triangulated irregular networks (TINs) for terrain elevation models. Computer graphics pipelines use it for surface reconstruction from point clouds, alpha shapes, and texture atlasing. Wireless and mobile network planning use Voronoi cells (the dual) to model coverage areas and handover boundaries between base stations.
Does the Delaunay triangulation always produce a unique result?
For points in "general position" — meaning no four points are exactly cocircular — the Delaunay triangulation is unique. When four or more points lie on a common circle (a degenerate configuration), there is no strict preference between two valid triangulations, so the result depends on tie-breaking rules. The simulation handles this by applying a tiny jitter to point coordinates during the Bowyer-Watson computation, ensuring a consistent result even for symmetric layouts such as regular grids or circles.
Who discovered Delaunay triangulation and when?
The triangulation is named after Boris Nikolaevich Delaunay (also transliterated as Delone), a Soviet mathematician who formally defined and proved the construction in his 1934 paper "Sur la sphere vide." Georgy Voronoi had already described the dual diagram in 1908. The Bowyer-Watson incremental algorithm, which this simulation implements, was independently discovered by Adrian Bowyer and David Watson in 1981, making the method efficient enough for practical interactive use.
What are related computational geometry structures?
Closely related structures include the convex hull (the outer boundary of the Delaunay triangulation, shown by enabling "Convex hull" in this simulation), the Gabriel graph (a subgraph of Delaunay edges where the diametral circle of each edge is empty), and the minimum spanning tree (always a subgraph of the Delaunay triangulation). In higher dimensions, the Delaunay triangulation generalises to Delaunay tetrahedralisation in 3D, essential for volumetric mesh generation in computational engineering.
How is Delaunay triangulation used in engineering and technology?
In finite-element analysis (FEA), poorly shaped triangles with very small angles cause ill-conditioned stiffness matrices and numerical instability; Delaunay meshing followed by refinement algorithms such as Ruppert's algorithm guarantees a minimum angle bound (typically above 20 degrees) across the mesh. In computer vision, Delaunay triangulation of facial landmark points produces a mesh used for face warping, morphing, and augmented reality filters. Geospatial software like QGIS and ArcGIS use it to interpolate elevation data and generate contour lines from scattered survey measurements.
What are current research directions in Delaunay triangulation?
Active research includes parallel and GPU-accelerated Delaunay construction for very large point sets (billions of points in scientific simulations), dynamic Delaunay structures that support efficient point insertions and deletions in streaming or moving-point scenarios, and anisotropic meshing where triangle shapes adapt to directionality in the underlying domain (such as boundary layers in fluid dynamics). There is also ongoing work on weighted Delaunay triangulations (power diagrams) and their applications in optimal transport and machine learning geometry.