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
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