lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kwri...@apache.org
Subject [1/2] lucene-solr:master: 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.
Date Tue, 10 Apr 2018 00:14:21 GMT
Repository: lucene-solr
Updated Branches:
  refs/heads/master a12d39887 -> 1cd859713


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/9bd6d130
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/9bd6d130
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/9bd6d130

Branch: refs/heads/master
Commit: 9bd6d1305c8bbccf2f3a22079a523b483325e9eb
Parents: bd8fe72
Author: Karl Wright <DaddyWri@gmail.com>
Authored: Mon Apr 9 20:13:12 2018 -0400
Committer: Karl Wright <DaddyWri@gmail.com>
Committed: Mon Apr 9 20:13:12 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/9bd6d130/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/9bd6d130/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/9bd6d130/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));
+  }
   
 }


Mime
View raw message