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 <kwri...@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 <kwri...@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-unsubscr...@lucene.apache.org For additional commands, e-mail: dev-h...@lucene.apache.org
