Last Resort Software

In the last episode I presented some code to triangulate a polygon using the ear-clipping algorithm. In this instalment the code has been extended to deal with polygons that have holes. Here are two example results... No, they're not the prettiest triangulations ever seen, but they could be improved with some post-processing. Here is the Java code used to generate them. Note, you'll need the JTS library if you want to run this. Warning: this code isn't pretty, even by my standards, but it might be useful if you want to play with the algorithm. import com.vividsolutions.jts.algorithm.CGAlgorithms; import com.vividsolutions.jts.geom.Coordinate; import com.vividsolutions.jts.geom.Envelope; import com.vividsolutions.jts.geom.Geometry; import com.vividsolutions.jts.geom.GeometryFactory; import com.vividsolutions.jts.geom.LineString; import com.vividsolutions.jts.geom.Polygon; import com.vividsolutions.jts.io.WKTReader; import java.awt.Color; import java.util.ArrayList; import

Inspired by a recent discussion on the JTS user list about decomposing simple polygons into triangles, here is a program that demonstrates the brute force, ear-clipping algorithm. To run this you will need the JTS library which you can get from the project web site or as a maven artifact (version 1.11) from the Maven central repository . import com.vividsolutions.jts.algorithm.Angle; import com.vividsolutions.jts.geom.Coordinate; import com.vividsolutions.jts.geom.Geometry; import com.vividsolutions.jts.geom.GeometryFactory; import com.vividsolutions.jts.geom.LineString; import com.vividsolutions.jts.geom.Polygon; import com.vividsolutions.jts.io.WKTReader; import java.util.ArrayList; import java.util.List; /** * Demonstrates brute force approach to the ear clipping algorithm * to triangulate a polygon. This demo doesn't yet cope with * polygons that have holes. * * @author Michael Bedward */ public class EarClipping { private static final double EPS = 1.0E-4; Geome