What is a Delaunay triangulation?
A Delaunay triangulation joins a set of points into triangles with one special rule: the circle through the three corners of any triangle — its circumcircle — contains no other point. Named after Boris Delaunay, who described it in 1934, it is the triangulation that makes the smallest angles as large as possible, so the triangles are as "fat" as the points allow.
How to use this generator
- Click to place points, or start from random points, a grid or a circle.
- Drag points around and watch the triangles flip as the empty-circle rule is restored.
- Hover any triangle to highlight it and its circumcircle; no point will ever be inside.
- Turn on the Voronoi diagram to see the dual structure: every Voronoi corner is a circumcircle center.
Delaunay triangulation vs. Voronoi diagram
The two structures carry the same information. A Delaunay edge links two points whose Voronoi cells touch; each Delaunay triangle corresponds to one Voronoi vertex at its circumcenter; and the convex hull of the points marks the cells that are open to infinity. That is why most software — including every tool in this set — computes the Delaunay triangulation first and derives the Voronoi diagram from it.
Grid and circle presets show a special case: when four or more points lie on one circle, several triangulations satisfy the rule equally well, and the one shown depends on tiny rounding differences.
See how the diagram is built step by step in the Voronoi simulation, or make the points evenly spaced with Lloyd relaxation.
Frequently asked questions
What is a Delaunay triangulation?
It connects a set of points into triangles so that no point lies inside the circumcircle of any triangle. Among all triangulations of the points it maximizes the smallest angle, so it avoids thin sliver triangles.
How is it related to the Voronoi diagram?
They are duals. Two points are joined by a Delaunay edge exactly when their Voronoi cells share a border, and the center of each triangle's circumcircle is a corner of the Voronoi diagram. Turn on both layers to see it.
How many triangles will I get?
For n points with h of them on the convex hull, a Delaunay triangulation has 2n − 2 − h triangles and 3n − 3 − h edges, provided the points are not all on one line.
Where is Delaunay triangulation used?
Terrain models (TINs), finite element meshes, interpolation of scattered measurements, computer graphics, path planning and low-poly art.