Expose constrained Delaunay triangulation

[bwibo]

SFCGAL provides a function for a Constrained Delaunay Triangluation. This is a useful feature for many application scenarios. Currently, it can be accessed like this:

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

It would be great to expose this SFCGAL function in PostGIS in the future.

I created a GIST with some more information and a small testing example and some images. ​https://gist.github.com/BWibo/2614b89b25827908fcac57efc525cbc5

[komzpa]

Wow, it's cool it's almost there already :)

It feels that a good way of doing it would be to make ST_DelaunayTriangles depend on postgis.backend the same way the rest of geos/sfcgal functions are?

[bwibo]

I believe that there are use cases for both constrained and non-constrained delaunay triangulation. So maybe two different functions or a switch to control the behavior of the triangulation would be best for most people.

I am not an expert on PostGIS/SFCGAL architecture, but if possible, I would rather add another function or offer ST_DElaunayTriangles with another signature, e.g. ST_DelauneyTriangles(geometry, boolean=enableConstrainedTriangluation), if SFCGAL backend is available.

[komzpa]

For non-constrained triangulation it's trivial to get it by feeding just points as input, ST_DumpPoints is there.

I don't see a common use case where one will be willing to put a linework into ST_DelaunayTriangles and then want it to be ignored. Nowadays it's more common to see it backwards, by applying ST_Segmentize to the linework to make sure the non-constrained triangulation is at least up to some extent follows constraints.

There is Conforming Delaunay Triangulation implementation in JTS. It wasn't ported to GEOS but probably could, then behavior will be similar in both backends.

[komzpa]

​https://github.com/postgis/postgis/pull/405

[komzpa]

In 17448:

[sfcgal] Expose ST_ConstrainedDelaunayTriangles

Closes #4198
Closes ​https://github.com/postgis/postgis/pull/405