Delaunay Triangulation Generator

The Delaunay Triangulation Generator turns any set of 2D points into the unique triangulation that maximizes the smallest interior angle — the gold standard for terrain modeling, finite-element meshing, nearest-neighbor interpolation, and computational geometry classrooms. Paste coordinates (or pick a quick-start pattern), and the tool runs the Bowyer-Watson algorithm server-side, colors each triangle by its quality, and shows the empty-circumcircle property, the convex hull, and the Voronoi dual on demand.

How to Read the Generated Mesh

What Makes This Delaunay Triangulator Different

What Is a Delaunay Triangulation?

Given a set of 2D points, there are usually many ways to connect them into a triangulation (a complete tiling of their convex hull by triangles with no overlaps or gaps). The Delaunay triangulation, named after Russian mathematician Boris Delaunay (1934), is the one that satisfies the empty-circumcircle property: for every triangle in the mesh, the circle that passes through its three vertices contains no other input points. This single property has a remarkable consequence: among all triangulations of the same point set, the Delaunay one maximizes the smallest interior angle. In plain English, it produces the most "fat" and "balanced" triangles possible.

How the Bowyer-Watson Algorithm Works

1. Surround all input points with a very large super-triangle.
2. Insert one input point at a time. For each new point, find every existing triangle whose circumcircle contains the new point — these are the "bad" triangles.
3. Remove the bad triangles. The hole they leave behind has a polygonal boundary.
4. Connect the new point to every edge of that boundary, forming new triangles.
5. After all points are inserted, remove any triangle still touching a super-triangle vertex. What remains is the Delaunay triangulation of the original point set.

Where the Delaunay Triangulation Is Used

• Terrain modeling (GIS): elevation samples (typically irregularly spaced, like terrain stations) are connected into a Triangulated Irregular Network (TIN) for elevation queries, shading, and 3D visualization.
• Finite-element analysis: well-shaped Delaunay triangles yield stable numerical solutions for partial differential equations in mechanics, heat transfer, and electromagnetics.
• Computer graphics: mesh generation for rendering, character rigging, and procedural terrain — Delaunay's "no skinny triangles" guarantee avoids texture stretching artifacts.
• Natural-neighbor interpolation: smooth surfaces are reconstructed from scattered samples by computing each query point's natural neighbors via the Voronoi dual.
• Computational geometry classes: a canonical algorithm with deep connections to convex hulls, Voronoi diagrams, point location, and divide-and-conquer.
• 3D printing slicers and CNC tool-paths: 2D Delaunay (and its 3D cousin, the Delaunay tetrahedralization) underlies many slicing and infill strategies.

Delaunay vs Voronoi: Two Sides of the Same Coin

The Voronoi diagram partitions the plane into one cell per input point, where each cell contains everything closer to its point than to any other. Connect the points whose cells share a boundary, and you get exactly the Delaunay triangulation. Conversely, the circumcenters of adjacent Delaunay triangles, joined by line segments, form the Voronoi edges. Toggle "Voronoi dual" on this tool to see the orange dashed lines overlaid on the same chart — every Delaunay edge crosses exactly one Voronoi edge at right angles.

Quality, Skinny Triangles, and Mesh Refinement

Delaunay maximizes the global minimum interior angle, but it cannot fix a fundamentally bad point distribution. If your input points are nearly collinear, clustered, or leave large empty regions, some triangles will still be skinny (minimum angle below 20°). The fix is Steiner-point insertion: algorithms like Ruppert's algorithm and Chew's second algorithm iteratively add new points at the circumcenter of skinny triangles, retriangulating each time, until every triangle meets a target quality bound. This generator shows you which triangles are skinny so you know where to add Steiner points if you want a finer mesh.

Worked Example

Click the "Circle + hub" preset. The tool places 18 points around a circle and 1 point at the center, and triangulates them. The result is a perfect fan of 18 isoceles triangles meeting at the hub — each one has angles of 10° at the rim and 80°–80° at the hub. The worst minimum angle is 10°, all triangles are flagged as skinny, and the histogram shows everything in the 0°–10° bin. The example is a great teaching case: even the Delaunay-optimal triangulation can have skinny triangles when the input forces them. Now click "Random cloud" — the same algorithm produces well-shaped triangles because the points are spread evenly, and the histogram shifts to the right.

Common Misconceptions

• "Delaunay triangulation is unique": usually yes, but if four input points are co-circular (all lie on the same circle), there are two valid Delaunay triangulations of that group. The generator picks one consistently.
• "More points always mean better quality": adding poorly-placed points can introduce new skinny triangles. Steiner-point algorithms place new points carefully — at circumcenters — so quality is guaranteed to improve.
• "Delaunay is the same as a convex hull": no. The convex hull is the outer boundary; the Delaunay triangulation fills in the interior with triangles.
• "All triangulations look about the same": the difference is dramatic. A "flip away" from a Delaunay edge can turn a 25° triangle into a 5° one. The tool's quality heatmap makes the difference visible.

Frequently Asked Questions