Polygon Triangulation via Ear-Clipping with Delaunay Refinement

After this thread on the JTS list Michael Bedward was inspired to create a polygon triangulation algorithm using the Ear-Clipping approach. Standard Ear-Clipping algorithms don't handle polygons with holes, but Michael made a nice extension to do this. (David Eberly has a good write-up on this subject here, and of course there's always Wikipedia). One problem with ear-clipping is that it produces sub-optimal triangulations (in the the sense that it creates lots of very skinny triangles, which are visually and computationally unappealing). I suggested that he add a refinement step based on "flipping triangles" to improve the quality of the output triangle mesh. This is similar to the approach used in Delaunay triangulation algorithms, and in fact it turns out that a good flipping criteria is to test for the Delaunay condition. (Two adjacent triangles which form a convex quadrilateral are Delaunay if neither lies in the circumcircle of the other. Wikipedia has a nice visual explanation). This code will get added to JTS in the next release. In the meantime, here's some cool pictures showing how it works. A gnarly test polygon:

Before refinement

After refinement

A country that has been in the news recently:

Before refinement

After refinement

Update (Nov 1, 2021): JTS now has Polygon Triangulation code.  See this post for details.

Dynamic Views in Google Blogs

Check out the cool new Dynamic Views feature for Google Blogs. I'm not sure how useful this is actually going to be for readers (especially since you have to do URL editing to invoke them - WTB!? (Where's The Button 8^)

But they sure look purty. Here's a shot of the Flipcard view:

Slope/Aspect/Elevation using JTS

David Skea is a longtime colleague, JTS contributor, and all-around geospatial guru. He's developing a Slope/Aspect/Elevation service to be used in forestry-related applications here in British Columbia. His work is a nice example of using JTS to perform real-world spatial processing.

The key to computing slope, aspect and elevation is to have a Digital Elevation Model (DEM) available for the terrain in the area of interest. In this case, the terrain data is provided by the TRIM irregular DEM, which is a dataset of over 500 million mass points covering all of British Columbia. To compute the required values for a given polygon, the first step is to extract only the mass points in the immediate region of the polygon (i.e. using the polygon envelope with a suitable buffer distance. The JTS Delaunay Triangulation API is used to compute a TIN triangulation from the TRIM mass points.


Using a JTS PointOnGeometryLocator, the triangles whose centroids lie in the polygon are selected. Since each mass point has an elevation value, each TIN triangle is located in 3D space. The normal vector can be computed for each triangle, which provides the slope and aspect values. The elevation is the height of the triangle centroid.

The SEA values for the triangles are averaged to compute the overall slope, aspect and elevation value for the polygon.

Here's a screenshot showing the results, using Google Earth as a convenient 3D visualization tool (click for full-size image).