Opened 4 years ago

Closed 3 years ago

#4198 closed enhancement (fixed)

Expose constrained Delaunay triangulation

Reported by: bwibo Owned by: komzpa
Priority: medium Milestone: PostGIS 3.0.0
Component: sfcgal Version:
Keywords: constrained delaunay triangulation Cc:

Description

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

Change History (7)

comment:1 by komzpa, 4 years ago

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?

comment:2 by komzpa, 4 years ago

Summary: EXpose constraint delauany triangulationExpose constrained Delaunay triangulation

comment:3 by bwibo, 4 years ago

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.

comment:4 by komzpa, 4 years ago

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.

comment:5 by komzpa, 3 years ago

Owner: changed from colivier to komzpa

comment:7 by komzpa, 3 years ago

Resolution: fixed
Status: newclosed

In 17448:

[sfcgal] Expose ST_ConstrainedDelaunayTriangles

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

Note: See TracTickets for help on using tickets.