[pgrouting-dev] Re: [postgis-users] Constrained Delaunay Triangulation

On 6/4/2011 9:51 AM, Sandro Santilli wrote:

On Sat, Jun 4, 2011 at 11:49 AM, Brian Sanjeewa Rupasinghe
<jinkabs@gmail.com> wrote:

Can i implement constrained delaunay triangulation in PostGIS?

Sanjeewa, I belive it would make sense to port the algorithm from JTS
(1.12) to GEOS first
and then have PostGIS give access to the GEOS implementation throught its C-API.

Sorry cross-posting this to pgRouting.

I would like to through out a use case for delauny triangulation to think about if you go forward with implementing this.

pgRouting today computes a drive time polygons. The way this is done is to solve a graph problem that results in a set of nodes (x,y) and a cost (z) at each node. If these nodes(ie 3D points) can be triangulated into a triangulated surface, then the surface can be sliced by equi-interval planes to create the edges of the polygons, that could then be passed to ST_BuildArea() to create polygon contours.

Today we use CGAL to post process the 3D points into contours, but we would like to remove that as a dependency because it has license complication.

I'm sure there are a lot of other use cases out there, but this is just one that I would like to add.