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

Stephen Woodbridge woodbri at swoodbridge.com
Sat Jun 4 10:54:39 EDT 2011


On 6/4/2011 9:51 AM, Sandro Santilli wrote:
> On Sat, Jun 4, 2011 at 11:49 AM, Brian Sanjeewa Rupasinghe
> <jinkabs at 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.

Thanks,
   -Steve


More information about the pgrouting-dev mailing list