Re: [Jts-topo-suite-user] Triangulating polygons?
Brought to you by:
dr_jts
From: Martin D. <mtn...@te...> - 2010-04-23 18:42:39
|
Thanks, Michael. I'll try this out ASAP. For handling holes I can think of two approaches (neither of which is trivial, but maybe not too difficult either) 1. When selecting an ear to clip, ensure that the clipping line does not intersect any holes in the polygon. (Although - as I write this I can think of a simple counterexample - if a hole is *almost* as large as the shell itself, this won't be able to find a non-intersecting clipping line 2. (This one I think is foolproof, but harder). Turn the shel-with-holes into a self-intersecting-shell, by adding lines which connect each hole to the outer shell. Then triangulate the resulting shell as per normal (the self-intersection should not affect the triangulation algorithm. The tricky part is finding "good" lines to connect each hole. Possibly an exhaustive approach of trying to connect each hole vertex to each shell vertex and choosing the shortest line segment will work. Process each hole sequentially - there can be situations where a hole connects to a (former) hole. Michael Bedward wrote: > 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]); > } > > } > > ------------------------------------------------------------------------------ > _______________________________________________ > Jts-topo-suite-user mailing list > Jts...@li... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > |