postgis – Creating st_delaunaytriangles Polygon with Holes

delaunayholespostgis

I'm using PostGIS to decompose a polygon with a few holes into triangles via st_delaunaytriangles. Unfortunately, it does not return the right result with holes, because the triangles being outputted cross the section with holes (I want the holes to be empty, i.e. no triangle should enter any of these holes).

I attempted to split the polygons with a line segment to create two polygons without a hole, but this did not work as expected.

Is there a way to decompose a polygon with holes into triangles, while forcing the triangles to not enter the holes?

Best Answer

-UPDATE- Since Postgis3 this function is available by default when SFCGAL is enabled as: ST_ConstrainedDelaunayTriangles

The ST_DelaunayTriangles function is based on points in the input and doesn't look at the already available linework in your geometry. Hence, it will not only ignore the holes, the resulting triangles may also cross your original polygon. What you are looking for is a constrained Delaunay triangulation. Luckily, there is a hidden functionality in SFCGAL that does precisely that, and faster than the geos version. Make sure you get postgis including sfcgal and add the functionality with:

CREATE OR REPLACE FUNCTION public.st_triangulate2dz(geometry)
  RETURNS geometry AS
'$libdir/postgis-2.3', 'sfcgal_triangulate'
  LANGUAGE c IMMUTABLE STRICT
  COST 100;

(make sure you set the correct postgis version).

Please note: the constrained Delaunay triangulation will still fill-up the interior and exterior of the polygon, which means you need to remove the non-overlapping polygons after triangulation.

Related Question