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 2017/09/14 17:52:07 UTC
lucene-solr:branch_6x: LUCENE-7962: Revamp how computeNearestDistance
is done to make it return the distance where the point is truly nearest to
the given path.
Repository: lucene-solr
Updated Branches:
refs/heads/branch_6x d475534ef -> 13c15bc38
LUCENE-7962: Revamp how computeNearestDistance is done to make it return the distance where the point is truly nearest to the given path.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/13c15bc3
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/13c15bc3
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/13c15bc3
Branch: refs/heads/branch_6x
Commit: 13c15bc3854e9adf6f23cd8986205c9127ea7cd5
Parents: d475534
Author: Karl Wright <Da...@gmail.com>
Authored: Thu Sep 14 13:50:41 2017 -0400
Committer: Karl Wright <Da...@gmail.com>
Committed: Thu Sep 14 13:51:58 2017 -0400
----------------------------------------------------------------------
.../spatial3d/geom/GeoDegeneratePath.java | 113 ++++++++++++++++---
.../apache/lucene/spatial3d/geom/GeoPath.java | 28 +++++
.../lucene/spatial3d/geom/GeoStandardPath.java | 113 ++++++++++++++++---
3 files changed, 222 insertions(+), 32 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/13c15bc3/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 861a2d4..6f2f81e 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
@@ -152,31 +152,52 @@ class GeoDegeneratePath extends GeoBasePath {
}
@Override
- public double computeNearestDistance(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.
- double currentDistance = 0.0;
+ public double computePathCenterDistance(final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ // Walk along path and keep track of the closest distance we find
+ double closestDistance = Double.POSITIVE_INFINITY;
+ // Segments first
for (PathSegment segment : segments) {
- double distance = segment.nearestPathDistance(planetModel, distanceStyle, x,y,z);
- if (distance != Double.POSITIVE_INFINITY)
- return distanceStyle.fromAggregationForm(distanceStyle.aggregateDistances(currentDistance, distance));
- currentDistance = distanceStyle.aggregateDistances(currentDistance, segment.fullPathDistance(distanceStyle));
+ final double segmentDistance = segment.pathCenterDistance(planetModel, distanceStyle, x, y, z);
+ if (segmentDistance < closestDistance) {
+ closestDistance = segmentDistance;
+ }
}
+ // Now, endpoints
+ for (SegmentEndpoint endpoint : endPoints) {
+ final double endpointDistance = endpoint.pathCenterDistance(distanceStyle, x, y, z);
+ if (endpointDistance < closestDistance) {
+ closestDistance = endpointDistance;
+ }
+ }
+ return closestDistance;
+ }
+ @Override
+ public double computeNearestDistance(final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ double currentDistance = 0.0;
+ double minPathCenterDistance = Double.POSITIVE_INFINITY;
+ double bestDistance = Double.POSITIVE_INFINITY;
int segmentIndex = 0;
- currentDistance = 0.0;
+
for (SegmentEndpoint endpoint : endPoints) {
- double distance = endpoint.nearestPathDistance(distanceStyle, x, y, z);
- if (distance != Double.POSITIVE_INFINITY) {
- return distanceStyle.fromAggregationForm(distanceStyle.aggregateDistances(currentDistance, distance));
+ final double endpointPathCenterDistance = endpoint.pathCenterDistance(distanceStyle, x, y, z);
+ if (endpointPathCenterDistance < minPathCenterDistance) {
+ // Use this endpoint
+ minPathCenterDistance = endpointPathCenterDistance;
+ bestDistance = currentDistance;
}
+ // Look at the following segment, if any
if (segmentIndex < segments.size()) {
- currentDistance = distanceStyle.aggregateDistances(currentDistance, segments.get(segmentIndex++).fullPathDistance(distanceStyle));
+ final PathSegment segment = segments.get(segmentIndex++);
+ final double segmentPathCenterDistance = segment.pathCenterDistance(planetModel, distanceStyle, x, y, z);
+ if (segmentPathCenterDistance < minPathCenterDistance) {
+ minPathCenterDistance = segmentPathCenterDistance;
+ bestDistance = distanceStyle.aggregateDistances(currentDistance, segment.nearestPathDistance(planetModel, distanceStyle, x, y, z));
+ }
+ currentDistance = distanceStyle.aggregateDistances(currentDistance, segment.fullPathDistance(distanceStyle));
}
}
-
- return Double.POSITIVE_INFINITY;
+ return bestDistance;
}
@Override
@@ -428,6 +449,23 @@ class GeoDegeneratePath extends GeoBasePath {
return distanceStyle.toAggregationForm(0.0);
}
+ /** Compute path center 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, or POSITIVE_INFINITY
+ * if the point is not within the bounds of the endpoint.
+ */
+ public double pathCenterDistance(final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ for (final Membership m : cutoffPlanes) {
+ if (!m.isWithin(x,y,z)) {
+ return Double.POSITIVE_INFINITY;
+ }
+ }
+ return distanceStyle.computeDistance(this.point, x, y, z);
+ }
+
/** Compute external distance.
*@param distanceStyle is the distance style.
*@param x is the point x.
@@ -567,6 +605,49 @@ class GeoDegeneratePath extends GeoBasePath {
normalizedConnectingPlane.evaluateIsZero(x, y, z);
}
+ /** Compute path center 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, or Double.POSITIVE_INFINITY if outside this segment
+ */
+ public double pathCenterDistance(final PlanetModel planetModel, final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ // First, if this point is outside the endplanes of the segment, return POSITIVE_INFINITY.
+ if (!startCutoffPlane.isWithin(x, y, z) || !endCutoffPlane.isWithin(x, y, z)) {
+ return Double.POSITIVE_INFINITY;
+ }
+ // (1) Compute normalizedPerpPlane. If degenerate, then there is no such plane, which means that the point given
+ // is insufficient to distinguish between a family of such planes. This can happen only if the point is one of the
+ // "poles", imagining the normalized plane to be the "equator". In that case, the distance returned should be zero.
+ // 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)
+ return distanceStyle.computeDistance(start, x, y, z);
+ final double normFactor = 1.0/magnitude;
+ final Plane normalizedPerpPlane = new Plane(perpX * normFactor, perpY * normFactor, perpZ * normFactor, 0.0);
+
+ 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);
+ }
+ return distanceStyle.computeDistance(thePoint, x, y, z);
+ }
+
/** Compute nearest 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/13c15bc3/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPath.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPath.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPath.java
index 891c896..8fe5632 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPath.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPath.java
@@ -52,4 +52,32 @@ public interface GeoPath extends GeoDistanceShape {
*/
public double computeNearestDistance(final DistanceStyle distanceStyle, final double x, final double y, final double z);
+ // The following methods compute the best distance from the path center to the point.
+
+ /**
+ * Compute the shortest distance from the path center to the GeoPoint.
+ * The distance is meant to allow comparisons between different
+ * paths to find the one that goes closest to a point.
+ *
+ * @param distanceStyle is the distance style.
+ * @param point is the point to compute the distance to.
+ * @return the shortest distance from the path center to the point.
+ */
+ public default double computePathCenterDistance(final DistanceStyle distanceStyle, final GeoPoint point) {
+ return computePathCenterDistance(distanceStyle, point.x, point.y, point.z);
+ }
+
+ /**
+ * Compute the shortest distance from the path center to the GeoPoint.
+ * The distance is meant to allow comparisons between different
+ * paths to find the one that goes closest to a point.
+ *
+ * @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 shortest distance from the path center to the point.
+ */
+ public double computePathCenterDistance(final DistanceStyle distanceStyle, final double x, final double y, final double z);
+
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/13c15bc3/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 841b981..195d596 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
@@ -215,31 +215,52 @@ class GeoStandardPath extends GeoBasePath {
}
@Override
- public double computeNearestDistance(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.
- double currentDistance = 0.0;
+ public double computePathCenterDistance(final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ // Walk along path and keep track of the closest distance we find
+ double closestDistance = Double.POSITIVE_INFINITY;
+ // Segments first
for (PathSegment segment : segments) {
- double distance = segment.nearestPathDistance(planetModel, distanceStyle, x,y,z);
- if (distance != Double.POSITIVE_INFINITY)
- return distanceStyle.fromAggregationForm(distanceStyle.aggregateDistances(currentDistance, distance));
- currentDistance = distanceStyle.aggregateDistances(currentDistance, segment.fullPathDistance(distanceStyle));
+ final double segmentDistance = segment.pathCenterDistance(planetModel, distanceStyle, x, y, z);
+ if (segmentDistance < closestDistance) {
+ closestDistance = segmentDistance;
+ }
}
+ // Now, endpoints
+ for (SegmentEndpoint endpoint : endPoints) {
+ final double endpointDistance = endpoint.pathCenterDistance(distanceStyle, x, y, z);
+ if (endpointDistance < closestDistance) {
+ closestDistance = endpointDistance;
+ }
+ }
+ return closestDistance;
+ }
+ @Override
+ public double computeNearestDistance(final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ double currentDistance = 0.0;
+ double minPathCenterDistance = Double.POSITIVE_INFINITY;
+ double bestDistance = Double.POSITIVE_INFINITY;
int segmentIndex = 0;
- currentDistance = 0.0;
+
for (SegmentEndpoint endpoint : endPoints) {
- double distance = endpoint.nearestPathDistance(distanceStyle, x, y, z);
- if (distance != Double.POSITIVE_INFINITY) {
- return distanceStyle.fromAggregationForm(distanceStyle.aggregateDistances(currentDistance, distance));
+ final double endpointPathCenterDistance = endpoint.pathCenterDistance(distanceStyle, x, y, z);
+ if (endpointPathCenterDistance < minPathCenterDistance) {
+ // Use this endpoint
+ minPathCenterDistance = endpointPathCenterDistance;
+ bestDistance = currentDistance;
}
+ // Look at the following segment, if any
if (segmentIndex < segments.size()) {
- currentDistance = distanceStyle.aggregateDistances(currentDistance, segments.get(segmentIndex++).fullPathDistance(distanceStyle));
+ final PathSegment segment = segments.get(segmentIndex++);
+ final double segmentPathCenterDistance = segment.pathCenterDistance(planetModel, distanceStyle, x, y, z);
+ if (segmentPathCenterDistance < minPathCenterDistance) {
+ minPathCenterDistance = segmentPathCenterDistance;
+ bestDistance = distanceStyle.aggregateDistances(currentDistance, segment.nearestPathDistance(planetModel, distanceStyle, x, y, z));
+ }
+ currentDistance = distanceStyle.aggregateDistances(currentDistance, segment.fullPathDistance(distanceStyle));
}
}
-
- return Double.POSITIVE_INFINITY;
+ return bestDistance;
}
@Override
@@ -607,6 +628,23 @@ class GeoStandardPath extends GeoBasePath {
return distanceStyle.toAggregationForm(0.0);
}
+ /** Compute path center 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, or POSITIVE_INFINITY
+ * if the point is not within the bounds of the endpoint.
+ */
+ public double pathCenterDistance(final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ for (final Membership m : cutoffPlanes) {
+ if (!m.isWithin(x,y,z)) {
+ return Double.POSITIVE_INFINITY;
+ }
+ }
+ return distanceStyle.computeDistance(this.point, x, y, z);
+ }
+
/** Compute external distance.
*@param distanceStyle is the distance style.
*@param x is the point x.
@@ -811,6 +849,49 @@ class GeoStandardPath extends GeoBasePath {
lowerConnectingPlane.isWithin(x, y, z);
}
+ /** Compute path center 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, or Double.POSITIVE_INFINITY if outside this segment
+ */
+ public double pathCenterDistance(final PlanetModel planetModel, final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ // First, if this point is outside the endplanes of the segment, return POSITIVE_INFINITY.
+ if (!startCutoffPlane.isWithin(x, y, z) || !endCutoffPlane.isWithin(x, y, z)) {
+ return Double.POSITIVE_INFINITY;
+ }
+ // (1) Compute normalizedPerpPlane. If degenerate, then there is no such plane, which means that the point given
+ // is insufficient to distinguish between a family of such planes. This can happen only if the point is one of the
+ // "poles", imagining the normalized plane to be the "equator". In that case, the distance returned should be zero.
+ // 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)
+ return distanceStyle.computeDistance(start, x, y, z);
+ final double normFactor = 1.0/magnitude;
+ final Plane normalizedPerpPlane = new Plane(perpX * normFactor, perpY * normFactor, perpZ * normFactor, 0.0);
+
+ 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);
+ }
+ return distanceStyle.computeDistance(thePoint, x, y, z);
+ }
+
/** Compute nearest path distance.
*@param planetModel is the planet model.
*@param distanceStyle is the distance style.