lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kwri...@apache.org
Subject lucene-solr:master: LUCENE-7290: Add support for calculating bounds for intersections.
Date Fri, 20 May 2016 17:50:15 GMT
Repository: lucene-solr
Updated Branches:
  refs/heads/master 59e6e3bac -> 908225d17


LUCENE-7290: Add support for calculating bounds for intersections.


Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/908225d1
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/908225d1
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/908225d1

Branch: refs/heads/master
Commit: 908225d1749a9c0b61d92fbc940c9031cd30e361
Parents: 59e6e3b
Author: Karl Wright <DaddyWri@gmail.com>
Authored: Fri May 20 13:49:13 2016 -0400
Committer: Karl Wright <DaddyWri@gmail.com>
Committed: Fri May 20 13:49:13 2016 -0400

----------------------------------------------------------------------
 .../apache/lucene/spatial3d/geom/Bounds.java    |  11 +
 .../spatial3d/geom/GeoComplexPolygon.java       |   2 +-
 .../spatial3d/geom/GeoLongitudeSlice.java       |   1 +
 .../spatial3d/geom/GeoNorthRectangle.java       |   1 +
 .../lucene/spatial3d/geom/GeoRectangle.java     |   1 +
 .../spatial3d/geom/GeoSouthRectangle.java       |   1 +
 .../spatial3d/geom/GeoWideLongitudeSlice.java   |   1 +
 .../spatial3d/geom/GeoWideNorthRectangle.java   |   1 +
 .../lucene/spatial3d/geom/GeoWideRectangle.java |   1 +
 .../spatial3d/geom/GeoWideSouthRectangle.java   |   1 +
 .../lucene/spatial3d/geom/LatLonBounds.java     |   6 +
 .../org/apache/lucene/spatial3d/geom/Plane.java | 216 +++++++++++++++++++
 .../apache/lucene/spatial3d/geom/XYZBounds.java |   9 +-
 .../apache/lucene/spatial3d/TestGeo3DPoint.java |   3 +-
 .../lucene/spatial3d/geom/GeoBBoxTest.java      |  11 +
 .../lucene/spatial3d/geom/GeoCircleTest.java    |   4 -
 .../lucene/spatial3d/geom/GeoPolygonTest.java   |   6 -
 17 files changed, 263 insertions(+), 13 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/908225d1/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Bounds.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Bounds.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Bounds.java
index 4f7c663..866068a 100755
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Bounds.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Bounds.java
@@ -66,6 +66,17 @@ public interface Bounds {
     final Plane verticalPlane,
     final Membership... bounds);
 
+  /** Add the intersection between two planes to the bounds description.
+   * Where the shape has intersecting planes, it is better to use this method
+   * than just adding the point, since this method takes each plane's error envelope into
+   * account.
+   *@param planetModel is the planet model.
+   *@param plane1 is the first plane.
+   *@param plane2 is the second plane.
+   *@param bounds are the membership bounds for the intersection.
+   */
+  public Bounds addIntersection(final PlanetModel planetModel, final Plane plane1, final
Plane plane2, final Membership... bounds);
+
   /** Add a single point.
    *@param point is the point.
    *@return the updated Bounds object.

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/908225d1/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 694c96b..8528471 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
@@ -436,7 +436,7 @@ class GeoComplexPolygon extends GeoBasePolygon {
       this.planeBounds = new XYZBounds();
       this.planeBounds.addPoint(startPoint);
       this.planeBounds.addPoint(endPoint);
-      this.plane.recordBounds(pm, this.planeBounds, this.startPlane, this.endPlane);
+      this.planeBounds.addPlane(pm, this.plane, this.startPlane, this.endPlane);
       //System.err.println("Recording edge "+this+" from "+startPoint+" to "+endPoint+";
bounds = "+planeBounds);
     }
   }

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/908225d1/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoLongitudeSlice.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoLongitudeSlice.java
b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoLongitudeSlice.java
index 263ff47..294d4e8 100755
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoLongitudeSlice.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoLongitudeSlice.java
@@ -133,6 +133,7 @@ class GeoLongitudeSlice extends GeoBaseBBox {
     bounds
       .addVerticalPlane(planetModel, leftLon, leftPlane, rightPlane)
       .addVerticalPlane(planetModel, rightLon, rightPlane, leftPlane)
+      .addIntersection(planetModel, rightPlane, leftPlane)
       .addPoint(planetModel.NORTH_POLE)
       .addPoint(planetModel.SOUTH_POLE);
   }

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/908225d1/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoNorthRectangle.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoNorthRectangle.java
b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoNorthRectangle.java
index 6015e5b..27422d2 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoNorthRectangle.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoNorthRectangle.java
@@ -181,6 +181,7 @@ class GeoNorthRectangle extends GeoBaseBBox {
       .addHorizontalPlane(planetModel, bottomLat, bottomPlane, leftPlane, rightPlane)
       .addVerticalPlane(planetModel, leftLon, leftPlane, bottomPlane, rightPlane)
       .addVerticalPlane(planetModel, rightLon, rightPlane, bottomPlane, leftPlane)
+      .addIntersection(planetModel, rightPlane, leftPlane, bottomPlane)
       .addPoint(LLHC).addPoint(LRHC).addPoint(planetModel.NORTH_POLE);
   }
 

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/908225d1/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoRectangle.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoRectangle.java
b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoRectangle.java
index 4be5d84..3d0a97d 100755
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoRectangle.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoRectangle.java
@@ -203,6 +203,7 @@ class GeoRectangle extends GeoBaseBBox {
       .addVerticalPlane(planetModel, rightLon, rightPlane, topPlane, bottomPlane, leftPlane)
       .addHorizontalPlane(planetModel, bottomLat, bottomPlane, topPlane, leftPlane, rightPlane)
       .addVerticalPlane(planetModel, leftLon, leftPlane, topPlane, bottomPlane, rightPlane)
+      .addIntersection(planetModel, leftPlane, rightPlane, topPlane, bottomPlane)
       .addPoint(ULHC).addPoint(URHC).addPoint(LLHC).addPoint(LRHC);
   }
 

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/908225d1/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoSouthRectangle.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoSouthRectangle.java
b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoSouthRectangle.java
index 2eb071c..ed380e1 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoSouthRectangle.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoSouthRectangle.java
@@ -179,6 +179,7 @@ class GeoSouthRectangle extends GeoBaseBBox {
       .addHorizontalPlane(planetModel, topLat, topPlane, leftPlane, rightPlane)
       .addVerticalPlane(planetModel, leftLon, leftPlane, topPlane, rightPlane)
       .addVerticalPlane(planetModel, rightLon, rightPlane, topPlane, leftPlane)
+      .addIntersection(planetModel, rightPlane, leftPlane, topPlane)
       .addPoint(URHC).addPoint(ULHC).addPoint(planetModel.SOUTH_POLE);
   }
 

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/908225d1/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoWideLongitudeSlice.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoWideLongitudeSlice.java
b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoWideLongitudeSlice.java
index 2ef3c8b..f208266 100755
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoWideLongitudeSlice.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoWideLongitudeSlice.java
@@ -139,6 +139,7 @@ class GeoWideLongitudeSlice extends GeoBaseBBox {
     bounds.isWide()
       .addVerticalPlane(planetModel, leftLon, leftPlane)
       .addVerticalPlane(planetModel, rightLon, rightPlane)
+      .addIntersection(planetModel, leftPlane, rightPlane)
       .addPoint(planetModel.NORTH_POLE)
       .addPoint(planetModel.SOUTH_POLE);
   }

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/908225d1/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoWideNorthRectangle.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoWideNorthRectangle.java
b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoWideNorthRectangle.java
index 1a5603f..849d4e9 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoWideNorthRectangle.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoWideNorthRectangle.java
@@ -183,6 +183,7 @@ class GeoWideNorthRectangle extends GeoBaseBBox {
       .addHorizontalPlane(planetModel, bottomLat, bottomPlane, eitherBound)
       .addVerticalPlane(planetModel, leftLon, leftPlane, bottomPlane)
       .addVerticalPlane(planetModel, rightLon, rightPlane, bottomPlane)
+      .addIntersection(planetModel, leftPlane, rightPlane, bottomPlane)
       .addPoint(LLHC).addPoint(LRHC).addPoint(planetModel.NORTH_POLE);
   }
 

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/908225d1/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoWideRectangle.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoWideRectangle.java
b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoWideRectangle.java
index 031dcaa..53c8c59 100755
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoWideRectangle.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoWideRectangle.java
@@ -212,6 +212,7 @@ class GeoWideRectangle extends GeoBaseBBox {
       .addVerticalPlane(planetModel, rightLon, rightPlane, topPlane, bottomPlane)
       .addHorizontalPlane(planetModel, bottomLat, bottomPlane, topPlane, eitherBound)
       .addVerticalPlane(planetModel, leftLon, leftPlane, topPlane, bottomPlane)
+      .addIntersection(planetModel, leftPlane, rightPlane, topPlane, bottomPlane)
       .addPoint(ULHC).addPoint(URHC).addPoint(LRHC).addPoint(LLHC);
   }
 

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/908225d1/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoWideSouthRectangle.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoWideSouthRectangle.java
b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoWideSouthRectangle.java
index 3f1d232..29d89c5 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoWideSouthRectangle.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoWideSouthRectangle.java
@@ -182,6 +182,7 @@ class GeoWideSouthRectangle extends GeoBaseBBox {
       .addHorizontalPlane(planetModel, topLat, topPlane, eitherBound)
       .addVerticalPlane(planetModel, rightLon, rightPlane, topPlane)
       .addVerticalPlane(planetModel, leftLon, leftPlane, topPlane)
+      .addIntersection(planetModel, leftPlane, rightPlane, topPlane)
       .addPoint(ULHC).addPoint(URHC).addPoint(planetModel.SOUTH_POLE);
   }
 

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/908225d1/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/LatLonBounds.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/LatLonBounds.java
b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/LatLonBounds.java
index 8f57efd..a607243 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/LatLonBounds.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/LatLonBounds.java
@@ -213,6 +213,12 @@ public class LatLonBounds implements Bounds {
   }
 
   @Override
+  public Bounds addIntersection(final PlanetModel planetModel, final Plane plane1, final
Plane plane2, final Membership... bounds) {
+    plane1.recordBounds(planetModel, this, plane2, bounds);
+    return this;
+  }
+
+  @Override
   public Bounds addPoint(GeoPoint point) {
     if (!noLongitudeBound) {
       // Get a longitude value

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/908225d1/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 567d12e..47c1b30 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
@@ -996,6 +996,191 @@ public class Plane extends Vector {
     }
   }
 
+  /**
+   * Record intersection points for planes with error bounds.
+   * This method calls the Bounds object with every intersection point it can find that matches
the criteria.
+   * Each plane is considered to have two sides, one that is D + MINIMUM_RESOLUTION, and
one that is 
+   * D - MINIMUM_RESOLUTION.  Both are examined and intersection points determined.
+   */
+  protected void findIntersectionBounds(final PlanetModel planetModel, final Bounds boundsInfo,
final Plane q, final Membership... bounds) {
+    // Unnormalized, unchecked...
+    final double lineVectorX = y * q.z - z * q.y;
+    final double lineVectorY = z * q.x - x * q.z;
+    final double lineVectorZ = x * q.y - y * q.x;
+    if (Math.abs(lineVectorX) < MINIMUM_RESOLUTION && Math.abs(lineVectorY) <
MINIMUM_RESOLUTION && Math.abs(lineVectorZ) < MINIMUM_RESOLUTION) {
+      // Degenerate case: parallel planes
+      //System.err.println(" planes are parallel - no intersection");
+      return;
+    }
+
+    // The line will have the equation: A t + A0 = x, B t + B0 = y, C t + C0 = z.
+    // We have A, B, and C.  In order to come up with A0, B0, and C0, we need to find a point
that is on both planes.
+    // To do this, we find the largest vector value (either x, y, or z), and look for a point
that solves both plane equations
+    // simultaneous.  For example, let's say that the vector is (0.5,0.5,1), and the two
plane equations are:
+    // 0.7 x + 0.3 y + 0.1 z + 0.0 = 0
+    // and
+    // 0.9 x - 0.1 y + 0.2 z + 4.0 = 0
+    // Then we'd pick z = 0, so the equations to solve for x and y would be:
+    // 0.7 x + 0.3y = 0.0
+    // 0.9 x - 0.1y = -4.0
+    // ... which can readily be solved using standard linear algebra.  Generally:
+    // Q0 x + R0 y = S0
+    // Q1 x + R1 y = S1
+    // ... can be solved by Cramer's rule:
+    // x = det(S0 R0 / S1 R1) / det(Q0 R0 / Q1 R1)
+    // y = det(Q0 S0 / Q1 S1) / det(Q0 R0 / Q1 R1)
+    // ... where det( a b / c d ) = ad - bc, so:
+    // x = (S0 * R1 - R0 * S1) / (Q0 * R1 - R0 * Q1)
+    // y = (Q0 * S1 - S0 * Q1) / (Q0 * R1 - R0 * Q1)
+    // We try to maximize the determinant in the denominator
+    final double denomYZ = this.y * q.z - this.z * q.y;
+    final double denomXZ = this.x * q.z - this.z * q.x;
+    final double denomXY = this.x * q.y - this.y * q.x;
+    if (Math.abs(denomYZ) >= Math.abs(denomXZ) && Math.abs(denomYZ) >= Math.abs(denomXY))
{
+      // X is the biggest, so our point will have x0 = 0.0
+      if (Math.abs(denomYZ) < MINIMUM_RESOLUTION_SQUARED) {
+        //System.err.println(" Denominator is zero: no intersection");
+        return;
+      }
+      final double denom = 1.0 / denomYZ;
+      // Each value of D really is two values of D.  That makes 4 combinations.
+      recordLineBounds(planetModel, boundsInfo,
+        lineVectorX, lineVectorY, lineVectorZ,
+        0.0, (-(this.D+MINIMUM_RESOLUTION) * q.z - this.z * -(q.D+MINIMUM_RESOLUTION)) *
denom, (this.y * -(q.D+MINIMUM_RESOLUTION) + (this.D+MINIMUM_RESOLUTION) * q.y) * denom,
+        bounds);
+      recordLineBounds(planetModel, boundsInfo,
+        lineVectorX, lineVectorY, lineVectorZ,
+        0.0, (-(this.D-MINIMUM_RESOLUTION) * q.z - this.z * -(q.D+MINIMUM_RESOLUTION)) *
denom, (this.y * -(q.D+MINIMUM_RESOLUTION) + (this.D-MINIMUM_RESOLUTION) * q.y) * denom,
+        bounds);
+      recordLineBounds(planetModel, boundsInfo,
+        lineVectorX, lineVectorY, lineVectorZ,
+        0.0, (-(this.D+MINIMUM_RESOLUTION) * q.z - this.z * -(q.D-MINIMUM_RESOLUTION)) *
denom, (this.y * -(q.D-MINIMUM_RESOLUTION) + (this.D+MINIMUM_RESOLUTION) * q.y) * denom,
+        bounds);
+      recordLineBounds(planetModel, boundsInfo,
+        lineVectorX, lineVectorY, lineVectorZ,
+        0.0, (-(this.D-MINIMUM_RESOLUTION) * q.z - this.z * -(q.D-MINIMUM_RESOLUTION)) *
denom, (this.y * -(q.D-MINIMUM_RESOLUTION) + (this.D-MINIMUM_RESOLUTION) * q.y) * denom,
+        bounds);
+    } else if (Math.abs(denomXZ) >= Math.abs(denomXY) && Math.abs(denomXZ) >=
Math.abs(denomYZ)) {
+      // Y is the biggest, so y0 = 0.0
+      if (Math.abs(denomXZ) < MINIMUM_RESOLUTION_SQUARED) {
+        //System.err.println(" Denominator is zero: no intersection");
+        return;
+      }
+      final double denom = 1.0 / denomXZ;
+      recordLineBounds(planetModel, boundsInfo,
+        lineVectorX, lineVectorY, lineVectorZ,
+        (-(this.D+MINIMUM_RESOLUTION) * q.z - this.z * -(q.D+MINIMUM_RESOLUTION)) * denom,
0.0, (this.x * -(q.D+MINIMUM_RESOLUTION) + (this.D+MINIMUM_RESOLUTION) * q.x) * denom,
+        bounds);
+      recordLineBounds(planetModel, boundsInfo,
+        lineVectorX, lineVectorY, lineVectorZ,
+        (-(this.D-MINIMUM_RESOLUTION) * q.z - this.z * -(q.D+MINIMUM_RESOLUTION)) * denom,
0.0, (this.x * -(q.D+MINIMUM_RESOLUTION) + (this.D-MINIMUM_RESOLUTION) * q.x) * denom,
+        bounds);
+      recordLineBounds(planetModel, boundsInfo,
+        lineVectorX, lineVectorY, lineVectorZ,
+        (-(this.D+MINIMUM_RESOLUTION) * q.z - this.z * -(q.D-MINIMUM_RESOLUTION)) * denom,
0.0, (this.x * -(q.D-MINIMUM_RESOLUTION) + (this.D+MINIMUM_RESOLUTION) * q.x) * denom,
+        bounds);
+      recordLineBounds(planetModel, boundsInfo,
+        lineVectorX, lineVectorY, lineVectorZ,
+        (-(this.D-MINIMUM_RESOLUTION) * q.z - this.z * -(q.D-MINIMUM_RESOLUTION)) * denom,
0.0, (this.x * -(q.D-MINIMUM_RESOLUTION) + (this.D-MINIMUM_RESOLUTION) * q.x) * denom,
+        bounds);
+    } else {
+      // Z is the biggest, so Z0 = 0.0
+      if (Math.abs(denomXY) < MINIMUM_RESOLUTION_SQUARED) {
+        //System.err.println(" Denominator is zero: no intersection");
+        return;
+      }
+      final double denom = 1.0 / denomXY;
+      recordLineBounds(planetModel, boundsInfo,
+        lineVectorX, lineVectorY, lineVectorZ,
+        (-(this.D+MINIMUM_RESOLUTION) * q.y - this.y * -(q.D+MINIMUM_RESOLUTION)) * denom,
(this.x * -(q.D+MINIMUM_RESOLUTION) + (this.D+MINIMUM_RESOLUTION) * q.x) * denom, 0.0,
+        bounds);
+      recordLineBounds(planetModel, boundsInfo,
+        lineVectorX, lineVectorY, lineVectorZ,
+        (-(this.D-MINIMUM_RESOLUTION) * q.y - this.y * -(q.D+MINIMUM_RESOLUTION)) * denom,
(this.x * -(q.D+MINIMUM_RESOLUTION) + (this.D-MINIMUM_RESOLUTION) * q.x) * denom, 0.0,
+        bounds);
+      recordLineBounds(planetModel, boundsInfo,
+        lineVectorX, lineVectorY, lineVectorZ,
+        (-(this.D+MINIMUM_RESOLUTION) * q.y - this.y * -(q.D-MINIMUM_RESOLUTION)) * denom,
(this.x * -(q.D-MINIMUM_RESOLUTION) + (this.D+MINIMUM_RESOLUTION) * q.x) * denom, 0.0,
+        bounds);
+      recordLineBounds(planetModel, boundsInfo,
+        lineVectorX, lineVectorY, lineVectorZ,
+        (-(this.D-MINIMUM_RESOLUTION) * q.y - this.y * -(q.D-MINIMUM_RESOLUTION)) * denom,
(this.x * -(q.D-MINIMUM_RESOLUTION) + (this.D-MINIMUM_RESOLUTION) * q.x) * denom, 0.0,
+        bounds);
+    }
+  }
+  
+  private static void recordLineBounds(final PlanetModel planetModel,
+    final Bounds boundsInfo,
+    final double lineVectorX, final double lineVectorY, final double lineVectorZ,
+    final double x0, final double y0, final double z0,
+    final Membership... bounds) {
+    // Once an intersecting line is determined, the next step is to intersect that line with
the ellipsoid, which
+    // will yield zero, one, or two points.
+    // The ellipsoid equation: 1,0 = x^2/a^2 + y^2/b^2 + z^2/c^2
+    // 1.0 = (At+A0)^2/a^2 + (Bt+B0)^2/b^2 + (Ct+C0)^2/c^2
+    // A^2 t^2 / a^2 + 2AA0t / a^2 + A0^2 / a^2 + B^2 t^2 / b^2 + 2BB0t / b^2 + B0^2 / b^2
+ C^2 t^2 / c^2 + 2CC0t / c^2 + C0^2 / c^2  - 1,0 = 0.0
+    // [A^2 / a^2 + B^2 / b^2 + C^2 / c^2] t^2 + [2AA0 / a^2 + 2BB0 / b^2 + 2CC0 / c^2] t
+ [A0^2 / a^2 + B0^2 / b^2 + C0^2 / c^2 - 1,0] = 0.0
+    // Use the quadratic formula to determine t values and candidate point(s)
+    final double A = lineVectorX * lineVectorX * planetModel.inverseAbSquared +
+      lineVectorY * lineVectorY * planetModel.inverseAbSquared +
+      lineVectorZ * lineVectorZ * planetModel.inverseCSquared;
+    final double B = 2.0 * (lineVectorX * x0 * planetModel.inverseAbSquared + lineVectorY
* y0 * planetModel.inverseAbSquared + lineVectorZ * z0 * planetModel.inverseCSquared);
+    final double C = x0 * x0 * planetModel.inverseAbSquared + y0 * y0 * planetModel.inverseAbSquared
+ z0 * z0 * planetModel.inverseCSquared - 1.0;
+
+    final double BsquaredMinus = B * B - 4.0 * A * C;
+    if (Math.abs(BsquaredMinus) < MINIMUM_RESOLUTION_SQUARED) {
+      //System.err.println(" One point of intersection");
+      final double inverse2A = 1.0 / (2.0 * A);
+      // One solution only
+      final double t = -B * inverse2A;
+      // Maybe we can save ourselves the cost of construction of a point?
+      final double pointX = lineVectorX * t + x0;
+      final double pointY = lineVectorY * t + y0;
+      final double pointZ = lineVectorZ * t + z0;
+      for (final Membership bound : bounds) {
+        if (!bound.isWithin(pointX, pointY, pointZ)) {
+          return;
+        }
+      }
+      boundsInfo.addPoint(new GeoPoint(pointX, pointY, pointZ));
+    } else if (BsquaredMinus > 0.0) {
+      //System.err.println(" Two points of intersection");
+      final double inverse2A = 1.0 / (2.0 * A);
+      // Two solutions
+      final double sqrtTerm = Math.sqrt(BsquaredMinus);
+      final double t1 = (-B + sqrtTerm) * inverse2A;
+      final double t2 = (-B - sqrtTerm) * inverse2A;
+      // Up to two points being returned.  Do what we can to save on object creation though.
+      final double point1X = lineVectorX * t1 + x0;
+      final double point1Y = lineVectorY * t1 + y0;
+      final double point1Z = lineVectorZ * t1 + z0;
+      final double point2X = lineVectorX * t2 + x0;
+      final double point2Y = lineVectorY * t2 + y0;
+      final double point2Z = lineVectorZ * t2 + z0;
+      boolean point1Valid = true;
+      boolean point2Valid = true;
+      for (final Membership bound : bounds) {
+        if (!bound.isWithin(point1X, point1Y, point1Z)) {
+          point1Valid = false;
+          break;
+        }
+      }
+      for (final Membership bound : bounds) {
+        if (!bound.isWithin(point2X, point2Y, point2Z)) {
+          point2Valid = false;
+          break;
+        }
+      }
+
+      if (point1Valid) {
+        boundsInfo.addPoint(new GeoPoint(point1X, point1Y, point1Z));
+      }
+      if (point2Valid) {
+        boundsInfo.addPoint(new GeoPoint(point2X, point2Y, point2Z));
+      }
+    }
+  }
+
   /*
   protected void verifyPoint(final PlanetModel planetModel, final GeoPoint point, final Plane
q) {
     if (!evaluateIsZero(point))
@@ -1008,6 +1193,21 @@ public class Plane extends Vector {
   */
 
   /**
+   * Accumulate (x,y,z) bounds information for this plane, intersected with another and the
+   * world.
+   * Updates min/max information using intersection points found.  These include the error
+   * envelope for the planes (D +/- MINIMUM_RESOLUTION).
+   * @param planetModel is the planet model to use in determining bounds.
+   * @param boundsInfo is the xyz info to update with additional bounding information.
+   * @param p is the other plane.
+   * @param bounds     are the surfaces delineating what's inside the shape.
+   */
+  public void recordBounds(final PlanetModel planetModel, final XYZBounds boundsInfo, final
Plane p, final Membership... bounds) {
+    findIntersectionBounds(planetModel, boundsInfo, p, bounds);
+  }
+
+
+  /**
    * Accumulate (x,y,z) bounds information for this plane, intersected with the unit sphere.
    * Updates min/max information, using max/min points found
    * within the specified bounds.
@@ -1403,6 +1603,22 @@ public class Plane extends Vector {
   }
   
   /**
+   * Accumulate bounds information for this plane, intersected with another plane
+   * and the world.
+   * Updates both latitude and longitude information, using max/min points found
+   * within the specified bounds.  Also takes into account the error envelope for all
+   * planes being intersected.
+   *
+   * @param planetModel is the planet model to use in determining bounds.
+   * @param boundsInfo is the lat/lon info to update with additional bounding information.
+   * @param p is the other plane.
+   * @param bounds     are the surfaces delineating what's inside the shape.
+   */
+  public void recordBounds(final PlanetModel planetModel, final LatLonBounds boundsInfo,
final Plane p, final Membership... bounds) {
+    findIntersectionBounds(planetModel, boundsInfo, p, bounds);
+  }
+
+  /**
    * Accumulate bounds information for this plane, intersected with the unit sphere.
    * Updates both latitude and longitude information, using max/min points found
    * within the specified bounds.

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/908225d1/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/XYZBounds.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/XYZBounds.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/XYZBounds.java
index 3df4694..171f510 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/XYZBounds.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/XYZBounds.java
@@ -28,8 +28,9 @@ public class XYZBounds implements Bounds {
    * except that our 'bounds' is defined as always equaling or exceeding the boundary
    * of the shape, and we cannot guarantee that without making MINIMUM_RESOLUTION
    * unacceptably large.
+   * Also, see LUCENE-7290 for a description of how geometry can magnify the bounds delta.
    */
-  private static final double FUDGE_FACTOR = Vector.MINIMUM_RESOLUTION * 500.0;
+  private static final double FUDGE_FACTOR = Vector.MINIMUM_RESOLUTION * 100.0;
   
   /** Minimum x */
   private Double minX = null;
@@ -257,6 +258,12 @@ public class XYZBounds implements Bounds {
   }
 
   @Override
+  public Bounds addIntersection(final PlanetModel planetModel, final Plane plane1, final
Plane plane2, final Membership... bounds) {
+    plane1.recordBounds(planetModel, this, plane2, bounds);
+    return this;
+  }
+
+  @Override
   public Bounds addPoint(final GeoPoint point) {
     return addXValue(point).addYValue(point).addZValue(point);
   }

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/908225d1/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java
index 3475b17..0eecc9e 100644
--- a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java
+++ b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java
@@ -430,7 +430,8 @@ public class TestGeo3DPoint extends LuceneTestCase {
           } else {
             log.println("doc=" + docID + " should match but did not");
           }
-          log.println("  point=" + docs[docID]);
+          log.println("  point=" + point);
+          log.println("  mappedPoint=" + mappedPoint);
           fail = true;
         }
       }

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/908225d1/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoBBoxTest.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoBBoxTest.java b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoBBoxTest.java
index ac8d49d..993c79f 100755
--- a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoBBoxTest.java
+++ b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoBBoxTest.java
@@ -361,4 +361,15 @@ public class GeoBBoxTest {
 
   }
   
+  @Test
+  public void testFailureCase1() {
+    final GeoPoint point = new GeoPoint(-0.017413370801260174, -2.132522881412925E-18, 0.9976113450663769);
+    final GeoBBox box = new GeoNorthRectangle(PlanetModel.WGS84, 0.35451471030934045, 9.908337057950734E-15,
2.891004593509811E-11);
+    final XYZBounds bounds = new XYZBounds();
+    box.getBounds(bounds);
+    final XYZSolid solid = XYZSolidFactory.makeXYZSolid(PlanetModel.WGS84, bounds.getMinimumX(),
bounds.getMaximumX(), bounds.getMinimumY(), bounds.getMaximumY(), bounds.getMinimumZ(), bounds.getMaximumZ());
+    
+    assertTrue(box.isWithin(point)?solid.isWithin(point):true);
+  }
+  
 }

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/908225d1/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoCircleTest.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoCircleTest.java
b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoCircleTest.java
index 84100cd..6f9a86b 100755
--- a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoCircleTest.java
+++ b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoCircleTest.java
@@ -118,10 +118,6 @@ public class GeoCircleTest extends LuceneTestCase {
       xyzb.getMinimumX(), xyzb.getMaximumX(), xyzb.getMinimumY(), xyzb.getMaximumY(), xyzb.getMinimumZ(),
xyzb.getMaximumZ());
     relationship = area.getRelationship(c);
     assertTrue(relationship == GeoArea.OVERLAPS || relationship == GeoArea.WITHIN);
-    // Point is actually outside the bounds, and outside the shape
-    assertTrue(!area.isWithin(p1));
-    // Approximate point the same
-    assertTrue(!area.isWithin(p2));
     
     // Eleventh BKD discovered failure
     c = GeoCircleFactory.makeGeoCircle(PlanetModel.SPHERE,-0.004431288600558495,-0.003687846671278374,1.704543429364245E-8);

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/908225d1/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 18753e3..f030896 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
@@ -162,8 +162,6 @@ public class GeoPolygonTest {
     c.getBounds(xyzBounds);
     xyzSolid = XYZSolidFactory.makeXYZSolid(PlanetModel.SPHERE, xyzBounds.getMinimumX(),
xyzBounds.getMaximumX(), xyzBounds.getMinimumY(), xyzBounds.getMaximumY(), xyzBounds.getMinimumZ(),
xyzBounds.getMaximumZ());
     assertEquals(GeoArea.WITHIN, xyzSolid.getRelationship(c));
-    xyzSolid = XYZSolidFactory.makeXYZSolid(PlanetModel.SPHERE, xyzBounds.getMinimumX()-0.01,
xyzBounds.getMaximumX()-0.01, xyzBounds.getMinimumY()-0.01, xyzBounds.getMaximumY()-0.01,
xyzBounds.getMinimumZ()-0.01, xyzBounds.getMaximumZ()-0.01);
-    assertEquals(GeoArea.OVERLAPS, xyzSolid.getRelationship(c));
     xyzSolid = XYZSolidFactory.makeXYZSolid(PlanetModel.SPHERE, xyzBounds.getMinimumY(),
xyzBounds.getMaximumY(), xyzBounds.getMinimumZ(), xyzBounds.getMaximumZ(), xyzBounds.getMinimumX(),
xyzBounds.getMaximumX());
     assertEquals(GeoArea.DISJOINT, xyzSolid.getRelationship(c));
 
@@ -175,8 +173,6 @@ public class GeoPolygonTest {
     // Same bounds should work
     xyzSolid = XYZSolidFactory.makeXYZSolid(PlanetModel.SPHERE, xyzBounds.getMinimumX(),
xyzBounds.getMaximumX(), xyzBounds.getMinimumY(), xyzBounds.getMaximumY(), xyzBounds.getMinimumZ(),
xyzBounds.getMaximumZ());
     assertEquals(GeoArea.WITHIN, xyzSolid.getRelationship(c));
-    xyzSolid = XYZSolidFactory.makeXYZSolid(PlanetModel.SPHERE, xyzBounds.getMinimumX()-0.01,
xyzBounds.getMaximumX()-0.01, xyzBounds.getMinimumY()-0.01, xyzBounds.getMaximumY()-0.01,
xyzBounds.getMinimumZ()-0.01, xyzBounds.getMaximumZ()-0.01);
-    assertEquals(GeoArea.OVERLAPS, xyzSolid.getRelationship(c));
     xyzSolid = XYZSolidFactory.makeXYZSolid(PlanetModel.SPHERE, xyzBounds.getMinimumY(),
xyzBounds.getMaximumY(), xyzBounds.getMinimumZ(), xyzBounds.getMaximumZ(), xyzBounds.getMinimumX(),
xyzBounds.getMaximumX());
     assertEquals(GeoArea.DISJOINT, xyzSolid.getRelationship(c));
 
@@ -185,8 +181,6 @@ public class GeoPolygonTest {
     c.getBounds(xyzBounds);
     xyzSolid = XYZSolidFactory.makeXYZSolid(PlanetModel.SPHERE, xyzBounds.getMinimumX(),
xyzBounds.getMaximumX(), xyzBounds.getMinimumY(), xyzBounds.getMaximumY(), xyzBounds.getMinimumZ(),
xyzBounds.getMaximumZ());
     assertEquals(GeoArea.WITHIN, xyzSolid.getRelationship(c));
-    xyzSolid = XYZSolidFactory.makeXYZSolid(PlanetModel.SPHERE, xyzBounds.getMinimumX()-0.01,
xyzBounds.getMaximumX()-0.01, xyzBounds.getMinimumY()-0.01, xyzBounds.getMaximumY()-0.01,
xyzBounds.getMinimumZ()-0.01, xyzBounds.getMaximumZ()-0.01);
-    assertEquals(GeoArea.OVERLAPS, xyzSolid.getRelationship(c));
     xyzSolid = XYZSolidFactory.makeXYZSolid(PlanetModel.SPHERE, xyzBounds.getMinimumY(),
xyzBounds.getMaximumY(), xyzBounds.getMinimumZ(), xyzBounds.getMaximumZ(), xyzBounds.getMinimumX(),
xyzBounds.getMaximumX());
     assertEquals(GeoArea.DISJOINT, xyzSolid.getRelationship(c));
 


Mime
View raw message