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/20 01:22:09 UTC
[lucene] 02/03: 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 main
in repository https://gitbox.apache.org/repos/asf/lucene.git
commit 9bca7a70e10db81b39a5afb4498aab1006402031
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));
}
Re: [lucene] 02/03: Fix longstanding bug in path bounds calculation, and hook up efficient isWithin() and distance logic
Posted by Dawid Weiss <da...@gmail.com>.
If you need a temporary commit to make the random tests always pass while I
> diagnose and fix please let me know.
>
Please do, thanks.
Dawid
Re: [lucene] 02/03: Fix longstanding bug in path bounds calculation, and hook up efficient isWithin() and distance logic
Posted by Karl Wright <da...@gmail.com>.
These are randomized test failures occurring because a getBounds()
operation is apparently not always returning the right thing and the new
code depends on it being right.
I can make a commit that disables this logic if it's annoying but the
failures have been there all along. But now the code is more sensitive to
them. I already fixed another such issue with getBounds() for GeoPaths but
there's apparently more I didn't get before committing. If you need a
temporary commit to make the random tests always pass while I diagnose and
fix please let me know.
Karl
On Sun, Nov 20, 2022 at 1:49 AM Karl Wright <da...@gmail.com> wrote:
> I'm looking at it.
> Karl
>
>
> On Sat, Nov 19, 2022 at 11:41 PM Robert Muir <rc...@gmail.com> wrote:
>
>> Multiple spatial tests are failing in jenkins... bisected them to this
>> commit.
>>
>> Can you please look into it?
>> https://github.com/apache/lucene/issues/11956
>>
>> On Sat, Nov 19, 2022 at 8:22 PM <kw...@apache.org> wrote:
>> >
>> > This is an automated email from the ASF dual-hosted git repository.
>> >
>> > kwright pushed a commit to branch main
>> > in repository https://gitbox.apache.org/repos/asf/lucene.git
>> >
>> > commit 9bca7a70e10db81b39a5afb4498aab1006402031
>> > 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));
>> > }
>> >
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
>> For additional commands, e-mail: dev-help@lucene.apache.org
>>
>>
Re: [lucene] 02/03: Fix longstanding bug in path bounds calculation, and hook up efficient isWithin() and distance logic
Posted by Karl Wright <da...@gmail.com>.
I'm looking at it.
Karl
On Sat, Nov 19, 2022 at 11:41 PM Robert Muir <rc...@gmail.com> wrote:
> Multiple spatial tests are failing in jenkins... bisected them to this
> commit.
>
> Can you please look into it? https://github.com/apache/lucene/issues/11956
>
> On Sat, Nov 19, 2022 at 8:22 PM <kw...@apache.org> wrote:
> >
> > This is an automated email from the ASF dual-hosted git repository.
> >
> > kwright pushed a commit to branch main
> > in repository https://gitbox.apache.org/repos/asf/lucene.git
> >
> > commit 9bca7a70e10db81b39a5afb4498aab1006402031
> > 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));
> > }
> >
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail: dev-help@lucene.apache.org
>
>
Re: [lucene] 02/03: Fix longstanding bug in path bounds calculation, and hook up efficient isWithin() and distance logic
Posted by Robert Muir <rc...@gmail.com>.
Multiple spatial tests are failing in jenkins... bisected them to this commit.
Can you please look into it? https://github.com/apache/lucene/issues/11956
On Sat, Nov 19, 2022 at 8:22 PM <kw...@apache.org> wrote:
>
> This is an automated email from the ASF dual-hosted git repository.
>
> kwright pushed a commit to branch main
> in repository https://gitbox.apache.org/repos/asf/lucene.git
>
> commit 9bca7a70e10db81b39a5afb4498aab1006402031
> 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));
> }
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org