Mailing List Archive

Re: [lucene] 02/03: Fix longstanding bug in path bounds calculation, and hook up efficient isWithin() and distance logic
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 <kwright@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 <kwright@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 [ In reply to ]
I'm looking at it.
Karl


On Sat, Nov 19, 2022 at 11:41 PM Robert Muir <rcmuir@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 <kwright@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 <kwright@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 [ In reply to ]
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 <daddywri@gmail.com> wrote:

> I'm looking at it.
> Karl
>
>
> On Sat, Nov 19, 2022 at 11:41 PM Robert Muir <rcmuir@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 <kwright@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 <kwright@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 [ In reply to ]
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