[GEO] Fix hole intersection at tangential coordinate

nknize · nknize · commit adb3e873f20e · 2015-04-10T12:23:32.000-05:00
OGC SFA 2.1.10 assertion 3 allows interior boundaries to touch exterior boundaries provided they intersect at a single point. Issue elastic#9511 provides an example where a valid shape is incorrectly interpreted as invalid (a false violation of assertion 3). When the intersecting point appears as the first and last coordinate of the interior boundary in a polygon, the ShapeBuilder incorrectly counted this as multiple intersecting vertices. The fix required a little more than just a logic check. Passing the duplicate vertices resulted in a connected component in the edge graph causing an invalid self crossing polygon. This required additional logic to the edge assignment in order to correctly segment the connected components. Finally, an additional hole validation has been added along with proper unit tests for testing valid and invalid conditions (including dateline crossing polys). closes elastic#9511
diff --git a/src/main/java/org/elasticsearch/common/geo/builders/BasePolygonBuilder.java b/src/main/java/org/elasticsearch/common/geo/builders/BasePolygonBuilder.java
@@ -19,14 +19,18 @@
 
 package org.elasticsearch.common.geo.builders;
 
+import com.google.common.collect.Sets;
+import com.spatial4j.core.exception.InvalidShapeException;
 import com.spatial4j.core.shape.Shape;
 import com.vividsolutions.jts.geom.*;
-import org.elasticsearch.ElasticsearchParseException;
+import org.apache.commons.lang3.tuple.Pair;
 import org.elasticsearch.common.xcontent.XContentBuilder;
 
 import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.HashMap;
+import java.util.HashSet;
 import java.util.Iterator;
 
 /**
@@ -111,6 +115,18 @@ public ShapeBuilder close() {
         return shell.close();
     }
 
+    /**
+     * Validates only 1 vertex is tangential (shared) between the interior and exterior of a polygon
+     */
+    protected void validateHole(BaseLineStringBuilder shell, BaseLineStringBuilder hole) {
+        HashSet exterior = Sets.newHashSet(shell.points);
+        HashSet interior = Sets.newHashSet(hole.points);
+        exterior.retainAll(interior);
+        if (exterior.size() >= 2) {
+            throw new InvalidShapeException("Invalid polygon, interior cannot share more than one point with the exterior");
+        }
+    }
+
     /**
      * The coordinates setup by the builder will be assembled to a polygon. The result will consist of
      * a set of polygons. Each of these components holds a list of linestrings defining the polygon: the
@@ -125,6 +141,7 @@ public Coordinate[][][] coordinates() {
         int numEdges = shell.points.size()-1; // Last point is repeated 
         for (int i = 0; i < holes.size(); i++) {
             numEdges += holes.get(i).points.size()-1;
+            validateHole(shell, this.holes.get(i));
         }
 
         Edge[] edges = new Edge[numEdges];
@@ -253,28 +270,62 @@ private static int component(final Edge edge, final int id, final ArrayList<Edge
             }
         }
 
-        double shift = any.coordinate.x > DATELINE ? DATELINE : (any.coordinate.x < -DATELINE ? -DATELINE : 0);
+        double shiftOffset = any.coordinate.x > DATELINE ? DATELINE : (any.coordinate.x < -DATELINE ? -DATELINE : 0);
         if (debugEnabled()) {
-            LOGGER.debug("shift: {[]}", shift);
+            LOGGER.debug("shift: {[]}", shiftOffset);
         }
 
         // run along the border of the component, collect the
         // edges, shift them according to the dateline and
         // update the component id
-        int length = 0;
+        int length = 0, connectedComponents = 0;
+        // if there are two connected components, splitIndex keeps track of where to split the edge array
+        // start at 1 since the source coordinate is shared
+        int splitIndex = 1;
         Edge current = edge;
+        Edge prev = edge;
+        // bookkeep the source and sink of each visited coordinate
+        HashMap<Coordinate, Pair<Edge, Edge>> visitedEdge = new HashMap<>();
         do {
-
-            current.coordinate = shift(current.coordinate, shift); 
+            current.coordinate = shift(current.coordinate, shiftOffset);
             current.component = id;
-            if(edges != null) {
+
+            if (edges != null) {
+                // found a closed loop - we have two connected components so we need to slice into two distinct components
+                if (visitedEdge.containsKey(current.coordinate)) {
+                    if (connectedComponents > 0 && current.next != edge) {
+                        throw new InvalidShapeException("Shape contains more than one shared point");
+                    }
+
+                    // a negative id flags the edge as visited for the edges(...) method.
+                    // since we're splitting connected components, we want the edges method to visit
+                    // the newly separated component
+                    final int visitID = -id;
+                    Edge firstAppearance = visitedEdge.get(current.coordinate).getRight();
+                    // correct the graph pointers by correcting the 'next' pointer for both the
+                    // first appearance and this appearance of the edge
+                    Edge temp = firstAppearance.next;
+                    firstAppearance.next = current.next;
+                    current.next = temp;
+                    current.component = visitID;
+                    // backtrack until we get back to this coordinate, setting the visit id to
+                    // a non-visited value (anything positive)
+                    do {
+                        prev.component = visitID;
+                        prev = visitedEdge.get(prev.coordinate).getLeft();
+                        ++splitIndex;
+                    } while (!current.coordinate.equals(prev.coordinate));
+                    ++connectedComponents;
+                } else {
+                    visitedEdge.put(current.coordinate, Pair.of(prev, current));
+                }
                 edges.add(current);
+                prev = current;
             }
-
             length++;
-        } while((current = current.next) != edge);
+        } while(connectedComponents == 0 && (current = current.next) != edge);
 
-        return length;
+        return (splitIndex != 1) ? length-splitIndex: length;
     }
 
     /**
@@ -364,11 +415,12 @@ private static void assign(Edge[] holes, Coordinate[][] points, int numHoles, Ed
             // if no intersection is found then the hole is not within the polygon, so
             // don't waste time calling a binary search
             final int pos;
-            if (intersections == 0 ||
-               (pos = Arrays.binarySearch(edges, 0, intersections, current, INTERSECTION_ORDER)) >= 0) {
-                throw new ElasticsearchParseException("Invalid shape: Hole is not within polygon");
+            boolean sharedVertex = false;
+            if (intersections == 0 || ((pos = Arrays.binarySearch(edges, 0, intersections, current, INTERSECTION_ORDER)) >= 0)
+                            && !(sharedVertex = (edges[pos].intersect.compareTo(current.coordinate) == 0)) ) {
+                throw new InvalidShapeException("Invalid shape: Hole is not within polygon");
             }
-            final int index = -(pos+2);
+            final int index = -((sharedVertex) ? 0 : pos+2);
             final int component = -edges[index].component - numHoles - 1;
 
             if(debugEnabled()) {
@@ -465,7 +517,7 @@ private static int createEdges(int component, Orientation orientation, BaseLineS
                                    Edge[] edges, int offset) {
         // inner rings (holes) have an opposite direction than the outer rings
         // XOR will invert the orientation for outer ring cases (Truth Table:, T/T = F, T/F = T, F/T = T, F/F = F)
-        boolean direction = (component != 0 ^ orientation == Orientation.RIGHT);
+        boolean direction = (component == 0 ^ orientation == Orientation.RIGHT);
         // set the points array accordingly (shell or hole)
         Coordinate[] points = (hole != null) ? hole.coordinates(false) : shell.coordinates(false);
         Edge.ring(component, direction, orientation == Orientation.LEFT, shell, points, 0, edges, offset, points.length-1);
diff --git a/src/main/java/org/elasticsearch/common/geo/builders/ShapeBuilder.java b/src/main/java/org/elasticsearch/common/geo/builders/ShapeBuilder.java
@@ -20,6 +20,7 @@
 package org.elasticsearch.common.geo.builders;
 
 import com.spatial4j.core.context.jts.JtsSpatialContext;
+import com.spatial4j.core.exception.InvalidShapeException;
 import com.spatial4j.core.shape.Shape;
 import com.spatial4j.core.shape.jts.JtsGeometry;
 import com.vividsolutions.jts.geom.Coordinate;
@@ -446,7 +447,8 @@ protected static final class Edge {
 
         protected Edge(Coordinate coordinate, Edge next, Coordinate intersection) {
             this.coordinate = coordinate;
-            this.next = next;
+            // use setter to catch duplicate point cases
+            this.setNext(next);
             this.intersect = intersection;
             if (next != null) {
                 this.component = next.component;
@@ -457,6 +459,17 @@ protected Edge(Coordinate coordinate, Edge next) {
             this(coordinate, next, Edge.MAX_COORDINATE);
         }
 
+        protected void setNext(Edge next) {
+            // don't bother setting next if its null
+            if (next != null) {
+                // self-loop throws an invalid shape
+                if (this.coordinate.equals(next.coordinate)) {
+                    throw new InvalidShapeException("Provided shape has duplicate consecutive coordinates at: " + this.coordinate);
+                }
+                this.next = next;
+            }
+        }
+
         private static final int top(Coordinate[] points, int offset, int length) {
             int top = 0; // we start at 1 here since top points to 0
             for (int i = 1; i < length; i++) {
@@ -522,17 +535,19 @@ private static Edge[] concat(int component, boolean direction, Coordinate[] poin
                 if (direction) {
                     edges[edgeOffset + i] = new Edge(points[pointOffset + i], edges[edgeOffset + i - 1]);
                     edges[edgeOffset + i].component = component;
-                } else {
+                } else if(!edges[edgeOffset + i - 1].coordinate.equals(points[pointOffset + i])) {
                     edges[edgeOffset + i - 1].next = edges[edgeOffset + i] = new Edge(points[pointOffset + i], null);
                     edges[edgeOffset + i - 1].component = component;
+                } else {
+                    throw new InvalidShapeException("Provided shape has duplicate consecutive coordinates at: " + points[pointOffset + i]);
                 }
             }
 
             if (direction) {
-                edges[edgeOffset].next = edges[edgeOffset + length - 1];
+                edges[edgeOffset].setNext(edges[edgeOffset + length - 1]);
                 edges[edgeOffset].component = component;
             } else {
-                edges[edgeOffset + length - 1].next = edges[edgeOffset];
+                edges[edgeOffset + length - 1].setNext(edges[edgeOffset]);
                 edges[edgeOffset + length - 1].component = component;
             }
 
diff --git a/src/test/java/org/elasticsearch/common/geo/GeoJSONShapeParserTests.java b/src/test/java/org/elasticsearch/common/geo/GeoJSONShapeParserTests.java
@@ -267,7 +267,7 @@ public void testParse_invalidMultiPolygon() throws IOException {
 
         XContentParser parser = JsonXContent.jsonXContent.createParser(multiPolygonGeoJson);
         parser.nextToken();
-        ElasticsearchGeoAssertions.assertValidException(parser, ElasticsearchParseException.class);
+        ElasticsearchGeoAssertions.assertValidException(parser, InvalidShapeException.class);
     }
 
     public void testParse_OGCPolygonWithoutHoles() throws IOException {
diff --git a/src/test/java/org/elasticsearch/common/geo/ShapeBuilderTests.java b/src/test/java/org/elasticsearch/common/geo/ShapeBuilderTests.java

Original file line number	Diff line number	Diff line change
`@@ -267,7 +267,7 @@ public void testParse_invalidMultiPolygon() throws IOException {`
`267`	`267`
`268`	`268`	`XContentParser parser = JsonXContent.jsonXContent.createParser(multiPolygonGeoJson);`
`269`	`269`	`parser.nextToken();`
`270`		`- ElasticsearchGeoAssertions.assertValidException(parser, ElasticsearchParseException.class);`
	`270`	`+ ElasticsearchGeoAssertions.assertValidException(parser, InvalidShapeException.class);`
`271`	`271`	`}`
`272`	`272`
`273`	`273`	`public void testParse_OGCPolygonWithoutHoles() throws IOException {`