Re: [Jts-topo-suite-user] Triangulating polygons?
Brought to you by:
dr_jts
From: Martin D. <mtn...@te...> - 2010-04-26 03:23:08
|
Michael, The code you provided doesn't work for me. Any chance you sent out an older version? Michael Bedward wrote: > 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); > } > > } > > ------------------------------------------------------------------------------ > _______________________________________________ > Jts-topo-suite-user mailing list > Jts...@li... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > |