Re: [Jts-topo-suite-user] Triangulating polygons?
Brought to you by:
dr_jts
From: Michael B. <mic...@gm...> - 2010-04-25 05:54:06
|
Normalizing the polygon did the trick. For the house-with-diamond polygon... POLYGON((0 0, 10 0, 10 5, 5 10, 0 5, 0 0), (5 3, 7 5, 5 7, 3 5, 5 3)) the algorithm returns these ears... POLYGON ((0 0, 0 5, 3 5, 0 0)) POLYGON ((0 0, 3 5, 5 3, 0 0)) POLYGON ((5 7, 3 5, 0 5, 5 7)) POLYGON ((5 7, 0 5, 5 10, 5 7)) POLYGON ((7 5, 5 7, 5 10, 7 5)) POLYGON ((7 5, 5 10, 10 5, 7 5)) POLYGON ((5 3, 7 5, 10 5, 5 3)) POLYGON ((0 0, 5 3, 10 5, 0 0)) POLYGON ((0 0, 10 5, 10 0, 0 0)) Not the prettiest solution, the second last ear in particular is a sliver, but it works. The code for this is below. > By the way, I can definitely visualize situations where the "choose > shortest segment to connect hole" algorithm won't work. Eg the following: > > POLYGON ((50 440, 50 50, 510 50, 510 440, 280 240, 50 440), > (105 230, 443 228, 106 208, 105 230), > (280 210, 260 190, 310 190, 280 210)) That's a nefarious polygon :-) I'll puzzle over that next. Michael /** * Demonstrates brute force approach to the ear clipping algorithm * to triangulate a polygon. This demo can deal with polygons having * non-challenging holes * * @author Michael Bedward */ public class EarClipping2 { private static final double EPS = 1.0E-4; GeometryFactory gf = new GeometryFactory(); public static void main(String[] args) throws Exception { new EarClipping2().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, 10 0, 10 5, 5 10, 0 5, 0 0), " + "(5 3, 7 5, 5 7, 3 5, 5 3))"); Geometry ears = triangulate(poly); for (int i = 0; i < ears.getNumGeometries(); 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) { List<Polygon> ears = new ArrayList<Polygon>(); List<Coordinate> coords = connectHoles(inputPoly); removeColinearVertices(coords); int N = coords.size() - 1; boolean finished = false; boolean found = false; boolean reversed = false; int k0 = 0; do { int k1 = (k0 + 1) % N; int k2 = (k1 + 2) % N; LineString ls = gf.createLineString(new Coordinate[] {coords.get(k0), coords.get(k2)}); found = false; if (inputPoly.covers(ls)) { Polygon ear = gf.createPolygon(gf.createLinearRing( new Coordinate[]{coords.get(k0), coords.get(k1), coords.get(k2), coords.get(k0)}), null); // additional check for hole over ear if (inputPoly.covers(ear)) { found = true; ears.add(ear); coords.remove(k1); removeColinearVertices(coords); N = coords.size() - 1; k0 = 0; if (N == 3) { // triangle ears.add(gf.createPolygon(gf.createLinearRing(coords.toArray(new Coordinate[4])), null)); finished = true; } } } if (!found) { k0++; if (k0 == N) { throw new IllegalStateException("Algorithm failed"); } } } 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 void removeColinearVertices(List<Coordinate> coords) { int N = coords.size() - 1; List<Coordinate> coordList = new ArrayList<Coordinate>(); for (int j = 1; j <= N; ) { int i = (j - 1) % N; int k = (j + 1) % N; if (Math.abs(Math.PI - Angle.angleBetween(coords.get(i), coords.get(j), coords.get(k))) < EPS) { coords.remove(j); N-- ; } else { j++ ; } } } /** * Connect any holes in the input polygon to the exterior ring to * form a self-intersecting shell * * @param inputPoly input polygon * @return a new polygon with holes (if any) connected to the exterior * ring */ private List<Coordinate> connectHoles(Polygon inputPoly) { // defensively copy the input polygon Polygon poly = (Polygon) inputPoly.clone(); poly.normalize(); Coordinate[] coords = poly.getExteriorRing().getCoordinates(); List<Coordinate> shellCoords = new ArrayList<Coordinate>(); shellCoords.addAll(Arrays.asList(coords)); for (int i = 0; i < inputPoly.getNumInteriorRing(); i++) { List<Coordinate> holeCoords = Arrays.asList(poly.getInteriorRingN(i).getCoordinates()); joinClosest(shellCoords, holeCoords); } return shellCoords; } private void joinClosest(List<Coordinate> shellCoords, List<Coordinate> holeCoords) { double minD2 = Double.MAX_VALUE; int minIh = -1, minIs = -1; final int Ns = shellCoords.size() - 1; final int Nh = holeCoords.size() - 1; for (int is = 0; is < Ns; is++) { Coordinate cs = shellCoords.get(is); for (int ih = 0; ih < Nh; ih++) { Coordinate ch = holeCoords.get(ih); double d2 = (ch.x - cs.x)*(ch.x - cs.x) + (ch.y - cs.y)*(ch.y - cs.y); if (d2 < minD2) { minD2 = d2; minIh = ih; minIs = is; } } } /* * Insert the join, then the hole coords, then the join again into * shell coords list */ List<Coordinate> toAdd = new ArrayList<Coordinate>(); toAdd.add(new Coordinate(shellCoords.get(minIs))); int i = minIh; do { toAdd.add(new Coordinate(holeCoords.get(i))); i = (i + 1) % Nh; } while (i != minIh); toAdd.add(new Coordinate(holeCoords.get(minIh))); shellCoords.addAll(minIs, toAdd); } } |