Good stuff, Michael!
A couple of ideas:
1. One way to improve triangulations is to "flip" edges within their
surrounding quadrilaterals, if flipping the edge would improve the
triangulation. (The exact test for improvement escapes me at the
moment, but I'll dig it out. Perhaps maximizing the minimum angle
size...) For instance, this would improve the sliver you noted.
2. For "connecting holes", I think perhaps a sweepline algorithm would
work. Sweep along (say) the Y axis from bottom to top. As the first
point of each hole is encountered, I think that some vertex of the
current shell should be visible from that point. Of course this might
not produce the best initial set of interior triangle segments - but
that's where #1 comes in.
Something to note is that creating a "good" triangulation is much harder
than creating "some" triangulation. In fact it's probably NP-complete
or something bad like that. So heuristic approachs like the one above
are always going to be necessary.
Martin
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-topo-suite-user@...
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>
>
|