You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by kw...@apache.org on 2018/04/13 16:28:51 UTC
lucene-solr:branch_7x: LUCENE-8251: Handle near-parallelness with
envelope plane by a progressive adjoining point distance increment,
up to 100 iterations. Then, give up and assume a crossing.
Repository: lucene-solr
Updated Branches:
refs/heads/branch_7x 6d771dcc9 -> 368bdf36c
LUCENE-8251: Handle near-parallelness with envelope plane by a progressive adjoining point distance increment, up to 100 iterations. Then, give up and assume a crossing.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/368bdf36
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/368bdf36
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/368bdf36
Branch: refs/heads/branch_7x
Commit: 368bdf36c117dafb6c793d787f1863e219352c31
Parents: 6d771dc
Author: Karl Wright <Da...@gmail.com>
Authored: Fri Apr 13 12:05:42 2018 -0400
Committer: Karl Wright <Da...@gmail.com>
Committed: Fri Apr 13 12:28:39 2018 -0400
----------------------------------------------------------------------
.../spatial3d/geom/GeoComplexPolygon.java | 82 +++++++++++++-------
.../lucene/spatial3d/geom/GeoPolygonTest.java | 1 -
.../spatial3d/geom/RandomGeoPolygonTest.java | 1 -
3 files changed, 54 insertions(+), 30 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/368bdf36/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java
index b6b6577..73ed92e 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java
@@ -977,15 +977,18 @@ class GeoComplexPolygon extends GeoBasePolygon {
for (final GeoPoint intersection : intersections) {
if (edge.startPlane.strictlyWithin(intersection) && edge.endPlane.strictlyWithin(intersection)) {
// It's unique, so assess it
- crossings += edgeCrossesEnvelope(edge.plane, intersection)?1:0;
+ crossings += edgeCrossesEnvelope(edge.plane, intersection, envelopePlane)?1:0;
}
}
}
return crossings;
}
- private boolean edgeCrossesEnvelope(final Plane edgePlane, final GeoPoint intersectionPoint) {
- final GeoPoint[] adjoiningPoints = findAdjoiningPoints(edgePlane, intersectionPoint);
+ private boolean edgeCrossesEnvelope(final Plane edgePlane, final GeoPoint intersectionPoint, final Plane envelopePlane) {
+ final GeoPoint[] adjoiningPoints = findAdjoiningPoints(edgePlane, intersectionPoint, envelopePlane);
+ if (adjoiningPoints == null) {
+ return true;
+ }
int withinCount = 0;
for (final GeoPoint adjoining : adjoiningPoints) {
if (plane.evaluateIsZero(adjoining) && bound.isWithin(adjoining)) {
@@ -1070,15 +1073,18 @@ class GeoComplexPolygon extends GeoBasePolygon {
for (final GeoPoint intersection : intersections) {
if (edge.startPlane.strictlyWithin(intersection) && edge.endPlane.strictlyWithin(intersection)) {
// It's unique, so assess it
- crossings += edgeCrossesEnvelope(edge.plane, intersection)?1:0;
+ crossings += edgeCrossesEnvelope(edge.plane, intersection, envelopePlane)?1:0;
}
}
}
return crossings;
}
- private boolean edgeCrossesEnvelope(final Plane edgePlane, final GeoPoint intersectionPoint) {
- final GeoPoint[] adjoiningPoints = findAdjoiningPoints(edgePlane, intersectionPoint);
+ private boolean edgeCrossesEnvelope(final Plane edgePlane, final GeoPoint intersectionPoint, final Plane envelopePlane) {
+ final GeoPoint[] adjoiningPoints = findAdjoiningPoints(edgePlane, intersectionPoint, envelopePlane);
+ if (adjoiningPoints == null) {
+ return true;
+ }
int withinCount = 0;
for (final GeoPoint adjoining : adjoiningPoints) {
if (plane.evaluateIsZero(adjoining) && bound1.isWithin(adjoining) && bound2.isWithin(adjoining)) {
@@ -1325,10 +1331,10 @@ class GeoComplexPolygon extends GeoBasePolygon {
break;
}
}
-
- System.out.println("");
- System.out.println("Considering edge "+(edge.startPoint)+" -> "+(edge.endPoint));
*/
+
+ //System.out.println("");
+ //System.out.println("Considering edge "+(edge.startPoint)+" -> "+(edge.endPoint));
// Some edges are going to be given to us even when there's no real intersection, so do that as a sanity check, first.
final GeoPoint[] travelCrossings = travelPlane.findIntersections(planetModel, edge.plane, checkPointCutoffPlane, checkPointOtherCutoffPlane, edge.startPlane, edge.endPlane);
@@ -1411,8 +1417,8 @@ class GeoComplexPolygon extends GeoBasePolygon {
continue;
}
// It's unique, so assess it
- //System.out.println(" Assessing travel envelope intersection point "+intersection+"...");
- crossings += edgeCrossesEnvelope(edge.plane, intersection)?1:0;
+ //System.out.println(" Assessing travel envelope intersection point "+intersection+", travelPlane distance="+travelPlane.evaluate(intersection)+"...");
+ crossings += edgeCrossesEnvelope(edge.plane, intersection, travelEnvelopePlane)?1:0;
}
}
}
@@ -1420,8 +1426,8 @@ class GeoComplexPolygon extends GeoBasePolygon {
for (final GeoPoint intersection : testPointIntersections) {
if (edge.startPlane.strictlyWithin(intersection) && edge.endPlane.strictlyWithin(intersection)) {
// It's unique, so assess it
- //System.out.println(" Assessing testpoint envelope intersection point "+intersection+"...");
- crossings += edgeCrossesEnvelope(edge.plane, intersection)?1:0;
+ //System.out.println(" Assessing testpoint envelope intersection point "+intersection+", testPointPlane distance="+testPointPlane.evaluate(intersection)+"...");
+ crossings += edgeCrossesEnvelope(edge.plane, intersection, testPointEnvelopePlane)?1:0;
}
}
}
@@ -1430,16 +1436,20 @@ class GeoComplexPolygon extends GeoBasePolygon {
/** Return true if the edge crosses the envelope plane, given the envelope intersection point.
*/
- private boolean edgeCrossesEnvelope(final Plane edgePlane, final GeoPoint intersectionPoint) {
- final GeoPoint[] adjoiningPoints = findAdjoiningPoints(edgePlane, intersectionPoint);
+ private boolean edgeCrossesEnvelope(final Plane edgePlane, final GeoPoint intersectionPoint, final Plane envelopePlane) {
+ final GeoPoint[] adjoiningPoints = findAdjoiningPoints(edgePlane, intersectionPoint, envelopePlane);
+ if (adjoiningPoints == null) {
+ // Couldn't find good adjoining points, so just assume there is a crossing.
+ return true;
+ }
int withinCount = 0;
for (final GeoPoint adjoining : adjoiningPoints) {
if ((travelPlane.evaluateIsZero(adjoining) && checkPointCutoffPlane.isWithin(adjoining) && checkPointOtherCutoffPlane.isWithin(adjoining)) ||
(testPointPlane.evaluateIsZero(adjoining) && testPointCutoffPlane.isWithin(adjoining) && testPointOtherCutoffPlane.isWithin(adjoining))) {
- //System.out.println(" Adjoining point "+adjoining+" (dist = "+intersectionPoint.linearDistance(adjoining)+") is within");
+ //System.out.println(" Adjoining point "+adjoining+" (intersection dist = "+intersectionPoint.linearDistance(adjoining)+") is within");
withinCount++;
} else {
- //System.out.println(" Adjoining point "+adjoining+" (dist = "+intersectionPoint.linearDistance(adjoining)+") is not within");
+ //System.out.println(" Adjoining point "+adjoining+" (intersection dist = "+intersectionPoint.linearDistance(adjoining)+"; travelPlane dist="+travelPlane.evaluate(adjoining)+"; testPointPlane dist="+testPointPlane.evaluate(adjoining)+") is not within");
}
}
return (withinCount & 1) != 0;
@@ -1450,23 +1460,39 @@ class GeoComplexPolygon extends GeoBasePolygon {
/** This is the amount we go, roughly, in both directions, to find adjoining points to test. If we go too far,
* we might miss a transition, but if we go too little, we might not see it either due to numerical issues.
*/
- private final static double DELTA_DISTANCE = Vector.MINIMUM_RESOLUTION;// * 0.5;
+ private final static double DELTA_DISTANCE = Vector.MINIMUM_RESOLUTION;
+ /** This is the maximum number of iterations. If we get this high, effectively the planes are parallel, and we
+ * treat that as a crossing.
+ */
+ private final static int MAX_ITERATIONS = 100;
+ /** This is the amount off of the envelope plane that we count as "enough" for a valid crossing assessment. */
+ private final static double OFF_PLANE_AMOUNT = Vector.MINIMUM_RESOLUTION * 0.1;
/** Given a point on the plane and the ellipsoid, this method looks for a pair of adjoining points on either side of the plane, which are
* about MINIMUM_RESOLUTION away from the given point. This only works for planes which go through the center of the world.
+ * Returns null if the planes are effectively parallel and reasonable adjoining points cannot be determined.
*/
- private GeoPoint[] findAdjoiningPoints(final Plane plane, final GeoPoint pointOnPlane) {
+ private GeoPoint[] findAdjoiningPoints(final Plane plane, final GeoPoint pointOnPlane, final Plane envelopePlane) {
// Compute a normalized perpendicular vector
final Vector perpendicular = new Vector(plane, pointOnPlane);
- // Compute two new points along this vector from the original
- final GeoPoint pointA = planetModel.createSurfacePoint(pointOnPlane.x + perpendicular.x * DELTA_DISTANCE,
- pointOnPlane.y + perpendicular.y * DELTA_DISTANCE,
- pointOnPlane.z + perpendicular.z * DELTA_DISTANCE);
- final GeoPoint pointB = planetModel.createSurfacePoint(pointOnPlane.x - perpendicular.x * DELTA_DISTANCE,
- pointOnPlane.y - perpendicular.y * DELTA_DISTANCE,
- pointOnPlane.z - perpendicular.z * DELTA_DISTANCE);
- //System.out.println("Distance: "+computeSquaredDistance(rval[0], pointOnPlane)+" and "+computeSquaredDistance(rval[1], pointOnPlane));
- return new GeoPoint[]{pointA, pointB};
+ double distanceFactor = 0.0;
+ for (int i = 0; i < MAX_ITERATIONS; i++) {
+ distanceFactor += DELTA_DISTANCE;
+ // Compute two new points along this vector from the original
+ final GeoPoint pointA = planetModel.createSurfacePoint(pointOnPlane.x + perpendicular.x * distanceFactor,
+ pointOnPlane.y + perpendicular.y * distanceFactor,
+ pointOnPlane.z + perpendicular.z * distanceFactor);
+ final GeoPoint pointB = planetModel.createSurfacePoint(pointOnPlane.x - perpendicular.x * distanceFactor,
+ pointOnPlane.y - perpendicular.y * distanceFactor,
+ pointOnPlane.z - perpendicular.z * distanceFactor);
+ if (Math.abs(envelopePlane.evaluate(pointA)) > OFF_PLANE_AMOUNT && Math.abs(envelopePlane.evaluate(pointB)) > OFF_PLANE_AMOUNT) {
+ //System.out.println("Distance: "+computeSquaredDistance(rval[0], pointOnPlane)+" and "+computeSquaredDistance(rval[1], pointOnPlane));
+ return new GeoPoint[]{pointA, pointB};
+ }
+ // Loop back around and use a bigger delta
+ }
+ // Had to abort, so return null.
+ return null;
}
private static double computeSquaredDistance(final GeoPoint checkPoint, final GeoPoint intersectionPoint) {
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/368bdf36/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 86f5694..524475a 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
@@ -1570,7 +1570,6 @@ shape:
}
@Test
- @AwaitsFix(bugUrl="https://issues.apache.org/jira/browse/LUCENE-8251")
public void testLUCENE8251() {
//POLYGON((135.63207358036593 -51.43541696593334,113.00782694696038 -58.984559858566556,0.0 -3.68E-321,-66.33598777585381 -7.382056816201731,135.63207358036593 -51.43541696593334))
final List<GeoPoint> points = new ArrayList<>();
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/368bdf36/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/RandomGeoPolygonTest.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/RandomGeoPolygonTest.java b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/RandomGeoPolygonTest.java
index b6364e0..a181d17 100644
--- a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/RandomGeoPolygonTest.java
+++ b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/RandomGeoPolygonTest.java
@@ -92,7 +92,6 @@ public class RandomGeoPolygonTest extends RandomGeo3dShapeGenerator {
* biased doubles.
*/
@Test
- @AwaitsFix(bugUrl="https://issues.apache.org/jira/browse/LUCENE-8251")
@Repeat(iterations = 10)
public void testComparePolygons() {
final PlanetModel planetModel = randomPlanetModel();