lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kwri...@apache.org
Subject lucene-solr:branch_6x: LUCENE-8039: Add delta distance method to augment internal distance.
Date Wed, 08 Nov 2017 12:32:44 GMT
Repository: lucene-solr
Updated Branches:
  refs/heads/branch_6x 2867a4eee -> 40540b4ca


LUCENE-8039: Add delta distance method to augment internal distance.


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

Branch: refs/heads/branch_6x
Commit: 40540b4cadf4ad1863d5aef2eee75a40931a4523
Parents: 2867a4e
Author: Karl Wright <DaddyWri@gmail.com>
Authored: Wed Nov 8 07:26:43 2017 -0500
Committer: Karl Wright <DaddyWri@gmail.com>
Committed: Wed Nov 8 07:32:33 2017 -0500

----------------------------------------------------------------------
 .../spatial3d/geom/GeoBaseDistanceShape.java    |  20 +++-
 .../spatial3d/geom/GeoDegeneratePath.java       |   6 +
 .../lucene/spatial3d/geom/GeoDistance.java      |  37 +++++-
 .../lucene/spatial3d/geom/GeoStandardPath.java  | 117 +++++++++++++++++--
 .../lucene/spatial3d/geom/GeoPathTest.java      |   4 +-
 5 files changed, 173 insertions(+), 11 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/40540b4c/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseDistanceShape.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseDistanceShape.java
b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseDistanceShape.java
index d7be2ab..2bdd54d 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseDistanceShape.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseDistanceShape.java
@@ -49,10 +49,28 @@ public abstract class GeoBaseDistanceShape extends GeoBaseAreaShape implements
G
     return distance(distanceStyle, x, y, z);
   }
 
-  /** Called by a {@code computeDistance} method if X/Y/Z is not within this shape. */
+  /** Called by a {@code computeDistance} method if X/Y/Z is within this shape. */
   protected abstract double distance(final DistanceStyle distanceStyle, final double x, final
double y, final double z);
 
   @Override
+  public double computeDeltaDistance(final DistanceStyle distanceStyle, final GeoPoint point)
{
+    return computeDeltaDistance(distanceStyle, point.x, point.y, point.z);
+  }
+
+  @Override
+  public double computeDeltaDistance(final DistanceStyle distanceStyle, final double x, final
double y, final double z) {
+    if (!isWithin(x,y,z)) {
+      return Double.POSITIVE_INFINITY;
+    }
+    return deltaDistance(distanceStyle, x, y, z);
+  }
+
+  /** Called by a {@code computeDeltaDistance} method if X/Y/Z is within this shape. */
+  protected double deltaDistance(final DistanceStyle distanceStyle, final double x, final
double y, final double z) {
+    return distance(distanceStyle, x, y, z) * 2.0;
+  }
+
+  @Override
   public void getDistanceBounds(final Bounds bounds, final DistanceStyle distanceStyle, final
double distanceValue) {
     if (distanceValue == Double.POSITIVE_INFINITY) {
       getBounds(bounds);

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/40540b4c/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoDegeneratePath.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoDegeneratePath.java
b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoDegeneratePath.java
index 6f2f81e..2662d87 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoDegeneratePath.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoDegeneratePath.java
@@ -227,6 +227,12 @@ class GeoDegeneratePath extends GeoBasePath {
   }
 
   @Override
+  protected double deltaDistance(final DistanceStyle distanceStyle, final double x, final
double y, final double z) {
+    // Since this is always called when a point is within the degenerate path, delta distance
is always zero by definition.
+    return 0.0;
+  }
+  
+  @Override
   protected void distanceBounds(final Bounds bounds, final DistanceStyle distanceStyle, final
double distanceValue) {
     // TBD: Compute actual bounds based on distance
     getBounds(bounds);

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/40540b4c/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoDistance.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoDistance.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoDistance.java
index 51c258a..bf020fe 100755
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoDistance.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoDistance.java
@@ -49,6 +49,7 @@ public interface GeoDistance extends Membership {
    * A return value of Double.POSITIVE_INFINITY should be returned for
    * points outside of the shape.
    *
+   * @param distanceStyle is the distance style.
    * @param x is the point's unit x coordinate (using U.S. convention).
    * @param y is the point's unit y coordinate (using U.S. convention).
    * @param z is the point's unit z coordinate (using U.S. convention).
@@ -56,5 +57,39 @@ public interface GeoDistance extends Membership {
    */
   public double computeDistance(final DistanceStyle distanceStyle, final double x, final
double y, final double z);
 
- 
+  /**
+   * Compute the shape's <em>delta</em> distance given a point.  This is defined
as the distance that someone traveling
+   * the "length" of the shape would have to go out of their way to include the point.
+   * For some shapes, e.g. paths, this makes perfect sense.  For other shapes, e.g. circles,
the "length" of the shape is zero, 
+   * and the delta is computed as the distance from the center to the point and back.
+   * A return value of Double.POSITIVE_INFINITY should be returned for
+   * points outside of the shape.
+   *
+   * @param distanceStyle is the distance style.
+   * @param point is the point to compute the distance to.
+   * @return the distance.
+   */
+  public default double computeDeltaDistance(final DistanceStyle distanceStyle, final GeoPoint
point) {
+    return computeDeltaDistance(distanceStyle, point.x, point.y, point.z);
+  }
+
+  /**
+   * Compute the shape's <em>delta</em> distance given a point.  This is defined
as the distance that someone traveling
+   * the "length" of the shape would have to go out of their way to include the point.
+   * For some shapes, e.g. paths, this makes perfect sense.  For other shapes, e.g. circles,
the "length" of the shape is zero, 
+   * and the delta is computed as the distance from the center to the point and back.
+   * A return value of Double.POSITIVE_INFINITY should be returned for
+   * points outside of the shape.
+   *
+   * @param distanceStyle is the distance style.
+   * @param x is the point's unit x coordinate (using U.S. convention).
+   * @param y is the point's unit y coordinate (using U.S. convention).
+   * @param z is the point's unit z coordinate (using U.S. convention).
+   * @return the distance.
+   */
+  public default double computeDeltaDistance(final DistanceStyle distanceStyle, final double
x, final double y, final double z) {
+    // Default to standard distance * 2, which is fine for circles
+    return computeDistance(distanceStyle, x, y, z) * 2.0;
+  }
+
 }

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/40540b4c/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoStandardPath.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoStandardPath.java
b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoStandardPath.java
index 195d596..43e6642 100755
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoStandardPath.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoStandardPath.java
@@ -242,7 +242,7 @@ class GeoStandardPath extends GeoBasePath {
     double bestDistance = Double.POSITIVE_INFINITY;
     int segmentIndex = 0;
     
-    for (SegmentEndpoint endpoint : endPoints) {
+    for (final SegmentEndpoint endpoint : endPoints) {
       final double endpointPathCenterDistance = endpoint.pathCenterDistance(distanceStyle,
x, y, z);
       if (endpointPathCenterDistance < minPathCenterDistance) {
         // Use this endpoint
@@ -268,28 +268,70 @@ class GeoStandardPath extends GeoBasePath {
     // Algorithm:
     // (1) If the point is within any of the segments along the path, return that value.
     // (2) If the point is within any of the segment end circles along the path, return that
value.
+    // The algorithm loops over the whole path to get the shortest distance
+    double bestDistance = Double.POSITIVE_INFINITY;
+    
     double currentDistance = 0.0;
-    for (PathSegment segment : segments) {
+    for (final PathSegment segment : segments) {
       double distance = segment.pathDistance(planetModel, distanceStyle, x,y,z);
-      if (distance != Double.POSITIVE_INFINITY)
-        return distanceStyle.fromAggregationForm(distanceStyle.aggregateDistances(currentDistance,
distance));
+      if (distance != Double.POSITIVE_INFINITY) {
+        final double thisDistance = distanceStyle.fromAggregationForm(distanceStyle.aggregateDistances(currentDistance,
distance));
+        if (thisDistance < bestDistance) {
+          bestDistance = thisDistance;
+        }
+      }
       currentDistance = distanceStyle.aggregateDistances(currentDistance, segment.fullPathDistance(distanceStyle));
     }
 
     int segmentIndex = 0;
     currentDistance = 0.0;
-    for (SegmentEndpoint endpoint : endPoints) {
+    for (final SegmentEndpoint endpoint : endPoints) {
       double distance = endpoint.pathDistance(distanceStyle, x, y, z);
-      if (distance != Double.POSITIVE_INFINITY)
-        return distanceStyle.fromAggregationForm(distanceStyle.aggregateDistances(currentDistance,
distance));
+      if (distance != Double.POSITIVE_INFINITY) {
+        final double thisDistance = distanceStyle.fromAggregationForm(distanceStyle.aggregateDistances(currentDistance,
distance));
+        if (thisDistance < bestDistance) {
+          bestDistance = thisDistance;
+        }
+      }
       if (segmentIndex < segments.size())
         currentDistance = distanceStyle.aggregateDistances(currentDistance, segments.get(segmentIndex++).fullPathDistance(distanceStyle));
     }
 
-    return Double.POSITIVE_INFINITY;
+    return bestDistance;
   }
 
   @Override
+  protected double deltaDistance(final DistanceStyle distanceStyle, final double x, final
double y, final double z) {
+    // Algorithm:
+    // (1) If the point is within any of the segments along the path, return that value.
+    // (2) If the point is within any of the segment end circles along the path, return that
value.
+    // Finds best distance
+    double bestDistance = Double.POSITIVE_INFINITY;
+    
+    for (final PathSegment segment : segments) {
+      final double distance = segment.pathDeltaDistance(planetModel, distanceStyle, x, y,
z);
+      if (distance != Double.POSITIVE_INFINITY) {
+        final double thisDistance = distanceStyle.fromAggregationForm(distance);
+        if (thisDistance < bestDistance) {
+          bestDistance = thisDistance;
+        }
+      }
+    }
+
+    for (final SegmentEndpoint endpoint : endPoints) {
+      final double distance = endpoint.pathDeltaDistance(distanceStyle, x, y, z);
+      if (distance != Double.POSITIVE_INFINITY) {
+        final double thisDistance = distanceStyle.fromAggregationForm(distance);
+        if (thisDistance < bestDistance) {
+          bestDistance = thisDistance;
+        }
+      }
+    }
+
+    return bestDistance;
+  }
+  
+  @Override
   protected void distanceBounds(final Bounds bounds, final DistanceStyle distanceStyle, final
double distanceValue) {
     // TBD: Compute actual bounds based on distance
     getBounds(bounds);
@@ -598,6 +640,20 @@ class GeoStandardPath extends GeoBasePath {
       return true;
     }
 
+    /** Compute delta path distance.
+     *@param distanceStyle is the distance style.
+     *@param x is the point x.
+     *@param y is the point y.
+     *@param z is the point z.
+     *@return the distance metric, in aggregation form.
+     */
+    public double pathDeltaDistance(final DistanceStyle distanceStyle, final double x, final
double y, final double z) {
+      if (!isWithin(x,y,z))
+        return Double.POSITIVE_INFINITY;
+      final double theDistance = distanceStyle.toAggregationForm(distanceStyle.computeDistance(this.point,
x, y, z));
+      return distanceStyle.aggregateDistances(theDistance, theDistance);
+    }
+
     /** Compute interior path distance.
      *@param distanceStyle is the distance style.
      *@param x is the point x.
@@ -935,7 +991,52 @@ class GeoStandardPath extends GeoBasePath {
       return distanceStyle.toAggregationForm(distanceStyle.computeDistance(start, thePoint.x,
thePoint.y, thePoint.z));
     }
       
+    /** Compute delta path distance.
+     *@param planetModel is the planet model.
+     *@param distanceStyle is the distance style.
+     *@param x is the point x.
+     *@param y is the point y.
+     *@param z is the point z.
+     *@return the distance metric, in aggregation form, or Double.POSITIVE_INFINITY if outside
the segment.
+     */
+    public double pathDeltaDistance(final PlanetModel planetModel, final DistanceStyle distanceStyle,
final double x, final double y, final double z) {
+      if (!isWithin(x,y,z))
+        return Double.POSITIVE_INFINITY;
+      // (1) Compute normalizedPerpPlane.  If degenerate, then return point distance from
start to point.
+      // Want no allocations or expensive operations!  so we do this the hard way
+      final double perpX = normalizedConnectingPlane.y * z - normalizedConnectingPlane.z
* y;
+      final double perpY = normalizedConnectingPlane.z * x - normalizedConnectingPlane.x
* z;
+      final double perpZ = normalizedConnectingPlane.x * y - normalizedConnectingPlane.y
* x;
+      final double magnitude = Math.sqrt(perpX * perpX + perpY * perpY + perpZ * perpZ);
+      if (Math.abs(magnitude) < Vector.MINIMUM_RESOLUTION) {
+        final double theDistance = distanceStyle.computeDistance(start, x,y,z);
+        return distanceStyle.aggregateDistances(theDistance, theDistance);
+      }
+      final double normFactor = 1.0/magnitude;
+      final Plane normalizedPerpPlane = new Plane(perpX * normFactor, perpY * normFactor,
perpZ * normFactor, 0.0);
+      
+      // Old computation: too expensive, because it calculates the intersection point twice.
+      //return distanceStyle.computeDistance(planetModel, normalizedConnectingPlane, x, y,
z, startCutoffPlane, endCutoffPlane) +
+      //  distanceStyle.computeDistance(planetModel, normalizedPerpPlane, start.x, start.y,
start.z, upperConnectingPlane, lowerConnectingPlane);
 
+      final GeoPoint[] intersectionPoints = normalizedConnectingPlane.findIntersections(planetModel,
normalizedPerpPlane);
+      GeoPoint thePoint;
+      if (intersectionPoints.length == 0)
+        throw new RuntimeException("Can't find world intersection for point x="+x+" y="+y+"
z="+z);
+      else if (intersectionPoints.length == 1)
+        thePoint = intersectionPoints[0];
+      else {
+        if (startCutoffPlane.isWithin(intersectionPoints[0]) && endCutoffPlane.isWithin(intersectionPoints[0]))
+          thePoint = intersectionPoints[0];
+        else if (startCutoffPlane.isWithin(intersectionPoints[1]) && endCutoffPlane.isWithin(intersectionPoints[1]))
+          thePoint = intersectionPoints[1];
+        else
+          throw new RuntimeException("Can't find world intersection for point x="+x+" y="+y+"
z="+z);
+      }
+      final double theDistance = distanceStyle.toAggregationForm(distanceStyle.computeDistance(thePoint,
x, y, z));
+      return distanceStyle.aggregateDistances(theDistance, theDistance);
+    }
+    
     /** Compute interior path distance.
      *@param planetModel is the planet model.
      *@param distanceStyle is the distance style.

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/40540b4c/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPathTest.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPathTest.java b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPathTest.java
index 922617d..f6d14f2 100755
--- a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPathTest.java
+++ b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPathTest.java
@@ -57,10 +57,12 @@ public class GeoPathTest {
     gp = new GeoPoint(PlanetModel.SPHERE, 0.05, 0.15);
     assertEquals(0.15 + 0.05, p.computeDistance(DistanceStyle.ARC,gp), 0.000001);
     assertEquals(0.15, p.computeNearestDistance(DistanceStyle.ARC,gp), 0.000001);
+    assertEquals(0.10, p.computeDeltaDistance(DistanceStyle.ARC,gp), 0.000001);
     gp = new GeoPoint(PlanetModel.SPHERE, 0.0, 0.12);
     assertEquals(0.12, p.computeDistance(DistanceStyle.ARC,gp), 0.000001);
     assertEquals(0.12, p.computeNearestDistance(DistanceStyle.ARC,gp), 0.000001);
-
+    assertEquals(0.0, p.computeDeltaDistance(DistanceStyle.ARC,gp), 0.000001);
+    
     // Now try a vertical path, and make sure distances are as expected
     p = new GeoStandardPath(PlanetModel.SPHERE, 0.1);
     p.addPoint(-Math.PI * 0.25, -0.5);


Mime
View raw message