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/10 00:15:26 UTC
lucene-solr:branch_7x: LUCENE-8245: Don't rely only on 'intersects'
code to determine whether we should bother looking for crossings;
also see if endpoints lie on travel planes.
Repository: lucene-solr
Updated Branches:
refs/heads/branch_7x 7009f1cad -> 2ef5c946c
LUCENE-8245: Don't rely only on 'intersects' code to determine whether we should bother looking for crossings; also see if endpoints lie on travel planes.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/2ef5c946
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/2ef5c946
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/2ef5c946
Branch: refs/heads/branch_7x
Commit: 2ef5c946c3e19a49c712047f0825c26d5db09cf6
Parents: 7009f1c
Author: Karl Wright <Da...@gmail.com>
Authored: Mon Apr 9 20:13:12 2018 -0400
Committer: Karl Wright <Da...@gmail.com>
Committed: Mon Apr 9 20:15:17 2018 -0400
----------------------------------------------------------------------
.../spatial3d/geom/GeoComplexPolygon.java | 46 +++++++++++++++-----
.../org/apache/lucene/spatial3d/geom/Plane.java | 5 ++-
.../lucene/spatial3d/geom/GeoPolygonTest.java | 17 ++++++++
3 files changed, 55 insertions(+), 13 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/2ef5c946/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 f64755c..5c3521c 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
@@ -935,8 +935,10 @@ class GeoComplexPolygon extends GeoBasePolygon {
// 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[] planeCrossings = plane.findIntersections(planetModel, edge.plane, bound, edge.startPlane, edge.endPlane);
if (planeCrossings != null && planeCrossings.length == 0) {
- // No actual crossing
- return true;
+ // Sometimes on the hairy edge an intersection will be missed. This check finds those.
+ if (!plane.evaluateIsZero(edge.startPoint) && !plane.evaluateIsZero(edge.endPoint)) {
+ return true;
+ }
}
// Determine crossings of this edge against all inside/outside planes. There's no further need to look at the actual travel plane itself.
@@ -1021,8 +1023,10 @@ class GeoComplexPolygon extends GeoBasePolygon {
// 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[] planeCrossings = plane.findIntersections(planetModel, edge.plane, bound1, bound2, edge.startPlane, edge.endPlane);
if (planeCrossings != null && planeCrossings.length == 0) {
- // No actual crossing
- return true;
+ // Sometimes on the hairy edge an intersection will be missed. This check finds those.
+ if (!plane.evaluateIsZero(edge.startPoint) && !plane.evaluateIsZero(edge.endPoint)) {
+ return true;
+ }
}
// Determine crossings of this edge against all inside/outside planes. There's no further need to look at the actual travel plane itself.
@@ -1248,8 +1252,6 @@ class GeoComplexPolygon extends GeoBasePolygon {
}
seenEdges.add(edge);
- //System.out.println("Considering edge "+(edge.startPoint)+" -> "+(edge.endPoint));
-
// We've never seen this edge before. Evaluate it in the context of inner and outer planes.
computeInsideOutside();
@@ -1273,14 +1275,36 @@ class GeoComplexPolygon extends GeoBasePolygon {
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);
if (travelCrossings != null && travelCrossings.length == 0) {
final GeoPoint[] testPointCrossings = testPointPlane.findIntersections(planetModel, edge.plane, testPointCutoffPlane, testPointOtherCutoffPlane, edge.startPlane, edge.endPlane);
if (testPointCrossings != null && testPointCrossings.length == 0) {
- return true;
+ // As a last resort, see if the edge endpoints are on either plane. This is sometimes necessary because the
+ // intersection computation logic might not detect near-miss edges otherwise.
+ if (!travelPlane.evaluateIsZero(edge.startPoint) && !travelPlane.evaluateIsZero(edge.endPoint) &&
+ !testPointPlane.evaluateIsZero(edge.startPoint) && !testPointPlane.evaluateIsZero(edge.endPoint)) {
+ return true;
+ }
}
}
+
+ /*
+ System.out.println(
+ " start point travel dist="+travelPlane.evaluate(edge.startPoint)+"; end point travel dist="+travelPlane.evaluate(edge.endPoint));
+ System.out.println(
+ " start point travel above dist="+travelAbovePlane.evaluate(edge.startPoint)+"; end point travel above dist="+travelAbovePlane.evaluate(edge.endPoint));
+ System.out.println(
+ " start point travel below dist="+travelBelowPlane.evaluate(edge.startPoint)+"; end point travel below dist="+travelBelowPlane.evaluate(edge.endPoint));
+ System.out.println(
+ " start point testpoint dist="+testPointPlane.evaluate(edge.startPoint)+"; end point testpoint dist="+testPointPlane.evaluate(edge.endPoint));
+ System.out.println(
+ " start point testpoint above dist="+testPointAbovePlane.evaluate(edge.startPoint)+"; end point testpoint above dist="+testPointAbovePlane.evaluate(edge.endPoint));
+ System.out.println(
+ " start point testpoint below dist="+testPointBelowPlane.evaluate(edge.startPoint)+"; end point testpoint below dist="+testPointBelowPlane.evaluate(edge.endPoint));
+ */
// Determine crossings of this edge against all inside/outside planes. There's no further need to look at the actual travel plane itself.
final GeoPoint[] travelInnerCrossings = travelInsidePlane.findCrossings(planetModel, edge.plane, checkPointCutoffPlane, insideTravelCutoffPlane, edge.startPlane, edge.endPlane);
@@ -1294,13 +1318,13 @@ class GeoComplexPolygon extends GeoBasePolygon {
if (travelInnerCrossings != null) {
for (final GeoPoint crossing : travelInnerCrossings) {
- //System.out.println(" Travel inner point "+crossing);
+ //System.out.println(" Travel inner point "+crossing+"; edgeplane="+edge.plane.evaluate(crossing)+"; travelInsidePlane="+travelInsidePlane.evaluate(crossing)+"; edgestartplane="+edge.startPlane.evaluate(crossing)+"; edgeendplane="+edge.endPlane.evaluate(crossing));
countingHash.add(crossing);
}
}
if (testPointInnerCrossings != null) {
for (final GeoPoint crossing : testPointInnerCrossings) {
- //System.out.println(" Test point inner point "+crossing);
+ //System.out.println(" Test point inner point "+crossing+"; edgeplane="+edge.plane.evaluate(crossing)+"; testPointInsidePlane="+testPointInsidePlane.evaluate(crossing)+"; edgestartplane="+edge.startPlane.evaluate(crossing)+"; edgeendplane="+edge.endPlane.evaluate(crossing));
countingHash.add(crossing);
}
}
@@ -1310,13 +1334,13 @@ class GeoComplexPolygon extends GeoBasePolygon {
countingHash.clear();
if (travelOuterCrossings != null) {
for (final GeoPoint crossing : travelOuterCrossings) {
- //System.out.println(" Travel outer point "+crossing);
+ //System.out.println(" Travel outer point "+crossing+"; edgeplane="+edge.plane.evaluate(crossing)+"; travelOutsidePlane="+travelOutsidePlane.evaluate(crossing)+"; edgestartplane="+edge.startPlane.evaluate(crossing)+"; edgeendplane="+edge.endPlane.evaluate(crossing));
countingHash.add(crossing);
}
}
if (testPointOuterCrossings != null) {
for (final GeoPoint crossing : testPointOuterCrossings) {
- //System.out.println(" Test point outer point "+crossing);
+ //System.out.println(" Test point outer point "+crossing+"; edgeplane="+edge.plane.evaluate(crossing)+"; testPointOutsidePlane="+testPointOutsidePlane.evaluate(crossing)+"; edgestartplane="+edge.startPlane.evaluate(crossing)+"; edgeendplane="+edge.endPlane.evaluate(crossing));
countingHash.add(crossing);
}
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/2ef5c946/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Plane.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Plane.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Plane.java
index 34a2fce..b47cffd 100755
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Plane.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Plane.java
@@ -23,8 +23,9 @@ package org.apache.lucene.spatial3d.geom;
* @lucene.experimental
*/
public class Plane extends Vector {
- /** For plane envelopes, we need a small distance that can't lead to numerical confusion. */
- public final static double MINIMUM_PLANE_OFFSET = MINIMUM_RESOLUTION * 1.1;
+ /** For plane envelopes, we need a small distance that can't lead to numerical confusion. This spacing is large enough to
+ * avoid numerical confusion, but still permit all points within the envelope to belong to one or another plane. */
+ public final static double MINIMUM_PLANE_OFFSET = MINIMUM_RESOLUTION * 2.0;
/** An array with no points in it */
public final static GeoPoint[] NO_POINTS = new GeoPoint[0];
/** An array with no bounds in it */
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/2ef5c946/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 d1e6688..ee2217d 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
@@ -1501,5 +1501,22 @@ shape:
final GeoPoint point = new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-6.782152464351765E-11), Geo3DUtil.fromDegrees(91.60559215160585));
assertTrue(polygon.isWithin(point) == largePolygon.isWithin(point));
}
+
+ @Test
+ public void testLUCENE8245() {
+ //POLYGON((-70.19447784626787 -83.117346007187,0.0 2.8E-322,-139.99870438810106 7.994601469571884,-143.14292702670522 -18.500141088122664,-158.7373186858464 -35.42942085357812,-70.19447784626787 -83.117346007187))
+ final List<GeoPoint> points = new ArrayList<>();
+ points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-83.117346007187), Geo3DUtil.fromDegrees(-70.19447784626787)));
+ points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(2.8E-322), Geo3DUtil.fromDegrees(0.0)));
+ points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(7.994601469571884), Geo3DUtil.fromDegrees(-139.99870438810106)));
+ points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-18.500141088122664), Geo3DUtil.fromDegrees(-143.14292702670522)));
+ points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-35.42942085357812), Geo3DUtil.fromDegrees(-158.7373186858464)));
+ final GeoPolygonFactory.PolygonDescription description = new GeoPolygonFactory.PolygonDescription(points);
+ final GeoPolygon polygon = GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE, description);
+ final GeoPolygon largePolygon = GeoPolygonFactory.makeLargeGeoPolygon(PlanetModel.SPHERE, Collections.singletonList(description));
+ //POINT(-1.91633079336513E-11 12.282452091883385)
+ final GeoPoint point = new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(12.282452091883385), Geo3DUtil.fromDegrees(-1.91633079336513E-11));
+ assertTrue(polygon.isWithin(point) == largePolygon.isWithin(point));
+ }
}