ST_TriangulatePolygon
Prev  7.14. Geometry Processing  Next

Name

ST_TriangulatePolygon — Computes the constrained Delaunay triangulation of polygons

Synopsis

geometry ST_TriangulatePolygon(geometry geom);

Description

Computes the constrained Delaunay triangulation of polygons. Holes and Multipolygons are supported.

The "constrained Delaunay triangulation" of a polygon is a set of triangles formed from the vertices of the polygon, and covering it exactly, with the maximum total interior angle over all possible triangulations. It provides the "best quality" triangulation of the polygon.

Availability: 3.3.0.

Requires GEOS >= 3.11.0.

Examples

Triangulation of a square.

Code
SELECT ST_TriangulatePolygon('POLYGON((0 0,0 1,1 1,1 0,0 0))');
Output
GEOMETRYCOLLECTION(POLYGON((0 0,0 1,1 1,0 0)), POLYGON((1 1,1 0,0 0,1 1)))
Figure
Geometry figure for visual-st-triangulatepolygon-01

Triangulation of the letter P.

Code
SELECT ST_TriangulatePolygon('POLYGON ((26 17,31 19,34 21,37 24,38 29,39 43,39 161,38 172,36 176,34 179,30 181,25 183,10 185,10 190,100 190,121 189,139 187,154 182,167 177,177 169,184 161,189 152,190 141,188 128,186 123,184 117,180 113,176 108,170 104,164 101,151 96,136 92,119 89,100 89,86 89,73 89,73 39,74 32,75 27,77 23,79 20,83 18,89 17,106 15,106 10,10 10,10 15,26 17),(152 147,151 152,149 157,146 162,142 166,137 169,132 172,126 175,118 177,109 179,99 180,89 180,80 179,76 178,74 176,73 171,73 100,85 99,91 99,102 99,112 100,121 102,128 104,134 107,139 110,143 114,147 118,149 123,151 128,153 141,152 147))'
);
Output
GEOMETRYCOLLECTION (POLYGON ((10 10, 10 15, 26 17, 10 10)), POLYGON ((25 183, 10 185, 10 190, 25 183)), POLYGON ((126 175, 121 189, 139 187, 126 175)), POLYGON ((137 169, 139 187, 154 182, 137 169)), POLYGON ((149 157, 167 177, 177 169, 149 157)), POLYGON ((153 141, 189 152, 190 141, 153 141)), POLYGON ((153 141, 188 128, 186 123, 153 141)), POLYGON ((186 123, 184 117, 180 113, 186 123)), POLYGON ((149 123, 176 108, 170 104, 149 123)), POLYGON ((147 118, 164 101, 151 96, 147 118)), POLYGON ((121 102, 136 92, 119 89, 121 102)), POLYGON ((85 99, 73 89, 73 100, 85 99)), POLYGON ((89 17, 106 15, 106 10, 89 17)), POLYGON ((83 18, 10 10, 26 17, 83 18)), POLYGON ((100 190, 25 183, 10 190, 100 190)), POLYGON ((121 189, 109 179, 100 190, 121 189)), POLYGON ((189 152, 152 147, 184 161, 189 152)), POLYGON ((153 141, 190 141, 188 128, 153 141)), POLYGON ((147 118, 170 104, 164 101, 147 118)), POLYGON ((139 110, 151 96, 136 92, 139 110)), POLYGON ((73 89, 85 99, 86 89, 73 89)), POLYGON ((83 18, 89 17, 106 10, 83 18)), POLYGON ((83 18, 26 17, 31 19, 83 18)), POLYGON ((100 190, 30 181, 25 183, 100 190)), POLYGON ((189 152, 153 141, 152 147, 189 152)), POLYGON ((176 108, 151 128, 180 113, 176 108)), POLYGON ((91 99, 86 89, 85 99, 91 99)), POLYGON ((10 10, 83 18, 106 10, 10 10)), POLYGON ((76 178, 100 190, 80 179, 76 178)), POLYGON ((86 89, 91 99, 100 89, 86 89)), POLYGON ((79 20, 83 18, 31 19, 79 20)), POLYGON ((102 99, 100 89, 91 99, 102 99)), POLYGON ((34 21, 79 20, 31 19, 34 21)), POLYGON ((112 100, 100 89, 102 99, 112 100)), POLYGON ((37 24, 79 20, 34 21, 37 24)), POLYGON ((100 89, 112 100, 119 89, 100 89)), POLYGON ((79 20, 37 24, 77 23, 79 20)), POLYGON ((119 89, 112 100, 121 102, 119 89)), POLYGON ((77 23, 37 24, 75 27, 77 23)), POLYGON ((136 92, 121 102, 128 104, 136 92)), POLYGON ((38 29, 75 27, 37 24, 38 29)), POLYGON ((134 107, 136 92, 128 104, 134 107)), POLYGON ((75 27, 38 29, 74 32, 75 27)), POLYGON ((139 110, 136 92, 134 107, 139 110)), POLYGON ((74 32, 38 29, 73 39, 74 32)), POLYGON ((151 96, 139 110, 143 114, 151 96)), POLYGON ((39 43, 73 39, 38 29, 39 43)), POLYGON ((151 96, 143 114, 147 118, 151 96)), POLYGON ((73 39, 39 43, 73 89, 73 39)), POLYGON ((170 104, 147 118, 149 123, 170 104)), POLYGON ((73 89, 39 43, 73 100, 73 89)), POLYGON ((176 108, 149 123, 151 128, 176 108)), POLYGON ((39 161, 73 100, 39 43, 39 161)), POLYGON ((180 113, 151 128, 186 123, 180 113)), POLYGON ((73 100, 39 161, 73 171, 73 100)), POLYGON ((186 123, 151 128, 153 141, 186 123)), POLYGON ((38 172, 73 171, 39 161, 38 172)), POLYGON ((151 152, 184 161, 152 147, 151 152)), POLYGON ((73 171, 38 172, 74 176, 73 171)), POLYGON ((184 161, 151 152, 177 169, 184 161)), POLYGON ((36 176, 74 176, 38 172, 36 176)), POLYGON ((149 157, 177 169, 151 152, 149 157)), POLYGON ((34 179, 74 176, 36 176, 34 179)), POLYGON ((146 162, 167 177, 149 157, 146 162)), POLYGON ((74 176, 34 179, 76 178, 74 176)), POLYGON ((167 177, 146 162, 154 182, 167 177)), POLYGON ((30 181, 76 178, 34 179, 30 181)), POLYGON ((154 182, 146 162, 142 166, 154 182)), POLYGON ((100 190, 76 178, 30 181, 100 190)), POLYGON ((154 182, 142 166, 137 169, 154 182)), POLYGON ((80 179, 100 190, 89 180, 80 179)), POLYGON ((139 187, 137 169, 132 172, 139 187)), POLYGON ((100 190, 99 180, 89 180, 100 190)), POLYGON ((139 187, 132 172, 126 175, 139 187)), POLYGON ((100 190, 109 179, 99 180, 100 190)), POLYGON ((121 189, 126 175, 118 177, 121 189)), POLYGON ((121 189, 118 177, 109 179, 121 189)))
Figure
Geometry figure for visual-st-triangulatepolygon-02

Triangulation of the polygon used in the CG_Tesselate example.

Code
SELECT ST_TriangulatePolygon('POLYGON (( 10 190,10 70,80 70,80 130,50 160,120 160,120 190,10 190 ))'::geometry
);
Output
GEOMETRYCOLLECTION(POLYGON((50 160,120 190,120 160,50 160)),
POLYGON((10 70,80 130,80 70,10 70)),
POLYGON((50 160,10 70,10 190,50 160)),
POLYGON((120 190,50 160,10 190,120 190)),
POLYGON((80 130,10 70,50 160,80 130)))
Figure
Geometry figure for visual-st-triangulatepolygon-03