Thursday, April 30, 2009

Delaunay Triangulation in JTS 1.11

The next version of JTS (1.11) will include an API for creating Delaunay triangulations and Conforming Delaunay triangulations. For a thorough explanation of the differences between Delaunay, Conforming Delaunay, and Constrained Delaunay, and why they are actually quite difficult to compute, see Jonathan Shewchuk's wonderful web site. [Side note - yet another B.C.-grown spatial dude - must be something in the water up here!]

This Delaunay implementation arose out of the work I did on automated watershed extraction using a system called WaterBuG a while back. It's taken a while to make its way into JTS because there's quite a bit of work involved in turning a codebase targeted at a very specific project into a clean, user-friendly API. Not to mention writing documentation...

But it's there now, and I'll be interested to see if it's of use to JTSer's. There seems to be a sudden surfeit of Delaunay and CDT Java libraries (see here, here, here, here and here), so I make no claims that the JTS one is best-of-breed. But hopefully having a decent implementation easily accessible and embedded in a general-purpose library will meet some needs. Also, my hope is that it will serve as the basis for further algorithms in JTS (such as the much-sought-after Concave Hull!).

Here's some screenshots showing the triangulation API at work:

The input points and constraint segments:
The Delaunay triangulation (notice that triangle edges cross some of the longer constraint edges):
A conforming Delaunay triangulation (the triangulation edges are now faithful to the constraint edges):