Re: [Jts-topo-suite-user] Triangulating polygons?
Brought to you by:
dr_jts
From: Michael B. <mic...@gm...> - 2010-04-23 06:51:24
|
This isn't a patch but a demo of brute force ear-clipping. Need some tips about how to deal with holes. I also had a look at the paper you pointed to Martin. Haven't got my head around it yet but it did make more sense when I finally realized the pages are in the wrong order :) 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; GeometryFactory gf = new GeometryFactory(); public static void main(String[] args) throws Exception { new EarClipping().demo(); } /** * Demonstrate the ear-clipping algorithm * @throws Exception */ private void demo() throws Exception { WKTReader reader = new WKTReader(gf); Polygon poly = (Polygon )reader.read("POLYGON((0 0, 5 0, 2 3, 5 5, 10 0, 10 -5, 5 -2, 0 -5, 0 0))"); System.out.println("Input polygon:"); System.out.println(poly); Geometry ears = triangulate(poly); final int n = ears.getNumGeometries(); System.out.println(); System.out.println("Found " + n + " ears:"); for (int i = 0; i < n; i++) { System.out.println(ears.getGeometryN(i)); } } /** * Brute force approach to ear clipping * * @param inputPoly input polygon * @return GeometryCollection of triangular polygons */ private Geometry triangulate(Polygon inputPoly) { if (inputPoly.getNumGeometries() > 1) { throw new IllegalArgumentException("Can't deal with holes yet"); } List<Polygon> ears = new ArrayList<Polygon>(); Polygon workingPoly = (Polygon) inputPoly.clone(); Coordinate[] coords = workingPoly.getBoundary().getCoordinates(); int N = coords.length - 1; boolean finished = false; int k0 = 0; do { int k1 = (k0 + 1) % N; int k2 = (k0 + 2) % N; LineString ls = gf.createLineString(new Coordinate[] {coords[k0], coords[k2]}); if (workingPoly.covers(ls)) { Polygon ear = gf.createPolygon( gf.createLinearRing(new Coordinate[]{coords[k0], coords[k1], coords[k2], coords[k0]}), null); ears.add(ear); workingPoly = (Polygon) workingPoly.difference(ear); coords = workingPoly.getBoundary().getCoordinates(); coords = removeColinearVertices(coords); N = coords.length - 1; k0 = 0; if (N == 3) { // triangle ears.add(gf.createPolygon(gf.createLinearRing(coords), null)); finished = true; } } else { k0++ ; } } while (!finished); return gf.createGeometryCollection(ears.toArray(new Geometry[0])); } /** * Remove co-linear vertices. TopologyPreservingSimplifier could be * used for this but that seems like over-kill. * * @param coords polygon vertices * @return coordinates with any co-linear vertices removed */ private Coordinate[] removeColinearVertices(Coordinate[] coords) { final int N = coords.length - 1; List<Coordinate> coordList = new ArrayList<Coordinate>(); for (int j = 1; j <= N; j++) { int i = (j - 1) % N; int k = (j + 1) % N; if (Math.abs(Math.PI - Angle.angleBetween(coords[i], coords[j], coords[k])) > EPS) { coordList.add(coords[j]); } } coordList.add(new Coordinate(coordList.get(0))); return coordList.toArray(new Coordinate[0]); } } |