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 2022/11/23 23:52:20 UTC
[lucene] 04/19: Fix longstanding bug in path bounds calculation, and hook up efficient isWithin() and distance logic
This is an automated email from the ASF dual-hosted git repository.
kwright pushed a commit to branch branch_9x
in repository https://gitbox.apache.org/repos/asf/lucene.git
commit 9450f3d2b648dbfd735db53a78a783650b7c4d33
Author: Karl David Wright <kw...@apache.org>
AuthorDate: Sat Nov 19 17:35:30 2022 -0500
Fix longstanding bug in path bounds calculation, and hook up efficient isWithin() and distance logic
---
.../geom/{GeoBaseShape.java => GeoBaseBounds.java} | 6 +-
.../apache/lucene/spatial3d/geom/GeoBaseShape.java | 24 +-
.../apache/lucene/spatial3d/geom/GeoBounds.java | 27 ++
.../org/apache/lucene/spatial3d/geom/GeoShape.java | 2 +-
.../lucene/spatial3d/geom/GeoStandardPath.java | 277 ++++++++-------------
5 files changed, 140 insertions(+), 196 deletions(-)
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseBounds.java
similarity index 90%
copy from lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
copy to lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseBounds.java
index a5992392563..52030b333d3 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseBounds.java
@@ -17,18 +17,18 @@
package org.apache.lucene.spatial3d.geom;
/**
- * Base extended shape object.
+ * Base object that supports bounds operations.
*
* @lucene.internal
*/
-public abstract class GeoBaseShape extends BasePlanetObject implements GeoShape {
+public abstract class GeoBaseBounds extends BasePlanetObject implements GeoBounds {
/**
* Constructor.
*
* @param planetModel is the planet model to use.
*/
- public GeoBaseShape(final PlanetModel planetModel) {
+ public GeoBaseBounds(final PlanetModel planetModel) {
super(planetModel);
}
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
index a5992392563..a4b5cd18a62 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
@@ -21,7 +21,7 @@ package org.apache.lucene.spatial3d.geom;
*
* @lucene.internal
*/
-public abstract class GeoBaseShape extends BasePlanetObject implements GeoShape {
+public abstract class GeoBaseShape extends GeoBaseBounds implements GeoShape {
/**
* Constructor.
@@ -31,26 +31,4 @@ public abstract class GeoBaseShape extends BasePlanetObject implements GeoShape
public GeoBaseShape(final PlanetModel planetModel) {
super(planetModel);
}
-
- @Override
- public void getBounds(Bounds bounds) {
- if (isWithin(planetModel.NORTH_POLE)) {
- bounds.noTopLatitudeBound().noLongitudeBound().addPoint(planetModel.NORTH_POLE);
- }
- if (isWithin(planetModel.SOUTH_POLE)) {
- bounds.noBottomLatitudeBound().noLongitudeBound().addPoint(planetModel.SOUTH_POLE);
- }
- if (isWithin(planetModel.MIN_X_POLE)) {
- bounds.addPoint(planetModel.MIN_X_POLE);
- }
- if (isWithin(planetModel.MAX_X_POLE)) {
- bounds.addPoint(planetModel.MAX_X_POLE);
- }
- if (isWithin(planetModel.MIN_Y_POLE)) {
- bounds.addPoint(planetModel.MIN_Y_POLE);
- }
- if (isWithin(planetModel.MAX_Y_POLE)) {
- bounds.addPoint(planetModel.MAX_Y_POLE);
- }
- }
}
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBounds.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBounds.java
new file mode 100644
index 00000000000..935366c5a08
--- /dev/null
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBounds.java
@@ -0,0 +1,27 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.spatial3d.geom;
+
+/**
+ * Generic shape that supports bounds. This describes methods that help
+ * shapes compute their bounds.
+ *
+ * @lucene.experimental
+ */
+public interface GeoBounds extends Bounded, Membership, PlanetObject {
+
+}
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoShape.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoShape.java
index 8262ecf5a9e..4e32b9e03e8 100755
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoShape.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoShape.java
@@ -22,7 +22,7 @@ package org.apache.lucene.spatial3d.geom;
*
* @lucene.experimental
*/
-public interface GeoShape extends Bounded, Membership, PlanetObject {
+public interface GeoShape extends GeoBounds {
/**
* Return a sample point that is on the outside edge/boundary of the shape.
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 1f997100e1a..16a07009b64 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
@@ -188,82 +188,83 @@ class GeoStandardPath extends GeoBasePath {
new GeoPoint[] {
onlyEndpoint.circlePlane.getSampleIntersectionPoint(planetModel, normalPlane)
};
- return;
- }
-
- // Create segment endpoints. Use an appropriate constructor for the start and end of the path.
- for (int i = 0; i < segments.size(); i++) {
- final PathSegment currentSegment = segments.get(i);
-
- if (i == 0) {
- // Starting endpoint
- final SegmentEndpoint startEndpoint =
+ } else {
+ // Create segment endpoints. Use an appropriate constructor for the start and end of the path.
+ for (int i = 0; i < segments.size(); i++) {
+ final PathSegment currentSegment = segments.get(i);
+
+ if (i == 0) {
+ // Starting endpoint
+ final SegmentEndpoint startEndpoint =
new CutoffSingleCircleSegmentEndpoint(
- planetModel,
- null,
- currentSegment.start,
- currentSegment.startCutoffPlane,
- currentSegment.ULHC,
- currentSegment.LLHC);
- endPoints.add(startEndpoint);
- this.edgePoints = new GeoPoint[] {currentSegment.ULHC};
- continue;
- }
+ planetModel,
+ null,
+ currentSegment.start,
+ currentSegment.startCutoffPlane,
+ currentSegment.ULHC,
+ currentSegment.LLHC);
+ endPoints.add(startEndpoint);
+ this.edgePoints = new GeoPoint[] {currentSegment.ULHC};
+ continue;
+ }
- // General intersection case
- final PathSegment prevSegment = segments.get(i - 1);
- if (prevSegment.endCutoffPlane.isWithin(currentSegment.ULHC)
- && prevSegment.endCutoffPlane.isWithin(currentSegment.LLHC)
- && currentSegment.startCutoffPlane.isWithin(prevSegment.URHC)
- && currentSegment.startCutoffPlane.isWithin(prevSegment.LRHC)) {
- // The planes are identical. We wouldn't need a circle at all except for the possibility of
- // backing up, which is hard to detect here.
- final SegmentEndpoint midEndpoint =
+ // General intersection case
+ final PathSegment prevSegment = segments.get(i - 1);
+ if (prevSegment.endCutoffPlane.isWithin(currentSegment.ULHC)
+ && prevSegment.endCutoffPlane.isWithin(currentSegment.LLHC)
+ && currentSegment.startCutoffPlane.isWithin(prevSegment.URHC)
+ && currentSegment.startCutoffPlane.isWithin(prevSegment.LRHC)) {
+ // The planes are identical. We wouldn't need a circle at all except for the possibility of
+ // backing up, which is hard to detect here.
+ final SegmentEndpoint midEndpoint =
new CutoffSingleCircleSegmentEndpoint(
- planetModel,
- prevSegment,
- currentSegment.start,
- prevSegment.endCutoffPlane,
- currentSegment.startCutoffPlane,
- currentSegment.ULHC,
- currentSegment.LLHC);
- // don't need a circle at all. Special constructor...
- endPoints.add(midEndpoint);
- } else {
- endPoints.add(
- new CutoffDualCircleSegmentEndpoint(
- planetModel,
- prevSegment,
- currentSegment.start,
- prevSegment.endCutoffPlane,
- currentSegment.startCutoffPlane,
- prevSegment.URHC,
- prevSegment.LRHC,
- currentSegment.ULHC,
- currentSegment.LLHC));
+ planetModel,
+ prevSegment,
+ currentSegment.start,
+ prevSegment.endCutoffPlane,
+ currentSegment.startCutoffPlane,
+ currentSegment.ULHC,
+ currentSegment.LLHC);
+ // don't need a circle at all. Special constructor...
+ endPoints.add(midEndpoint);
+ } else {
+ endPoints.add(
+ new CutoffDualCircleSegmentEndpoint(
+ planetModel,
+ prevSegment,
+ currentSegment.start,
+ prevSegment.endCutoffPlane,
+ currentSegment.startCutoffPlane,
+ prevSegment.URHC,
+ prevSegment.LRHC,
+ currentSegment.ULHC,
+ currentSegment.LLHC));
+ }
}
+ // Do final endpoint
+ final PathSegment lastSegment = segments.get(segments.size() - 1);
+ endPoints.add(
+ new CutoffSingleCircleSegmentEndpoint(
+ planetModel,
+ lastSegment,
+ lastSegment.end,
+ lastSegment.endCutoffPlane,
+ lastSegment.URHC,
+ lastSegment.LRHC));
}
- // Do final endpoint
- final PathSegment lastSegment = segments.get(segments.size() - 1);
- endPoints.add(
- new CutoffSingleCircleSegmentEndpoint(
- planetModel,
- lastSegment,
- lastSegment.end,
- lastSegment.endCutoffPlane,
- lastSegment.URHC,
- lastSegment.LRHC));
final TreeBuilder treeBuilder = new TreeBuilder(segments.size() + endPoints.size());
// Segments will have one less than the number of endpoints.
// So, we add the first endpoint, and then do it pairwise.
- treeBuilder.addComponent(segments.get(0));
+ treeBuilder.addComponent(endPoints.get(0));
for (int i = 0; i < segments.size(); i++) {
treeBuilder.addComponent(segments.get(i));
treeBuilder.addComponent(endPoints.get(i + 1));
}
rootComponent = treeBuilder.getRoot();
+
+ //System.out.println("Root component: "+rootComponent);
}
/**
@@ -289,28 +290,16 @@ class GeoStandardPath extends GeoBasePath {
@Override
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) {
- final double segmentDistance = segment.pathCenterDistance(distanceStyle, x, y, z);
- if (segmentDistance < closestDistance) {
- closestDistance = segmentDistance;
- }
+ if (rootComponent == null) {
+ return Double.POSITIVE_INFINITY;
}
- // Now, endpoints
- for (SegmentEndpoint endpoint : endPoints) {
- final double endpointDistance = endpoint.pathCenterDistance(distanceStyle, x, y, z);
- if (endpointDistance < closestDistance) {
- closestDistance = endpointDistance;
- }
- }
- return closestDistance;
+ return rootComponent.pathCenterDistance(distanceStyle, x, y, z);
}
@Override
public double computeNearestDistance(
final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ // MHL - need another abstraction method for this
double currentDistance = 0.0;
double minPathCenterDistance = Double.POSITIVE_INFINITY;
double bestDistance = Double.POSITIVE_INFINITY;
@@ -344,6 +333,8 @@ class GeoStandardPath extends GeoBasePath {
@Override
protected double distance(
final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ // MHL - need another method in the abstraction!
+
// 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.
@@ -390,33 +381,10 @@ class GeoStandardPath extends GeoBasePath {
@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(distanceStyle, x, y, z);
- if (distance != Double.POSITIVE_INFINITY) {
- final double thisDistance = distanceStyle.fromAggregationForm(distance);
- if (thisDistance < bestDistance) {
- bestDistance = thisDistance;
- }
- }
+ if (rootComponent == null) {
+ return Double.POSITIVE_INFINITY;
}
-
- 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;
+ return distanceStyle.fromAggregationForm(rootComponent.pathDeltaDistance(distanceStyle, x, y, z));
}
@Override
@@ -429,35 +397,18 @@ class GeoStandardPath extends GeoBasePath {
@Override
protected double outsideDistance(
final DistanceStyle distanceStyle, final double x, final double y, final double z) {
- double minDistance = Double.POSITIVE_INFINITY;
- for (final SegmentEndpoint endpoint : endPoints) {
- final double newDistance = endpoint.outsideDistance(distanceStyle, x, y, z);
- if (newDistance < minDistance) {
- minDistance = newDistance;
- }
+ if (rootComponent == null) {
+ return Double.POSITIVE_INFINITY;
}
- for (final PathSegment segment : segments) {
- final double newDistance = segment.outsideDistance(distanceStyle, x, y, z);
- if (newDistance < minDistance) {
- minDistance = newDistance;
- }
- }
- return minDistance;
+ return rootComponent.outsideDistance(distanceStyle, x, y, z);
}
@Override
public boolean isWithin(final double x, final double y, final double z) {
- for (SegmentEndpoint pathPoint : endPoints) {
- if (pathPoint.isWithin(x, y, z)) {
- return true;
- }
- }
- for (PathSegment pathSegment : segments) {
- if (pathSegment.isWithin(x, y, z)) {
- return true;
- }
+ if (rootComponent == null) {
+ return false;
}
- return false;
+ return rootComponent.isWithin(x, y, z);
}
@Override
@@ -478,49 +429,25 @@ class GeoStandardPath extends GeoBasePath {
// Well, sort of. We can detect intersections also due to overlap of segments with each other.
// But that's an edge case and we won't be optimizing for it.
// System.err.println(" Looking for intersection of plane " + plane + " with path " + this);
- for (final SegmentEndpoint pathPoint : endPoints) {
- if (pathPoint.intersects(plane, notablePoints, bounds)) {
- return true;
- }
- }
-
- for (final PathSegment pathSegment : segments) {
- if (pathSegment.intersects(plane, notablePoints, bounds)) {
- return true;
- }
+ if (rootComponent == null) {
+ return false;
}
-
- return false;
+ return rootComponent.intersects(plane, notablePoints, bounds);
}
@Override
public boolean intersects(GeoShape geoShape) {
- for (final SegmentEndpoint pathPoint : endPoints) {
- if (pathPoint.intersects(geoShape)) {
- return true;
- }
- }
-
- for (final PathSegment pathSegment : segments) {
- if (pathSegment.intersects(geoShape)) {
- return true;
- }
+ if (rootComponent == null) {
+ return false;
}
-
- return false;
+ return rootComponent.intersects(geoShape);
}
@Override
public void getBounds(Bounds bounds) {
super.getBounds(bounds);
- // For building bounds, order matters. We want to traverse
- // never more than 180 degrees longitude at a pop or we risk having the
- // bounds object get itself inverted. So do the edges first.
- for (PathSegment pathSegment : segments) {
- pathSegment.getBounds(bounds);
- }
- for (SegmentEndpoint pathPoint : endPoints) {
- pathPoint.getBounds(bounds);
+ if (rootComponent != null) {
+ rootComponent.getBounds(bounds);
}
}
@@ -700,6 +627,7 @@ class GeoStandardPath extends GeoBasePath {
bounds = new XYZBounds();
child1.getBounds(bounds);
child2.getBounds(bounds);
+ //System.out.println("Constructed PathNode with child1="+child1+" and child2="+child2+" with computed bounds "+bounds);
}
@Override
@@ -711,6 +639,8 @@ class GeoStandardPath extends GeoBasePath {
public boolean isWithin(final double x, final double y, final double z) {
// We computed the bounds for the node already, so use that as an "early-out".
// If we don't leave early, we need to check both children.
+ // This code breaks things; not sure why yet. TBD
+
if (x < bounds.getMinimumX() || x > bounds.getMaximumX()) {
return false;
}
@@ -720,6 +650,7 @@ class GeoStandardPath extends GeoBasePath {
if (z < bounds.getMinimumZ() || z > bounds.getMaximumZ()) {
return false;
}
+
return child1.isWithin(x, y, z) || child2.isWithin(x, y, z);
}
@@ -809,6 +740,11 @@ class GeoStandardPath extends GeoBasePath {
child2.getBounds(bounds);
}
}
+
+ @Override
+ public String toString() {
+ return "PathNode ("+child1+") ("+child2+")";
+ }
}
/**
@@ -827,9 +763,7 @@ class GeoStandardPath extends GeoBasePath {
private interface SegmentEndpoint extends PathComponent {}
/** Base implementation of SegmentEndpoint */
- private static class BaseSegmentEndpoint implements SegmentEndpoint {
- /** The planet model */
- protected final PlanetModel planetModel;
+ private static class BaseSegmentEndpoint extends GeoBaseBounds implements SegmentEndpoint {
/** The previous path element */
protected final PathComponent previous;
/** The center point of the endpoint */
@@ -839,7 +773,7 @@ class GeoStandardPath extends GeoBasePath {
public BaseSegmentEndpoint(
final PlanetModel planetModel, final PathComponent previous, final GeoPoint point) {
- this.planetModel = planetModel;
+ super(planetModel);
this.previous = previous;
this.point = point;
}
@@ -918,6 +852,7 @@ class GeoStandardPath extends GeoBasePath {
@Override
public void getBounds(final Bounds bounds) {
+ super.getBounds(bounds);
bounds.addPoint(point);
}
@@ -937,7 +872,7 @@ class GeoStandardPath extends GeoBasePath {
@Override
public String toString() {
- return point.toString();
+ return "SegmentEndpoint ("+point+")";
}
}
@@ -1269,9 +1204,7 @@ class GeoStandardPath extends GeoBasePath {
}
/** This is the pre-calculated data for a path segment. */
- private static class PathSegment implements PathComponent {
- /** Planet model */
- public final PlanetModel planetModel;
+ private static class PathSegment extends GeoBaseBounds implements PathComponent {
/** Previous path component */
public final PathComponent previous;
/** Starting point of the segment */
@@ -1319,7 +1252,7 @@ class GeoStandardPath extends GeoBasePath {
final GeoPoint end,
final Plane normalizedConnectingPlane,
final double planeBoundingOffset) {
- this.planetModel = planetModel;
+ super(planetModel);
this.previous = previous;
this.start = start;
this.end = end;
@@ -1724,6 +1657,7 @@ class GeoStandardPath extends GeoBasePath {
@Override
public void getBounds(final Bounds bounds) {
+ super.getBounds(bounds);
// We need to do all bounding planes as well as corner points
bounds
.addPoint(start)
@@ -1781,6 +1715,11 @@ class GeoStandardPath extends GeoBasePath {
startCutoffPlane,
lowerConnectingPlane);
}
+
+ @Override
+ public String toString() {
+ return "PathSegment ("+ULHC+", "+URHC+", "+LRHC+", "+LLHC+")";
+ }
}
private static class TreeBuilder {
@@ -1816,9 +1755,9 @@ class GeoStandardPath extends GeoBasePath {
private void mergeTop() {
depthStack.remove(depthStack.size() - 1);
- PathComponent firstComponent = componentStack.remove(componentStack.size() - 1);
- int newDepth = depthStack.remove(depthStack.size() - 1);
PathComponent secondComponent = componentStack.remove(componentStack.size() - 1);
+ int newDepth = depthStack.remove(depthStack.size() - 1) + 1;
+ PathComponent firstComponent = componentStack.remove(componentStack.size() - 1);
depthStack.add(newDepth);
componentStack.add(new PathNode(firstComponent, secondComponent));
}