Thursday, 30 April 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):
at

8 comments:

  1. mentaer1 May 2009 at 20:27

    great! thanks Martin. I guess it will sooner or later make its way into OpenJUMP (the questions is in which enduser friendly application way). But research will pick it up for sure.

    ReplyDelete
  2. Unknown17 May 2009 at 02:09

    Hello.

    Thank you for your great work.

    Are you interested in Generalized Voronoi Diagrams/Algorithms as follows.


    -http://www.nirarebakun.com/voro/voro.html (Sorry in Japanese and too heavy)

    -Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware: http://www.cs.unc.edu/~geom/voronoi/




    Regards.

    ReplyDelete
  3. jlhgis12 August 2009 at 20:30

    Hi Martin

    Curious - whatever became of your WaterBuG application? Never was able to find a copy of your presentation from FOSS4G 07 or GeoTec07 anywhere online - just a couple of "teaser mentions" here & there. Is WaterBuG still alive ? If so, any information available about it? Would it be possible to use it on USGS NHD format stream network data ?

    Thanks,

    Julia

    ReplyDelete
  4. Dr JTS12 August 2009 at 21:29

    Julia,

    WaterBuG is alive and well, but not leading a very exciting life these days. It is being used in production for computing watersheds for the BC stream network, and has worked well for that application. As long as there was a suitable driver to read the USGS data, I expect it would be able to run on it as well.

    You're right about there being a lack of information & code available, though. As you know, it takes a bit of effort to package up an application along with documentation to make it usable by a wider audience. Unfortunately the client sort of lost interest in doing this, and we haven't devoted the time to doing so up til now.

    I can provide the presentation easily - in fact, I'll make it available online. The source could be available too - with the proviso that it will probably need some work to make the inputs & outputs more generally usable. What I'd like to do is to provide WaterBuG as a JEQL extension - that will make it much more easily configurable for inputs, outputs and parameters.

    Feel free to contact me directly for more info.

    ReplyDelete
  5. Alexander7 January 2010 at 14:57

    Hello Martin,

    When is version 1.11 going to be released? My interest is in nterpolating surface with a VERY large number of data points, using the Delaunay triangulation.

    Thanks,

    Alex Molochnikov
    Kelman Technologies Inc.

    ReplyDelete
  6. ouioui10 January 2011 at 08:33

    Hi Martin,

    Thanks for this amazing JTS package! I have tested it. It is easy to use and very quick.

    However, I did not find how to compute a conforming Delaunay triangulation without creation of new points on the constraint edges. I know in this case the triangulation is no more a 'Delaunay' triangulation, but is it possible to get it?

    ReplyDelete
  7. Dr JTS12 January 2011 at 22:38

    JTS will compute a conforming Delaunay Triangulation. This is a true Delaunay, but which necessarily introduces new Steiner points along edges. There is also a notion of a constrained Delaunay, which isn't true Delaunay but which doesn't split edges. JTS does not have code to compute this.

    ReplyDelete
  8. ouioui14 January 2011 at 01:47

    Thanks for your answer!

    ReplyDelete