You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by th...@apache.org on 2016/04/14 01:21:47 UTC
[31/50] lucene-solr:jira/SOLR-8908: LUCENE-7204: Add check for
backtracking over polygon path.
LUCENE-7204: Add check for backtracking over polygon path.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/414bdea9
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/414bdea9
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/414bdea9
Branch: refs/heads/jira/SOLR-8908
Commit: 414bdea97a5c1e514c0ea28abf3d7b0471cf04a5
Parents: e034b04
Author: Karl Wright <Da...@gmail.com>
Authored: Tue Apr 12 15:37:13 2016 -0400
Committer: Karl Wright <Da...@gmail.com>
Committed: Tue Apr 12 15:37:13 2016 -0400
----------------------------------------------------------------------
.../spatial3d/geom/GeoPolygonFactory.java | 79 +++++++++++++++++++-
.../lucene/spatial3d/geom/GeoPolygonTest.java | 40 ++++++++++
2 files changed, 117 insertions(+), 2 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/414bdea9/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPolygonFactory.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPolygonFactory.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPolygonFactory.java
index 4b7f4f4..9865ac0 100755
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPolygonFactory.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPolygonFactory.java
@@ -64,6 +64,7 @@ public class GeoPolygonFactory {
final List<GeoPolygon> holes) {
// The basic operation uses a set of points, two points determining one particular edge, and a sided plane
// describing membership.
+ //System.out.println("Initial point list = "+pointList+"; convexPointIndex = "+convexPointIndex+"; holes = "+holes);
final GeoCompositePolygon rval = new GeoCompositePolygon();
if (buildPolygonShape(rval,
planetModel, pointList, new BitSet(),
@@ -391,6 +392,68 @@ public class GeoPolygonFactory {
// The edge buffer.
final EdgeBuffer edgeBuffer = new EdgeBuffer(pointsList, internalEdges, startPointIndex, endPointIndex, startingEdge);
+ /*
+ // Verify that the polygon does not self-intersect
+ // Now, look for non-adjacent edges that cross.
+ System.err.println("Looking for intersections...");
+ System.err.println("Starting edge is: "+startingEdge);
+ final Iterator<Edge> edgeIterator = edgeBuffer.iterator();
+ while (edgeIterator.hasNext()) {
+ final Edge edge = edgeIterator.next();
+ final Set<Edge> excludedEdges = new HashSet<>();
+ excludedEdges.add(edge);
+ Edge oneBoundary = edgeBuffer.getPrevious(edge);
+ while (oneBoundary.plane.isNumericallyIdentical(edge.plane)) {
+ excludedEdges.add(oneBoundary);
+ oneBoundary = edgeBuffer.getPrevious(oneBoundary);
+ }
+ excludedEdges.add(oneBoundary);
+ Edge otherBoundary = edgeBuffer.getNext(edge);
+ while (otherBoundary.plane.isNumericallyIdentical(edge.plane)) {
+ excludedEdges.add(otherBoundary);
+ otherBoundary = edgeBuffer.getNext(otherBoundary);
+ }
+ excludedEdges.add(otherBoundary);
+
+ // Now go through all other edges and rule out any intersections
+ final Iterator<Edge> compareIterator = edgeBuffer.iterator();
+ while (compareIterator.hasNext()) {
+ final Edge compareEdge = compareIterator.next();
+ if (!excludedEdges.contains(compareEdge)) {
+ // Found an edge we can compare with!
+ //System.err.println("Found a compare edge...");
+ boolean nonOverlapping = true;
+ // We need the other boundaries though.
+ Edge oneCompareBoundary = edgeBuffer.getPrevious(compareEdge);
+ while (oneCompareBoundary.plane.isNumericallyIdentical(compareEdge.plane)) {
+ if (excludedEdges.contains(oneCompareBoundary)) {
+ //System.err.println(" excluded because oneCompareBoundary found to be in set");
+ nonOverlapping = false;
+ break;
+ }
+ oneCompareBoundary = edgeBuffer.getPrevious(oneCompareBoundary);
+ }
+ Edge otherCompareBoundary = edgeBuffer.getNext(compareEdge);
+ while (otherCompareBoundary.plane.isNumericallyIdentical(compareEdge.plane)) {
+ if (excludedEdges.contains(otherCompareBoundary)) {
+ //System.err.println(" excluded because otherCompareBoundary found to be in set");
+ nonOverlapping = false;
+ break;
+ }
+ otherCompareBoundary = edgeBuffer.getNext(otherCompareBoundary);
+ }
+ if (nonOverlapping) {
+ //System.err.println("Preparing to call findIntersections...");
+ // Finally do an intersection test
+ if (edge.plane.findIntersections(planetModel, compareEdge.plane, oneBoundary.plane, otherBoundary.plane, oneCompareBoundary.plane, otherCompareBoundary.plane).length > 0) {
+ throw new IllegalArgumentException("polygon has intersecting edges");
+ }
+ }
+ }
+ }
+ }
+ */
+
// Starting state:
// The stopping point
Edge stoppingPoint = edgeBuffer.pickOne();
@@ -997,7 +1060,13 @@ public class GeoPolygonFactory {
System.out.println(" "+p);
}
*/
+
+ // We need to detect backtracks, and also situations where someone has tried to stitch together multiple segments into one long arc (> 180 degrees).
+ // To do this, every time we extend by a coplanar segment, we compute the total arc distance to the new endpoint, as
+ // well as a sum of the arc distances we've accumulated as we march forward. If these two numbers disagree, then
+ // we know there has been a backtrack or other anomaly.
+ // extend the edge, we compute the distance along the
final Edge startEdge = new Edge(pointList.get(startPlaneStartIndex), pointList.get(startPlaneEndIndex), startPlane, internalEdges.get(startPlaneStartIndex));
// Fill in the EdgeBuffer by walking around creating more stuff
Edge currentEdge = startEdge;
@@ -1027,15 +1096,21 @@ public class GeoPolygonFactory {
if (currentEdge.plane.evaluateIsZero(newPoint)) {
// The new point is colinear with the current edge. We'll have to look for the first point that isn't.
int checkPointIndex = -1;
+ // Compute the arc distance before we try to extend
+ double accumulatedDistance = 0.0;
final Plane checkPlane = new Plane(pointList.get(startIndex), newPoint);
for (int i = 0; i < pointList.size(); i++) {
final int index = getLegalIndex(startIndex - 1 - i, pointList.size());
if (!checkPlane.evaluateIsZero(pointList.get(index))) {
checkPointIndex = index;
break;
+ } else {
+ accumulatedDistance += pointList.get(getLegalIndex(index+1, pointList.size())).arcDistance(pointList.get(index));
+ final double actualDistance = pointList.get(getLegalIndex(startIndex-1, pointList.size())).arcDistance(pointList.get(index));
+ if (Math.abs(actualDistance - accumulatedDistance) >= Vector.MINIMUM_RESOLUTION) {
+ throw new IllegalArgumentException("polygon backtracks over itself");
+ }
}
- }
- if (checkPointIndex == -1) {
throw new IllegalArgumentException("polygon is illegal (linear)");
}
pointToPresent = pointList.get(checkPointIndex);
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/414bdea9/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java
index 33840da..2da93cf 100755
--- a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java
+++ b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java
@@ -378,4 +378,44 @@ shape:
final GeoPolygon p = GeoPolygonFactory.makeGeoPolygon(PlanetModel.WGS84, points, null);
}
+ @Test
+ public void testPolygonIntersectionFailure1() {
+ final PlanetModel pm = PlanetModel.WGS84;
+ //[junit4] > Throwable #1: java.lang.AssertionError: invalid hits for shape=GeoCompositeMembershipShape:
+ //{[GeoConvexPolygon: {planetmodel=PlanetModel.WGS84, points=
+ //[[lat=0.2669499069140678, lon=-0.31249902828113546([X=0.9186752334433793, Y=-0.2968103450748192, Z=0.2640238502385029])],
+ //[lat=1.538559019421765, lon=0.0([X=0.03215971057004023, Y=0.0, Z=0.9972473454662941])],
+ //[lat=-0.5516194571595735, lon=0.0([X=0.8518418310766115, Y=0.0, Z=-0.5241686363384119])]], internalEdges={2}},
+ //GeoConvexPolygon: {planetmodel=PlanetModel.WGS84, points=
+ //[[lat=0.0, lon=-3.141592653589793([X=-1.0011188539924791, Y=-1.226017000107956E-16, Z=0.0])],
+ //[lat=-1.5707963267948966, lon=-2.2780601241431375([X=-3.9697069088211677E-17, Y=-4.644115432258393E-17, Z=-0.997762292022105])],
+ //[lat=0.2669499069140678, lon=-0.31249902828113546([X=0.9186752334433793, Y=-0.2968103450748192, Z=0.2640238502385029])]], internalEdges={2}},
+ //GeoConvexPolygon: {planetmodel=PlanetModel.WGS84, points=
+ //[[lat=0.2669499069140678, lon=-0.31249902828113546([X=0.9186752334433793, Y=-0.2968103450748192, Z=0.2640238502385029])],
+ //[lat=-0.5516194571595735, lon=0.0([X=0.8518418310766115, Y=0.0, Z=-0.5241686363384119])],
+ //[lat=0.0, lon=-3.141592653589793([X=-1.0011188539924791, Y=-1.226017000107956E-16, Z=0.0])]], internalEdges={0, 2}}]}
+
+ // Build the polygon
+ //[[lat=-0.5516194571595735, lon=0.0([X=0.8518418310766115, Y=0.0, Z=-0.5241686363384119])],
+ //[lat=0.0, lon=-3.141592653589793([X=-1.0011188539924791, Y=-1.226017000107956E-16, Z=0.0])],
+ //[lat=-1.5707963267948966, lon=-2.2780601241431375([X=-3.9697069088211677E-17, Y=-4.644115432258393E-17, Z=-0.997762292022105])],
+ //[lat=0.2669499069140678, lon=-0.31249902828113546([X=0.9186752334433793, Y=-0.2968103450748192, Z=0.2640238502385029])],
+ //[lat=1.538559019421765, lon=0.0([X=0.03215971057004023, Y=0.0, Z=0.9972473454662941])]]
+ List<GeoPoint> polyPoints = new ArrayList<>();
+ polyPoints.add(new GeoPoint(pm, -0.5516194571595735, 0.0));
+ polyPoints.add(new GeoPoint(pm, 0.0, -3.141592653589793));
+ polyPoints.add(new GeoPoint(pm, -1.5707963267948966, -2.2780601241431375));
+ polyPoints.add(new GeoPoint(pm, 0.2669499069140678, -0.31249902828113546));
+ polyPoints.add(new GeoPoint(pm, 1.538559019421765, 0.0));
+ // Make sure we catch the backtrack
+ boolean backtracks = false;
+ try {
+ GeoPolygonFactory.makeGeoPolygon(pm, polyPoints, 4, null);
+ } catch (IllegalArgumentException e) {
+ backtracks = true;
+ }
+ assertTrue(backtracks);
+
+ }
+
}