Delaunay triangulation of points
Triangles joining a set of points so no point sits inside any triangle's circumcircle: planar on a local map for a regional set, or on the sphere for a global one.
The points make 4 triangles on the planar surface.
| First | Second | Third |
|---|---|---|
| 3 | 5 | 4 |
| 4 | 5 | 1 |
| 1 | 5 | 2 |
| 2 | 5 | 3 |
- Surface
Provenance
- Computed by
- geometry.mesh.delaunay 1.0.0, core 0.1.0
- Model
- Planar: the lower convex hull of the points lifted to z = x² + y² on an azimuthal equidistant plane at their center. Spherical: the convex hull of their directions on the unit sphere. Both by incremental insertion, with a fixed jitter far below a millimeter to settle ties
- Accuracy
- Exact triangulation of the points on the chosen surface; where four points share a circle, either diagonal is valid and one is chosen consistently
- Notes
- None
- Cites
- de Berg, M., Cheong, O., van Kreveld, M., and Overmars, M., Springer, Computational Geometry: Algorithms and Applications
Something look off?
How we got thisFormula, worked example, sources, and proof
Model: Planar: the lower convex hull of the points lifted to z = x² + y² on an azimuthal equidistant plane at their center. Spherical: the convex hull of their directions on the unit sphere. Both by incremental insertion, with a fixed jitter far below a millimeter to settle ties
Show your work
Surface
planar within 1,000 km of the center, else the sphere5 points= planarTriangles
faces of the convex hull (the lower hull of the lifted points on the plane)5 points= 4
The same steps an agent gets from the MCP server with explain: true.
Accuracy: Exact triangulation of the points on the chosen surface; where four points share a circle, either diagonal is valid and one is chosen consistently
When to use this: Use this to turn scattered points into a surface. A triangulation is what interpolation between measurements runs on — a terrain model from spot heights, a field from soundings or samples, contours from a survey — and it is also the skeleton the Voronoi cells are built from, so the two answer opposite halves of the same question. Take the spherical surface when the points spread far enough that a plane would distort them; planar is right for a site, a field, or a survey block.
Limitations: It triangulates the convex hull of the points and nothing beyond it, so a concave boundary is filled in: an L-shaped site comes back with triangles spanning the notch, and they have to be clipped afterwards. Where four or more points share a circle the triangulation is genuinely not unique and either diagonal is correct; one is chosen consistently, but two implementations can differ there and neither is wrong. The result is a mesh over the points given and interpolating on it is only as good as they are — it says nothing about what happens between them beyond a straight line.
Worked example: Five survey points. Source: de Berg et al. (2008), the lifting map. Checked against GEOS 3.11.4's own delaunay_triangles over fifteen point sets — scatters, jittered grids, rings, two clusters, and sets at the equator, at 70 north and across the antimeridian — agreeing triangle for triangle on every one, which a unique triangulation permits demanding.
You enter
- Points
- 40, -105 40.01, -104.99 40, -104.98 39.99, -104.992 40.004, -104.995
You get
- Triangles
- 4
- Surface
- planar
Review: Not yet independently reviewed by a GIS professional.
Last verified: 2026-09-22, when a maintainer last confirmed this tool's sources at the issuer. See the sources ledger.
Status: version 1.0.0, core 0.1.0. See this tool in the verification report.
Checked against: 20 golden test vectors (download the test vectors, each with its source and tolerance). See how results are checked and every source.
Sources
- Computational Geometry: Algorithms and Applications, de Berg, M., Cheong, O., van Kreveld, M., and Overmars, M., Springer, 3rd edition. Chapter 9 (Delaunay triangulations) and 11.5 (the lifting map and convex hulls).