Delaunay Triangulation

Draft: written, not yet checked by a person Operation · delaunay-triangulation

Triangles joining a set of points so that no point falls inside any triangle's circumcircle.

Pitfall. Some functions triangulate the vertices of each geometry on its own; collect the points into one geometry first for one triangulation of the whole layer.

Pitfall. Four or more points on one circle have more than one valid triangulation, so engines can return different triangles covering the same area.

Pitfall. Triangles in a geographic CRS are built in degrees.

About this operation
Also called	Delaunay triangles, TIN, Create TIN, triangulated irregular network, triangulation
Group	`vector/geometry`
Checks	`geometry.valid`
Pitfalls	3 listed above
Columbus tool	Not stated
Notes	Not stated
Status	active
Broader	Not stated
Narrower	Not stated
Related	`voronoi` `convex-hull`

Parameters

Name	Type	Required	Default	Values	Note
`tolerance`	length	no	`0`	Not stated	Points closer together than this (in the CRS's units) are snapped together first.

Inputs and outputs

Direction	Name	Type	Geometry	Note
Input	`layer`	vector	point	Not stated
Output	`output`	vector	polygon	Not stated

In each engine

Engine	Tool	Parameters	Differences
`apache-sedona`	`sedona.sql.ST_DelaunayTriangles`	`tolerance` → `tolerance` `layer` → `geometry`	Triangulates the vertices of one geometry: collect the points first (ST_Union_Aggr or ST_Collect). A Spark SQL function: arguments are columns or column names, run over a Spark DataFrame.
`geopandas`	`geopandas.GeoSeries.delaunay_triangles`	`tolerance` → `tolerance`	Called on a GeoSeries; triangulates the vertices of all its geometries together and returns one triangle per row.
`grass`	`v.delaunay`	`tolerance` always 0 `layer` → `input` `output` → `output`	Limited to the current computational region (flag r); flag l outputs the edges as lines.
`postgis`	`st_delaunaytriangles`	`tolerance` → `#2` `layer` → `#1`	Triangulates the vertices of one geometry: ST_Collect the points first for one triangulation of the layer. Returns a GeometryCollection of triangles (flags 0); flags 1 returns the edges, 2 a TIN.
`qgis`	`native:delaunaytriangulation`	`tolerance` → `TOLERANCE` `layer` → `INPUT` `output` → `OUTPUT`	ADD_ATTRIBUTES copies the point ids onto each triangle (on by default).
`sf`	`sf::st_triangulate`	`tolerance` → `dTolerance` `layer` → `x`	Triangulates the vertices of each geometry on its own: combine the points first (st_union or st_combine) for one triangulation. Returns a GEOMETRYCOLLECTION of triangles per geometry; bOnlyEdges returns the edges.
`shapely`	`shapely.delaunay_triangles`	`tolerance` → `tolerance` `layer` → `geometry`	Triangulates the vertices of each geometry on its own: pass one MultiPoint (shapely.union_all of the points) for one triangulation. Returns a GeometryCollection of triangles; only_edges returns the edges as lines.
`terra`	`terra::delaunay`	`tolerance` → `tolerance` `layer` → `x`	as.lines returns the edges; constrained keeps polygon edges as triangle edges.
`turf-js`	`turf.tin`	`tolerance` always 0 `layer` → `points`	z names a property whose values become the triangles' a, b and c properties. Turf works on GeoJSON in longitude/latitude (WGS 84); data in another CRS must be reprojected first.