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.
Friday, 8 April 2011
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:
A country that has been in the news recently:
A country that has been in the news recently:
Subscribe to:
Post Comments (Atom)
4 comments:
Is this triangulation method available in the current JTS version? If so, which class is it? If not, is there another way to triangulate with support for holes?
Thanks!
Did the code ever get into JTS ?
Despite this post being years old, it's still a top result on google when searching for ear clipping in JTS. I've tested out this library for triangulation OSM data and it works better than any other library out there that I've found.
In the hopes of helping someone in the future, I've taken the liberty of posting this code on Github
https://github.com/metsfan/jts_earclipper
Its small enough that you can probably just throw the source into your project. But if someone wants to wrap it into a JTS fork or add it to maven I'd be happy to accept pull requests.
please can anyone give me the code?
Post a Comment