ST_DelaunayTriangles
Prev  7.14. Geometry Processing  Next

Name

ST_DelaunayTriangles — Returns the Delaunay triangulation of the vertices of a geometry.

Synopsis

geometry ST_DelaunayTriangles(geometry g1, float tolerance = 0.0, int4 flags = 0);

Description

Computes the Delaunay triangulation of the vertices of the input geometry. The optional tolerance can be used to snap nearby input vertices together, which improves robustness in some situations. The result geometry is bounded by the convex hull of the input vertices. The result geometry representation is determined by the flags code:

  • 0 - a GEOMETRYCOLLECTION of triangular POLYGONs (default)

  • 1 - a MULTILINESTRING of the edges of the triangulation

  • 2 - A TIN of the triangulation

Performed by the GEOS module.

Availability: 2.1.0

This function supports 3d and will not drop the z-index.

This function supports Triangles and Triangulated Irregular Network Surfaces (TIN).

Examples

Triangulation of the vertices of a polygon and a buffered point.

Code
WITH data AS (
  SELECT polygon, ST_Buffer(center, 20) AS point_buffer
  FROM (SELECT
    'POLYGON((175 150,20 40,50 60,125 100,175 150))'::geometry AS polygon,
    'POINT(110 170)'::geometry AS center
  ) AS input
)
SELECT ST_DelaunayTriangles(ST_Union(polygon, point_buffer)) AS triangles
FROM data;
Output
GEOMETRYCOLLECTION(POLYGON((96 184,93 181,96 156,96 184)), POLYGON((96 184,96 156,102 188,96 184)), POLYGON((96 184,102 188,99 187,96 184)), POLYGON((102 188,96 156,99 153,102 188)), POLYGON((102 188,99 153,102 152,102 188)), POLYGON((102 188,102 152,106 190,102 188)), POLYGON((106 190,102 152,106 150,106 190)), POLYGON((106 190,106 150,110 190,106 190)), POLYGON((110 190,106 150,110 150,110 190)), POLYGON((110 190,110 150,118 188,110 190)), POLYGON((110 190,118 188,114 190,110 190)), POLYGON((118 188,110 150,121 153,118 188)), POLYGON((118 188,121 153,121 187,118 188)), POLYGON((121 187,121 153,124 156,121 187)), POLYGON((121 187,124 156,124 184,121 187)), POLYGON((121 187,124 184,175 150,121 187)), POLYGON((175 150,124 184,127 181,175 150)), POLYGON((175 150,127 181,128 178,175 150)), POLYGON((175 150,128 178,130 174,175 150)), POLYGON((175 150,130 174,130 170,175 150)), POLYGON((175 150,130 170,130 166,175 150)), POLYGON((175 150,130 166,128 162,175 150)), POLYGON((175 150,128 162,127 159,175 150)), POLYGON((175 150,127 159,124 156,175 150)), POLYGON((175 150,124 156,125 100,175 150)), POLYGON((125 100,124 156,121 153,125 100)), POLYGON((125 100,121 153,118 152,125 100)), POLYGON((125 100,118 152,114 150,125 100)), POLYGON((125 100,114 150,110 150,125 100)), POLYGON((125 100,110 150,106 150,125 100)), POLYGON((125 100,106 150,102 152,125 100)), POLYGON((125 100,102 152,99 153,125 100)), POLYGON((125 100,99 153,50 60,125 100)), POLYGON((125 100,50 60,20 40,125 100)), POLYGON((20 40,50 60,90 166,20 40)), POLYGON((20 40,90 166,90 170,20 40)), POLYGON((20 40,90 170,90 174,20 40)), POLYGON((20 40,90 174,92 178,20 40)), POLYGON((92 178,90 174,90 170,92 178)), POLYGON((92 178,90 170,92 162,92 178)), POLYGON((92 178,92 162,93 159,92 178)), POLYGON((92 178,93 159,93 181,92 178)), POLYGON((93 181,93 159,96 156,93 181)), POLYGON((96 156,93 159,50 60,96 156)), POLYGON((96 156,50 60,99 153,96 156)), POLYGON((50 60,93 159,92 162,50 60)), POLYGON((50 60,92 162,90 166,50 60)), POLYGON((90 166,92 162,90 170,90 166)), POLYGON((110 150,114 150,121 153,110 150)), POLYGON((121 153,114 150,118 152,121 153)), POLYGON((124 156,127 159,130 166,124 156)), POLYGON((124 156,130 166,128 178,124 156)), POLYGON((124 156,128 178,124 184,124 156)), POLYGON((124 184,128 178,127 181,124 184)), POLYGON((128 178,130 166,130 170,128 178)), POLYGON((128 178,130 170,130 174,128 178)), POLYGON((130 166,127 159,128 162,130 166)))
Figure
Geometry figure for visual-st-delaunaytriangles-01

Triangulation edges returned as a MULTILINESTRING.

Code
WITH data AS (
  SELECT polygon, ST_Buffer(center, 20) AS point_buffer
  FROM (SELECT
    'POLYGON((175 150,20 40,50 60,125 100,175 150))'::geometry AS polygon,
    'POINT(110 170)'::geometry AS center
  ) AS input
)
SELECT ST_DelaunayTriangles(ST_Union(polygon, point_buffer), 0.001, 1) AS triangulation_edges
FROM data;
Output
MULTILINESTRING((121 187,175 150),(118 188,121 187),(114 190,118 188),(110 190,114 190),(106 190,110 190),(102 188,106 190),(99 187,102 188),(96 184,99 187),(93 181,96 184),(92 178,93 181),(20 40,92 178),(20 40,125 100),(125 100,175 150),(124 156,125 100),(124 156,175 150),(124 156,127 159),(127 159,175 150),(127 159,128 162),(128 162,175 150),(128 162,130 166),(130 166,175 150),(130 166,130 170),(130 170,175 150),(130 174,130 170),(130 174,175 150),(128 178,130 174),(128 178,175 150),(127 181,128 178),(127 181,175 150),(124 184,127 181),(124 184,175 150),(121 187,124 184),(124 156,124 184),(121 187,124 156),(121 153,124 156),(121 153,121 187),(118 188,121 153),(110 150,121 153),(110 150,118 188),(110 150,110 190),(110 190,118 188),(106 150,110 150),(106 150,110 190),(106 190,106 150),(102 152,106 150),(102 152,106 190),(102 152,102 188),(99 153,102 152),(99 153,102 188),(96 156,99 153),(96 156,102 188),(96 156,96 184),(96 184,102 188),(93 181,96 156),(93 159,96 156),(93 159,93 181),(92 178,93 159),(92 162,93 159),(92 162,92 178),(90 170,92 162),(90 170,92 178),(90 170,90 174),(90 174,92 178),(20 40,90 174),(20 40,90 170),(90 170,90 166),(20 40,90 166),(50 60,90 166),(20 40,50 60),(50 60,125 100),(50 60,99 153),(99 153,125 100),(50 60,96 156),(50 60,93 159),(50 60,92 162),(90 166,92 162),(102 152,125 100),(106 150,125 100),(110 150,125 100),(110 150,114 150),(114 150,125 100),(114 150,118 152),(118 152,125 100),(118 152,121 153),(121 153,125 100),(114 150,121 153),(124 184,128 178),(124 156,128 178),(128 178,130 166),(124 156,130 166),(127 159,130 166),(128 178,130 170))
Figure
Geometry figure for visual-st-delaunaytriangles-02

Triangulation of 42 points forming an L shape.

Code
WITH data AS (
  SELECT 'MULTIPOINT(14 14,34 14,54 14,74 14,94 14,114 14,134 14,
    150 14,154 14,154 6,134 6,114 6,94 6,74 6,54 6,34 6,
    14 6,10 6,8 6,7 7,6 8,6 10,6 30,6 50,6 70,6 90,6 110,6 130,
    6 150,6 170,6 190,6 194,14 194,14 174,14 154,14 134,14 114,
    14 94,14 74,14 54,14 34,14 14)'::geometry AS l_shape_points
)
SELECT ST_DelaunayTriangles(l_shape_points) AS triangles
FROM data;
Output
GEOMETRYCOLLECTION(POLYGON((6 194,6 190,14 194,6 194)), POLYGON((14 194,6 190,14 174,14 194)), POLYGON((14 194,14 174,154 14,14 194)), POLYGON((154 14,14 174,14 154,154 14)), POLYGON((154 14,14 154,150 14,154 14)), POLYGON((154 14,150 14,154 6,154 14)), POLYGON((154 6,150 14,134 6,154 6)), POLYGON((134 6,150 14,134 14,134 6)), POLYGON((134 6,134 14,114 14,134 6)), POLYGON((134 6,114 14,114 6,134 6)), POLYGON((114 6,114 14,94 14,114 6)), POLYGON((114 6,94 14,94 6,114 6)), POLYGON((94 6,94 14,74 14,94 6)), POLYGON((94 6,74 14,74 6,94 6)), POLYGON((74 6,74 14,54 14,74 6)), POLYGON((74 6,54 14,54 6,74 6)), POLYGON((54 6,54 14,34 14,54 6)), POLYGON((54 6,34 14,34 6,54 6)), POLYGON((34 6,34 14,14 14,34 6)), POLYGON((34 6,14 14,14 6,34 6)), POLYGON((14 6,14 14,10 6,14 6)), POLYGON((10 6,14 14,6 10,10 6)), POLYGON((10 6,6 10,7 7,10 6)), POLYGON((10 6,7 7,8 6,10 6)), POLYGON((7 7,6 10,6 8,7 7)), POLYGON((6 10,14 14,6 30,6 10)), POLYGON((6 30,14 14,14 34,6 30)), POLYGON((6 30,14 34,6 50,6 30)), POLYGON((6 50,14 34,14 54,6 50)), POLYGON((6 50,14 54,6 70,6 50)), POLYGON((6 70,14 54,14 74,6 70)), POLYGON((6 70,14 74,6 90,6 70)), POLYGON((6 90,14 74,14 94,6 90)), POLYGON((6 90,14 94,6 110,6 90)), POLYGON((6 110,14 94,14 114,6 110)), POLYGON((6 110,14 114,6 130,6 110)), POLYGON((6 130,14 114,14 134,6 130)), POLYGON((6 130,14 134,6 150,6 130)), POLYGON((6 150,14 134,14 154,6 150)), POLYGON((6 150,14 154,6 170,6 150)), POLYGON((6 170,14 154,14 174,6 170)), POLYGON((6 170,14 174,6 190,6 170)), POLYGON((14 154,14 134,150 14,14 154)), POLYGON((150 14,14 134,134 14,150 14)), POLYGON((134 14,14 134,114 14,134 14)), POLYGON((114 14,14 134,14 114,114 14)), POLYGON((114 14,14 114,94 14,114 14)), POLYGON((94 14,14 114,14 94,94 14)), POLYGON((94 14,14 94,74 14,94 14)), POLYGON((74 14,14 94,14 74,74 14)), POLYGON((74 14,14 74,54 14,74 14)), POLYGON((54 14,14 74,14 54,54 14)), POLYGON((54 14,14 54,34 14,54 14)), POLYGON((34 14,14 54,14 34,34 14)), POLYGON((34 14,14 34,14 14,34 14)))
Figure
Geometry figure for visual-st-delaunaytriangles-03

Example using vertices with Z values.

Code
SELECT ST_DelaunayTriangles(
  'MULTIPOINT Z(14 14 10,150 14 100,34 6 25,20 10 150)'::geometry);
Output
GEOMETRYCOLLECTION Z (POLYGON Z ((14 14 10,20 10 150,34 6 25,14 14 10)),POLYGON Z ((14 14 10,34 6 25,150 14 100,14 14 10)))