You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by kw...@apache.org on 2022/11/20 01:22:07 UTC
[lucene] branch main updated (62f2b425025 -> 1e236090af5)
This is an automated email from the ASF dual-hosted git repository.
kwright pushed a change to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git
from 62f2b425025 Prevent TestStressIndexing from taking minutes for normal non-NIGHTLY runs (#11953)
new fbdb6552212 Add node structures and fast operations for them.
new 9bca7a70e10 Fix longstanding bug in path bounds calculation, and hook up efficient isWithin() and distance logic
new 1e236090af5 Fix up formatting
The 3 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
.../geom/{GeoBaseShape.java => GeoBaseBounds.java} | 6 +-
.../apache/lucene/spatial3d/geom/GeoBaseShape.java | 24 +-
.../geom/{GeoCircle.java => GeoBounds.java} | 4 +-
.../org/apache/lucene/spatial3d/geom/GeoShape.java | 2 +-
.../lucene/spatial3d/geom/GeoStandardPath.java | 588 ++++++++++++++-------
.../apache/lucene/spatial3d/geom/XYZBounds.java | 26 +
6 files changed, 434 insertions(+), 216 deletions(-)
copy lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/{GeoBaseShape.java => GeoBaseBounds.java} (90%)
copy lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/{GeoCircle.java => GeoBounds.java} (83%)
mode change 100755 => 100644
Re: [lucene] 02/03: Fix longstanding bug in path bounds calculation, and hook up efficient isWithin() and distance logic
Posted by Dawid Weiss <da...@gmail.com>.
If you need a temporary commit to make the random tests always pass while I
> diagnose and fix please let me know.
>
Please do, thanks.
Dawid
Re: [lucene] 02/03: Fix longstanding bug in path bounds calculation, and hook up efficient isWithin() and distance logic
Posted by Karl Wright <da...@gmail.com>.
These are randomized test failures occurring because a getBounds()
operation is apparently not always returning the right thing and the new
code depends on it being right.
I can make a commit that disables this logic if it's annoying but the
failures have been there all along. But now the code is more sensitive to
them. I already fixed another such issue with getBounds() for GeoPaths but
there's apparently more I didn't get before committing. If you need a
temporary commit to make the random tests always pass while I diagnose and
fix please let me know.
Karl
On Sun, Nov 20, 2022 at 1:49 AM Karl Wright <da...@gmail.com> wrote:
> I'm looking at it.
> Karl
>
>
> On Sat, Nov 19, 2022 at 11:41 PM Robert Muir <rc...@gmail.com> wrote:
>
>> Multiple spatial tests are failing in jenkins... bisected them to this
>> commit.
>>
>> Can you please look into it?
>> https://github.com/apache/lucene/issues/11956
>>
>> On Sat, Nov 19, 2022 at 8:22 PM <kw...@apache.org> wrote:
>> >
>> > This is an automated email from the ASF dual-hosted git repository.
>> >
>> > kwright pushed a commit to branch main
>> > in repository https://gitbox.apache.org/repos/asf/lucene.git
>> >
>> > commit 9bca7a70e10db81b39a5afb4498aab1006402031
>> > Author: Karl David Wright <kw...@apache.org>
>> > AuthorDate: Sat Nov 19 17:35:30 2022 -0500
>> >
>> > Fix longstanding bug in path bounds calculation, and hook up
>> efficient isWithin() and distance logic
>> > ---
>> > .../geom/{GeoBaseShape.java => GeoBaseBounds.java} | 6 +-
>> > .../apache/lucene/spatial3d/geom/GeoBaseShape.java | 24 +-
>> > .../apache/lucene/spatial3d/geom/GeoBounds.java | 27 ++
>> > .../org/apache/lucene/spatial3d/geom/GeoShape.java | 2 +-
>> > .../lucene/spatial3d/geom/GeoStandardPath.java | 277
>> ++++++++-------------
>> > 5 files changed, 140 insertions(+), 196 deletions(-)
>> >
>> > diff --git
>> a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
>> b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseBounds.java
>> > similarity index 90%
>> > copy from
>> lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
>> > copy to
>> lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseBounds.java
>> > index a5992392563..52030b333d3 100644
>> > ---
>> a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
>> > +++
>> b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseBounds.java
>> > @@ -17,18 +17,18 @@
>> > package org.apache.lucene.spatial3d.geom;
>> >
>> > /**
>> > - * Base extended shape object.
>> > + * Base object that supports bounds operations.
>> > *
>> > * @lucene.internal
>> > */
>> > -public abstract class GeoBaseShape extends BasePlanetObject implements
>> GeoShape {
>> > +public abstract class GeoBaseBounds extends BasePlanetObject
>> implements GeoBounds {
>> >
>> > /**
>> > * Constructor.
>> > *
>> > * @param planetModel is the planet model to use.
>> > */
>> > - public GeoBaseShape(final PlanetModel planetModel) {
>> > + public GeoBaseBounds(final PlanetModel planetModel) {
>> > super(planetModel);
>> > }
>> >
>> > diff --git
>> a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
>> b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
>> > index a5992392563..a4b5cd18a62 100644
>> > ---
>> a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
>> > +++
>> b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
>> > @@ -21,7 +21,7 @@ package org.apache.lucene.spatial3d.geom;
>> > *
>> > * @lucene.internal
>> > */
>> > -public abstract class GeoBaseShape extends BasePlanetObject implements
>> GeoShape {
>> > +public abstract class GeoBaseShape extends GeoBaseBounds implements
>> GeoShape {
>> >
>> > /**
>> > * Constructor.
>> > @@ -31,26 +31,4 @@ public abstract class GeoBaseShape extends
>> BasePlanetObject implements GeoShape
>> > public GeoBaseShape(final PlanetModel planetModel) {
>> > super(planetModel);
>> > }
>> > -
>> > - @Override
>> > - public void getBounds(Bounds bounds) {
>> > - if (isWithin(planetModel.NORTH_POLE)) {
>> > -
>> bounds.noTopLatitudeBound().noLongitudeBound().addPoint(planetModel.NORTH_POLE);
>> > - }
>> > - if (isWithin(planetModel.SOUTH_POLE)) {
>> > -
>> bounds.noBottomLatitudeBound().noLongitudeBound().addPoint(planetModel.SOUTH_POLE);
>> > - }
>> > - if (isWithin(planetModel.MIN_X_POLE)) {
>> > - bounds.addPoint(planetModel.MIN_X_POLE);
>> > - }
>> > - if (isWithin(planetModel.MAX_X_POLE)) {
>> > - bounds.addPoint(planetModel.MAX_X_POLE);
>> > - }
>> > - if (isWithin(planetModel.MIN_Y_POLE)) {
>> > - bounds.addPoint(planetModel.MIN_Y_POLE);
>> > - }
>> > - if (isWithin(planetModel.MAX_Y_POLE)) {
>> > - bounds.addPoint(planetModel.MAX_Y_POLE);
>> > - }
>> > - }
>> > }
>> > diff --git
>> a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBounds.java
>> b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBounds.java
>> > new file mode 100644
>> > index 00000000000..935366c5a08
>> > --- /dev/null
>> > +++
>> b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBounds.java
>> > @@ -0,0 +1,27 @@
>> > +/*
>> > + * Licensed to the Apache Software Foundation (ASF) under one or more
>> > + * contributor license agreements. See the NOTICE file distributed
>> with
>> > + * this work for additional information regarding copyright ownership.
>> > + * The ASF licenses this file to You under the Apache License, Version
>> 2.0
>> > + * (the "License"); you may not use this file except in compliance with
>> > + * the License. You may obtain a copy of the License at
>> > + *
>> > + * http://www.apache.org/licenses/LICENSE-2.0
>> > + *
>> > + * Unless required by applicable law or agreed to in writing, software
>> > + * distributed under the License is distributed on an "AS IS" BASIS,
>> > + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
>> implied.
>> > + * See the License for the specific language governing permissions and
>> > + * limitations under the License.
>> > + */
>> > +package org.apache.lucene.spatial3d.geom;
>> > +
>> > +/**
>> > + * Generic shape that supports bounds. This describes methods that help
>> > + * shapes compute their bounds.
>> > + *
>> > + * @lucene.experimental
>> > + */
>> > +public interface GeoBounds extends Bounded, Membership, PlanetObject {
>> > +
>> > +}
>> > diff --git
>> a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoShape.java
>> b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoShape.java
>> > index 8262ecf5a9e..4e32b9e03e8 100755
>> > ---
>> a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoShape.java
>> > +++
>> b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoShape.java
>> > @@ -22,7 +22,7 @@ package org.apache.lucene.spatial3d.geom;
>> > *
>> > * @lucene.experimental
>> > */
>> > -public interface GeoShape extends Bounded, Membership, PlanetObject {
>> > +public interface GeoShape extends GeoBounds {
>> >
>> > /**
>> > * Return a sample point that is on the outside edge/boundary of the
>> shape.
>> > diff --git
>> a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoStandardPath.java
>> b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoStandardPath.java
>> > index 1f997100e1a..16a07009b64 100755
>> > ---
>> a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoStandardPath.java
>> > +++
>> b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoStandardPath.java
>> > @@ -188,82 +188,83 @@ class GeoStandardPath extends GeoBasePath {
>> > new GeoPoint[] {
>> >
>> onlyEndpoint.circlePlane.getSampleIntersectionPoint(planetModel,
>> normalPlane)
>> > };
>> > - return;
>> > - }
>> > -
>> > - // Create segment endpoints. Use an appropriate constructor for
>> the start and end of the path.
>> > - for (int i = 0; i < segments.size(); i++) {
>> > - final PathSegment currentSegment = segments.get(i);
>> > -
>> > - if (i == 0) {
>> > - // Starting endpoint
>> > - final SegmentEndpoint startEndpoint =
>> > + } else {
>> > + // Create segment endpoints. Use an appropriate constructor for
>> the start and end of the path.
>> > + for (int i = 0; i < segments.size(); i++) {
>> > + final PathSegment currentSegment = segments.get(i);
>> > +
>> > + if (i == 0) {
>> > + // Starting endpoint
>> > + final SegmentEndpoint startEndpoint =
>> > new CutoffSingleCircleSegmentEndpoint(
>> > - planetModel,
>> > - null,
>> > - currentSegment.start,
>> > - currentSegment.startCutoffPlane,
>> > - currentSegment.ULHC,
>> > - currentSegment.LLHC);
>> > - endPoints.add(startEndpoint);
>> > - this.edgePoints = new GeoPoint[] {currentSegment.ULHC};
>> > - continue;
>> > - }
>> > + planetModel,
>> > + null,
>> > + currentSegment.start,
>> > +
>> currentSegment.startCutoffPlane,
>> > + currentSegment.ULHC,
>> > + currentSegment.LLHC);
>> > + endPoints.add(startEndpoint);
>> > + this.edgePoints = new GeoPoint[] {currentSegment.ULHC};
>> > + continue;
>> > + }
>> >
>> > - // General intersection case
>> > - final PathSegment prevSegment = segments.get(i - 1);
>> > - if (prevSegment.endCutoffPlane.isWithin(currentSegment.ULHC)
>> > - && prevSegment.endCutoffPlane.isWithin(currentSegment.LLHC)
>> > - && currentSegment.startCutoffPlane.isWithin(prevSegment.URHC)
>> > - &&
>> currentSegment.startCutoffPlane.isWithin(prevSegment.LRHC)) {
>> > - // The planes are identical. We wouldn't need a circle at all
>> except for the possibility of
>> > - // backing up, which is hard to detect here.
>> > - final SegmentEndpoint midEndpoint =
>> > + // General intersection case
>> > + final PathSegment prevSegment = segments.get(i - 1);
>> > + if (prevSegment.endCutoffPlane.isWithin(currentSegment.ULHC)
>> > + && prevSegment.endCutoffPlane.isWithin(currentSegment.LLHC)
>> > + &&
>> currentSegment.startCutoffPlane.isWithin(prevSegment.URHC)
>> > + &&
>> currentSegment.startCutoffPlane.isWithin(prevSegment.LRHC)) {
>> > + // The planes are identical. We wouldn't need a circle at
>> all except for the possibility of
>> > + // backing up, which is hard to detect here.
>> > + final SegmentEndpoint midEndpoint =
>> > new CutoffSingleCircleSegmentEndpoint(
>> > - planetModel,
>> > - prevSegment,
>> > - currentSegment.start,
>> > - prevSegment.endCutoffPlane,
>> > - currentSegment.startCutoffPlane,
>> > - currentSegment.ULHC,
>> > - currentSegment.LLHC);
>> > - // don't need a circle at all. Special constructor...
>> > - endPoints.add(midEndpoint);
>> > - } else {
>> > - endPoints.add(
>> > - new CutoffDualCircleSegmentEndpoint(
>> > - planetModel,
>> > - prevSegment,
>> > - currentSegment.start,
>> > - prevSegment.endCutoffPlane,
>> > - currentSegment.startCutoffPlane,
>> > - prevSegment.URHC,
>> > - prevSegment.LRHC,
>> > - currentSegment.ULHC,
>> > - currentSegment.LLHC));
>> > + planetModel,
>> > + prevSegment,
>> > + currentSegment.start,
>> > +
>> prevSegment.endCutoffPlane,
>> > +
>> currentSegment.startCutoffPlane,
>> > + currentSegment.ULHC,
>> > + currentSegment.LLHC);
>> > + // don't need a circle at all. Special constructor...
>> > + endPoints.add(midEndpoint);
>> > + } else {
>> > + endPoints.add(
>> > + new CutoffDualCircleSegmentEndpoint(
>> > +
>> planetModel,
>> > +
>> prevSegment,
>> > +
>> currentSegment.start,
>> > +
>> prevSegment.endCutoffPlane,
>> > +
>> currentSegment.startCutoffPlane,
>> > +
>> prevSegment.URHC,
>> > +
>> prevSegment.LRHC,
>> > +
>> currentSegment.ULHC,
>> > +
>> currentSegment.LLHC));
>> > + }
>> > }
>> > + // Do final endpoint
>> > + final PathSegment lastSegment = segments.get(segments.size() -
>> 1);
>> > + endPoints.add(
>> > + new CutoffSingleCircleSegmentEndpoint(
>> > + planetModel,
>> > + lastSegment,
>> > +
>> lastSegment.end,
>> > +
>> lastSegment.endCutoffPlane,
>> > +
>> lastSegment.URHC,
>> > +
>> lastSegment.LRHC));
>> > }
>> > - // Do final endpoint
>> > - final PathSegment lastSegment = segments.get(segments.size() - 1);
>> > - endPoints.add(
>> > - new CutoffSingleCircleSegmentEndpoint(
>> > - planetModel,
>> > - lastSegment,
>> > - lastSegment.end,
>> > - lastSegment.endCutoffPlane,
>> > - lastSegment.URHC,
>> > - lastSegment.LRHC));
>> >
>> > final TreeBuilder treeBuilder = new TreeBuilder(segments.size() +
>> endPoints.size());
>> > // Segments will have one less than the number of endpoints.
>> > // So, we add the first endpoint, and then do it pairwise.
>> > - treeBuilder.addComponent(segments.get(0));
>> > + treeBuilder.addComponent(endPoints.get(0));
>> > for (int i = 0; i < segments.size(); i++) {
>> > treeBuilder.addComponent(segments.get(i));
>> > treeBuilder.addComponent(endPoints.get(i + 1));
>> > }
>> >
>> > rootComponent = treeBuilder.getRoot();
>> > +
>> > + //System.out.println("Root component: "+rootComponent);
>> > }
>> >
>> > /**
>> > @@ -289,28 +290,16 @@ class GeoStandardPath extends GeoBasePath {
>> > @Override
>> > public double computePathCenterDistance(
>> > final DistanceStyle distanceStyle, final double x, final double
>> y, final double z) {
>> > - // Walk along path and keep track of the closest distance we find
>> > - double closestDistance = Double.POSITIVE_INFINITY;
>> > - // Segments first
>> > - for (PathSegment segment : segments) {
>> > - final double segmentDistance =
>> segment.pathCenterDistance(distanceStyle, x, y, z);
>> > - if (segmentDistance < closestDistance) {
>> > - closestDistance = segmentDistance;
>> > - }
>> > + if (rootComponent == null) {
>> > + return Double.POSITIVE_INFINITY;
>> > }
>> > - // Now, endpoints
>> > - for (SegmentEndpoint endpoint : endPoints) {
>> > - final double endpointDistance =
>> endpoint.pathCenterDistance(distanceStyle, x, y, z);
>> > - if (endpointDistance < closestDistance) {
>> > - closestDistance = endpointDistance;
>> > - }
>> > - }
>> > - return closestDistance;
>> > + return rootComponent.pathCenterDistance(distanceStyle, x, y, z);
>> > }
>> >
>> > @Override
>> > public double computeNearestDistance(
>> > final DistanceStyle distanceStyle, final double x, final double
>> y, final double z) {
>> > + // MHL - need another abstraction method for this
>> > double currentDistance = 0.0;
>> > double minPathCenterDistance = Double.POSITIVE_INFINITY;
>> > double bestDistance = Double.POSITIVE_INFINITY;
>> > @@ -344,6 +333,8 @@ class GeoStandardPath extends GeoBasePath {
>> > @Override
>> > protected double distance(
>> > final DistanceStyle distanceStyle, final double x, final double
>> y, final double z) {
>> > + // MHL - need another method in the abstraction!
>> > +
>> > // Algorithm:
>> > // (1) If the point is within any of the segments along the path,
>> return that value.
>> > // (2) If the point is within any of the segment end circles along
>> the path, return that value.
>> > @@ -390,33 +381,10 @@ class GeoStandardPath extends GeoBasePath {
>> > @Override
>> > protected double deltaDistance(
>> > final DistanceStyle distanceStyle, final double x, final double
>> y, final double z) {
>> > - // Algorithm:
>> > - // (1) If the point is within any of the segments along the path,
>> return that value.
>> > - // (2) If the point is within any of the segment end circles along
>> the path, return that value.
>> > - // Finds best distance
>> > - double bestDistance = Double.POSITIVE_INFINITY;
>> > -
>> > - for (final PathSegment segment : segments) {
>> > - final double distance = segment.pathDeltaDistance(distanceStyle,
>> x, y, z);
>> > - if (distance != Double.POSITIVE_INFINITY) {
>> > - final double thisDistance =
>> distanceStyle.fromAggregationForm(distance);
>> > - if (thisDistance < bestDistance) {
>> > - bestDistance = thisDistance;
>> > - }
>> > - }
>> > + if (rootComponent == null) {
>> > + return Double.POSITIVE_INFINITY;
>> > }
>> > -
>> > - for (final SegmentEndpoint endpoint : endPoints) {
>> > - final double distance =
>> endpoint.pathDeltaDistance(distanceStyle, x, y, z);
>> > - if (distance != Double.POSITIVE_INFINITY) {
>> > - final double thisDistance =
>> distanceStyle.fromAggregationForm(distance);
>> > - if (thisDistance < bestDistance) {
>> > - bestDistance = thisDistance;
>> > - }
>> > - }
>> > - }
>> > -
>> > - return bestDistance;
>> > + return
>> distanceStyle.fromAggregationForm(rootComponent.pathDeltaDistance(distanceStyle,
>> x, y, z));
>> > }
>> >
>> > @Override
>> > @@ -429,35 +397,18 @@ class GeoStandardPath extends GeoBasePath {
>> > @Override
>> > protected double outsideDistance(
>> > final DistanceStyle distanceStyle, final double x, final double
>> y, final double z) {
>> > - double minDistance = Double.POSITIVE_INFINITY;
>> > - for (final SegmentEndpoint endpoint : endPoints) {
>> > - final double newDistance =
>> endpoint.outsideDistance(distanceStyle, x, y, z);
>> > - if (newDistance < minDistance) {
>> > - minDistance = newDistance;
>> > - }
>> > + if (rootComponent == null) {
>> > + return Double.POSITIVE_INFINITY;
>> > }
>> > - for (final PathSegment segment : segments) {
>> > - final double newDistance =
>> segment.outsideDistance(distanceStyle, x, y, z);
>> > - if (newDistance < minDistance) {
>> > - minDistance = newDistance;
>> > - }
>> > - }
>> > - return minDistance;
>> > + return rootComponent.outsideDistance(distanceStyle, x, y, z);
>> > }
>> >
>> > @Override
>> > public boolean isWithin(final double x, final double y, final double
>> z) {
>> > - for (SegmentEndpoint pathPoint : endPoints) {
>> > - if (pathPoint.isWithin(x, y, z)) {
>> > - return true;
>> > - }
>> > - }
>> > - for (PathSegment pathSegment : segments) {
>> > - if (pathSegment.isWithin(x, y, z)) {
>> > - return true;
>> > - }
>> > + if (rootComponent == null) {
>> > + return false;
>> > }
>> > - return false;
>> > + return rootComponent.isWithin(x, y, z);
>> > }
>> >
>> > @Override
>> > @@ -478,49 +429,25 @@ class GeoStandardPath extends GeoBasePath {
>> > // Well, sort of. We can detect intersections also due to overlap
>> of segments with each other.
>> > // But that's an edge case and we won't be optimizing for it.
>> > // System.err.println(" Looking for intersection of plane " +
>> plane + " with path " + this);
>> > - for (final SegmentEndpoint pathPoint : endPoints) {
>> > - if (pathPoint.intersects(plane, notablePoints, bounds)) {
>> > - return true;
>> > - }
>> > - }
>> > -
>> > - for (final PathSegment pathSegment : segments) {
>> > - if (pathSegment.intersects(plane, notablePoints, bounds)) {
>> > - return true;
>> > - }
>> > + if (rootComponent == null) {
>> > + return false;
>> > }
>> > -
>> > - return false;
>> > + return rootComponent.intersects(plane, notablePoints, bounds);
>> > }
>> >
>> > @Override
>> > public boolean intersects(GeoShape geoShape) {
>> > - for (final SegmentEndpoint pathPoint : endPoints) {
>> > - if (pathPoint.intersects(geoShape)) {
>> > - return true;
>> > - }
>> > - }
>> > -
>> > - for (final PathSegment pathSegment : segments) {
>> > - if (pathSegment.intersects(geoShape)) {
>> > - return true;
>> > - }
>> > + if (rootComponent == null) {
>> > + return false;
>> > }
>> > -
>> > - return false;
>> > + return rootComponent.intersects(geoShape);
>> > }
>> >
>> > @Override
>> > public void getBounds(Bounds bounds) {
>> > super.getBounds(bounds);
>> > - // For building bounds, order matters. We want to traverse
>> > - // never more than 180 degrees longitude at a pop or we risk
>> having the
>> > - // bounds object get itself inverted. So do the edges first.
>> > - for (PathSegment pathSegment : segments) {
>> > - pathSegment.getBounds(bounds);
>> > - }
>> > - for (SegmentEndpoint pathPoint : endPoints) {
>> > - pathPoint.getBounds(bounds);
>> > + if (rootComponent != null) {
>> > + rootComponent.getBounds(bounds);
>> > }
>> > }
>> >
>> > @@ -700,6 +627,7 @@ class GeoStandardPath extends GeoBasePath {
>> > bounds = new XYZBounds();
>> > child1.getBounds(bounds);
>> > child2.getBounds(bounds);
>> > + //System.out.println("Constructed PathNode with
>> child1="+child1+" and child2="+child2+" with computed bounds "+bounds);
>> > }
>> >
>> > @Override
>> > @@ -711,6 +639,8 @@ class GeoStandardPath extends GeoBasePath {
>> > public boolean isWithin(final double x, final double y, final
>> double z) {
>> > // We computed the bounds for the node already, so use that as
>> an "early-out".
>> > // If we don't leave early, we need to check both children.
>> > + // This code breaks things; not sure why yet. TBD
>> > +
>> > if (x < bounds.getMinimumX() || x > bounds.getMaximumX()) {
>> > return false;
>> > }
>> > @@ -720,6 +650,7 @@ class GeoStandardPath extends GeoBasePath {
>> > if (z < bounds.getMinimumZ() || z > bounds.getMaximumZ()) {
>> > return false;
>> > }
>> > +
>> > return child1.isWithin(x, y, z) || child2.isWithin(x, y, z);
>> > }
>> >
>> > @@ -809,6 +740,11 @@ class GeoStandardPath extends GeoBasePath {
>> > child2.getBounds(bounds);
>> > }
>> > }
>> > +
>> > + @Override
>> > + public String toString() {
>> > + return "PathNode ("+child1+") ("+child2+")";
>> > + }
>> > }
>> >
>> > /**
>> > @@ -827,9 +763,7 @@ class GeoStandardPath extends GeoBasePath {
>> > private interface SegmentEndpoint extends PathComponent {}
>> >
>> > /** Base implementation of SegmentEndpoint */
>> > - private static class BaseSegmentEndpoint implements SegmentEndpoint {
>> > - /** The planet model */
>> > - protected final PlanetModel planetModel;
>> > + private static class BaseSegmentEndpoint extends GeoBaseBounds
>> implements SegmentEndpoint {
>> > /** The previous path element */
>> > protected final PathComponent previous;
>> > /** The center point of the endpoint */
>> > @@ -839,7 +773,7 @@ class GeoStandardPath extends GeoBasePath {
>> >
>> > public BaseSegmentEndpoint(
>> > final PlanetModel planetModel, final PathComponent previous,
>> final GeoPoint point) {
>> > - this.planetModel = planetModel;
>> > + super(planetModel);
>> > this.previous = previous;
>> > this.point = point;
>> > }
>> > @@ -918,6 +852,7 @@ class GeoStandardPath extends GeoBasePath {
>> >
>> > @Override
>> > public void getBounds(final Bounds bounds) {
>> > + super.getBounds(bounds);
>> > bounds.addPoint(point);
>> > }
>> >
>> > @@ -937,7 +872,7 @@ class GeoStandardPath extends GeoBasePath {
>> >
>> > @Override
>> > public String toString() {
>> > - return point.toString();
>> > + return "SegmentEndpoint ("+point+")";
>> > }
>> > }
>> >
>> > @@ -1269,9 +1204,7 @@ class GeoStandardPath extends GeoBasePath {
>> > }
>> >
>> > /** This is the pre-calculated data for a path segment. */
>> > - private static class PathSegment implements PathComponent {
>> > - /** Planet model */
>> > - public final PlanetModel planetModel;
>> > + private static class PathSegment extends GeoBaseBounds implements
>> PathComponent {
>> > /** Previous path component */
>> > public final PathComponent previous;
>> > /** Starting point of the segment */
>> > @@ -1319,7 +1252,7 @@ class GeoStandardPath extends GeoBasePath {
>> > final GeoPoint end,
>> > final Plane normalizedConnectingPlane,
>> > final double planeBoundingOffset) {
>> > - this.planetModel = planetModel;
>> > + super(planetModel);
>> > this.previous = previous;
>> > this.start = start;
>> > this.end = end;
>> > @@ -1724,6 +1657,7 @@ class GeoStandardPath extends GeoBasePath {
>> >
>> > @Override
>> > public void getBounds(final Bounds bounds) {
>> > + super.getBounds(bounds);
>> > // We need to do all bounding planes as well as corner points
>> > bounds
>> > .addPoint(start)
>> > @@ -1781,6 +1715,11 @@ class GeoStandardPath extends GeoBasePath {
>> > startCutoffPlane,
>> > lowerConnectingPlane);
>> > }
>> > +
>> > + @Override
>> > + public String toString() {
>> > + return "PathSegment ("+ULHC+", "+URHC+", "+LRHC+", "+LLHC+")";
>> > + }
>> > }
>> >
>> > private static class TreeBuilder {
>> > @@ -1816,9 +1755,9 @@ class GeoStandardPath extends GeoBasePath {
>> >
>> > private void mergeTop() {
>> > depthStack.remove(depthStack.size() - 1);
>> > - PathComponent firstComponent =
>> componentStack.remove(componentStack.size() - 1);
>> > - int newDepth = depthStack.remove(depthStack.size() - 1);
>> > PathComponent secondComponent =
>> componentStack.remove(componentStack.size() - 1);
>> > + int newDepth = depthStack.remove(depthStack.size() - 1) + 1;
>> > + PathComponent firstComponent =
>> componentStack.remove(componentStack.size() - 1);
>> > depthStack.add(newDepth);
>> > componentStack.add(new PathNode(firstComponent,
>> secondComponent));
>> > }
>> >
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
>> For additional commands, e-mail: dev-help@lucene.apache.org
>>
>>
Re: [lucene] 02/03: Fix longstanding bug in path bounds calculation, and hook up efficient isWithin() and distance logic
Posted by Karl Wright <da...@gmail.com>.
I'm looking at it.
Karl
On Sat, Nov 19, 2022 at 11:41 PM Robert Muir <rc...@gmail.com> wrote:
> Multiple spatial tests are failing in jenkins... bisected them to this
> commit.
>
> Can you please look into it? https://github.com/apache/lucene/issues/11956
>
> On Sat, Nov 19, 2022 at 8:22 PM <kw...@apache.org> wrote:
> >
> > This is an automated email from the ASF dual-hosted git repository.
> >
> > kwright pushed a commit to branch main
> > in repository https://gitbox.apache.org/repos/asf/lucene.git
> >
> > commit 9bca7a70e10db81b39a5afb4498aab1006402031
> > Author: Karl David Wright <kw...@apache.org>
> > AuthorDate: Sat Nov 19 17:35:30 2022 -0500
> >
> > Fix longstanding bug in path bounds calculation, and hook up
> efficient isWithin() and distance logic
> > ---
> > .../geom/{GeoBaseShape.java => GeoBaseBounds.java} | 6 +-
> > .../apache/lucene/spatial3d/geom/GeoBaseShape.java | 24 +-
> > .../apache/lucene/spatial3d/geom/GeoBounds.java | 27 ++
> > .../org/apache/lucene/spatial3d/geom/GeoShape.java | 2 +-
> > .../lucene/spatial3d/geom/GeoStandardPath.java | 277
> ++++++++-------------
> > 5 files changed, 140 insertions(+), 196 deletions(-)
> >
> > diff --git
> a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
> b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseBounds.java
> > similarity index 90%
> > copy from
> lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
> > copy to
> lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseBounds.java
> > index a5992392563..52030b333d3 100644
> > ---
> a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
> > +++
> b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseBounds.java
> > @@ -17,18 +17,18 @@
> > package org.apache.lucene.spatial3d.geom;
> >
> > /**
> > - * Base extended shape object.
> > + * Base object that supports bounds operations.
> > *
> > * @lucene.internal
> > */
> > -public abstract class GeoBaseShape extends BasePlanetObject implements
> GeoShape {
> > +public abstract class GeoBaseBounds extends BasePlanetObject implements
> GeoBounds {
> >
> > /**
> > * Constructor.
> > *
> > * @param planetModel is the planet model to use.
> > */
> > - public GeoBaseShape(final PlanetModel planetModel) {
> > + public GeoBaseBounds(final PlanetModel planetModel) {
> > super(planetModel);
> > }
> >
> > diff --git
> a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
> b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
> > index a5992392563..a4b5cd18a62 100644
> > ---
> a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
> > +++
> b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
> > @@ -21,7 +21,7 @@ package org.apache.lucene.spatial3d.geom;
> > *
> > * @lucene.internal
> > */
> > -public abstract class GeoBaseShape extends BasePlanetObject implements
> GeoShape {
> > +public abstract class GeoBaseShape extends GeoBaseBounds implements
> GeoShape {
> >
> > /**
> > * Constructor.
> > @@ -31,26 +31,4 @@ public abstract class GeoBaseShape extends
> BasePlanetObject implements GeoShape
> > public GeoBaseShape(final PlanetModel planetModel) {
> > super(planetModel);
> > }
> > -
> > - @Override
> > - public void getBounds(Bounds bounds) {
> > - if (isWithin(planetModel.NORTH_POLE)) {
> > -
> bounds.noTopLatitudeBound().noLongitudeBound().addPoint(planetModel.NORTH_POLE);
> > - }
> > - if (isWithin(planetModel.SOUTH_POLE)) {
> > -
> bounds.noBottomLatitudeBound().noLongitudeBound().addPoint(planetModel.SOUTH_POLE);
> > - }
> > - if (isWithin(planetModel.MIN_X_POLE)) {
> > - bounds.addPoint(planetModel.MIN_X_POLE);
> > - }
> > - if (isWithin(planetModel.MAX_X_POLE)) {
> > - bounds.addPoint(planetModel.MAX_X_POLE);
> > - }
> > - if (isWithin(planetModel.MIN_Y_POLE)) {
> > - bounds.addPoint(planetModel.MIN_Y_POLE);
> > - }
> > - if (isWithin(planetModel.MAX_Y_POLE)) {
> > - bounds.addPoint(planetModel.MAX_Y_POLE);
> > - }
> > - }
> > }
> > diff --git
> a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBounds.java
> b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBounds.java
> > new file mode 100644
> > index 00000000000..935366c5a08
> > --- /dev/null
> > +++
> b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBounds.java
> > @@ -0,0 +1,27 @@
> > +/*
> > + * Licensed to the Apache Software Foundation (ASF) under one or more
> > + * contributor license agreements. See the NOTICE file distributed with
> > + * this work for additional information regarding copyright ownership.
> > + * The ASF licenses this file to You under the Apache License, Version
> 2.0
> > + * (the "License"); you may not use this file except in compliance with
> > + * the License. You may obtain a copy of the License at
> > + *
> > + * http://www.apache.org/licenses/LICENSE-2.0
> > + *
> > + * Unless required by applicable law or agreed to in writing, software
> > + * distributed under the License is distributed on an "AS IS" BASIS,
> > + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
> implied.
> > + * See the License for the specific language governing permissions and
> > + * limitations under the License.
> > + */
> > +package org.apache.lucene.spatial3d.geom;
> > +
> > +/**
> > + * Generic shape that supports bounds. This describes methods that help
> > + * shapes compute their bounds.
> > + *
> > + * @lucene.experimental
> > + */
> > +public interface GeoBounds extends Bounded, Membership, PlanetObject {
> > +
> > +}
> > diff --git
> a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoShape.java
> b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoShape.java
> > index 8262ecf5a9e..4e32b9e03e8 100755
> > ---
> a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoShape.java
> > +++
> b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoShape.java
> > @@ -22,7 +22,7 @@ package org.apache.lucene.spatial3d.geom;
> > *
> > * @lucene.experimental
> > */
> > -public interface GeoShape extends Bounded, Membership, PlanetObject {
> > +public interface GeoShape extends GeoBounds {
> >
> > /**
> > * Return a sample point that is on the outside edge/boundary of the
> shape.
> > diff --git
> a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoStandardPath.java
> b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoStandardPath.java
> > index 1f997100e1a..16a07009b64 100755
> > ---
> a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoStandardPath.java
> > +++
> b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoStandardPath.java
> > @@ -188,82 +188,83 @@ class GeoStandardPath extends GeoBasePath {
> > new GeoPoint[] {
> >
> onlyEndpoint.circlePlane.getSampleIntersectionPoint(planetModel,
> normalPlane)
> > };
> > - return;
> > - }
> > -
> > - // Create segment endpoints. Use an appropriate constructor for
> the start and end of the path.
> > - for (int i = 0; i < segments.size(); i++) {
> > - final PathSegment currentSegment = segments.get(i);
> > -
> > - if (i == 0) {
> > - // Starting endpoint
> > - final SegmentEndpoint startEndpoint =
> > + } else {
> > + // Create segment endpoints. Use an appropriate constructor for
> the start and end of the path.
> > + for (int i = 0; i < segments.size(); i++) {
> > + final PathSegment currentSegment = segments.get(i);
> > +
> > + if (i == 0) {
> > + // Starting endpoint
> > + final SegmentEndpoint startEndpoint =
> > new CutoffSingleCircleSegmentEndpoint(
> > - planetModel,
> > - null,
> > - currentSegment.start,
> > - currentSegment.startCutoffPlane,
> > - currentSegment.ULHC,
> > - currentSegment.LLHC);
> > - endPoints.add(startEndpoint);
> > - this.edgePoints = new GeoPoint[] {currentSegment.ULHC};
> > - continue;
> > - }
> > + planetModel,
> > + null,
> > + currentSegment.start,
> > +
> currentSegment.startCutoffPlane,
> > + currentSegment.ULHC,
> > + currentSegment.LLHC);
> > + endPoints.add(startEndpoint);
> > + this.edgePoints = new GeoPoint[] {currentSegment.ULHC};
> > + continue;
> > + }
> >
> > - // General intersection case
> > - final PathSegment prevSegment = segments.get(i - 1);
> > - if (prevSegment.endCutoffPlane.isWithin(currentSegment.ULHC)
> > - && prevSegment.endCutoffPlane.isWithin(currentSegment.LLHC)
> > - && currentSegment.startCutoffPlane.isWithin(prevSegment.URHC)
> > - &&
> currentSegment.startCutoffPlane.isWithin(prevSegment.LRHC)) {
> > - // The planes are identical. We wouldn't need a circle at all
> except for the possibility of
> > - // backing up, which is hard to detect here.
> > - final SegmentEndpoint midEndpoint =
> > + // General intersection case
> > + final PathSegment prevSegment = segments.get(i - 1);
> > + if (prevSegment.endCutoffPlane.isWithin(currentSegment.ULHC)
> > + && prevSegment.endCutoffPlane.isWithin(currentSegment.LLHC)
> > + &&
> currentSegment.startCutoffPlane.isWithin(prevSegment.URHC)
> > + &&
> currentSegment.startCutoffPlane.isWithin(prevSegment.LRHC)) {
> > + // The planes are identical. We wouldn't need a circle at
> all except for the possibility of
> > + // backing up, which is hard to detect here.
> > + final SegmentEndpoint midEndpoint =
> > new CutoffSingleCircleSegmentEndpoint(
> > - planetModel,
> > - prevSegment,
> > - currentSegment.start,
> > - prevSegment.endCutoffPlane,
> > - currentSegment.startCutoffPlane,
> > - currentSegment.ULHC,
> > - currentSegment.LLHC);
> > - // don't need a circle at all. Special constructor...
> > - endPoints.add(midEndpoint);
> > - } else {
> > - endPoints.add(
> > - new CutoffDualCircleSegmentEndpoint(
> > - planetModel,
> > - prevSegment,
> > - currentSegment.start,
> > - prevSegment.endCutoffPlane,
> > - currentSegment.startCutoffPlane,
> > - prevSegment.URHC,
> > - prevSegment.LRHC,
> > - currentSegment.ULHC,
> > - currentSegment.LLHC));
> > + planetModel,
> > + prevSegment,
> > + currentSegment.start,
> > +
> prevSegment.endCutoffPlane,
> > +
> currentSegment.startCutoffPlane,
> > + currentSegment.ULHC,
> > + currentSegment.LLHC);
> > + // don't need a circle at all. Special constructor...
> > + endPoints.add(midEndpoint);
> > + } else {
> > + endPoints.add(
> > + new CutoffDualCircleSegmentEndpoint(
> > + planetModel,
> > + prevSegment,
> > +
> currentSegment.start,
> > +
> prevSegment.endCutoffPlane,
> > +
> currentSegment.startCutoffPlane,
> > +
> prevSegment.URHC,
> > +
> prevSegment.LRHC,
> > +
> currentSegment.ULHC,
> > +
> currentSegment.LLHC));
> > + }
> > }
> > + // Do final endpoint
> > + final PathSegment lastSegment = segments.get(segments.size() - 1);
> > + endPoints.add(
> > + new CutoffSingleCircleSegmentEndpoint(
> > + planetModel,
> > + lastSegment,
> > +
> lastSegment.end,
> > +
> lastSegment.endCutoffPlane,
> > +
> lastSegment.URHC,
> > +
> lastSegment.LRHC));
> > }
> > - // Do final endpoint
> > - final PathSegment lastSegment = segments.get(segments.size() - 1);
> > - endPoints.add(
> > - new CutoffSingleCircleSegmentEndpoint(
> > - planetModel,
> > - lastSegment,
> > - lastSegment.end,
> > - lastSegment.endCutoffPlane,
> > - lastSegment.URHC,
> > - lastSegment.LRHC));
> >
> > final TreeBuilder treeBuilder = new TreeBuilder(segments.size() +
> endPoints.size());
> > // Segments will have one less than the number of endpoints.
> > // So, we add the first endpoint, and then do it pairwise.
> > - treeBuilder.addComponent(segments.get(0));
> > + treeBuilder.addComponent(endPoints.get(0));
> > for (int i = 0; i < segments.size(); i++) {
> > treeBuilder.addComponent(segments.get(i));
> > treeBuilder.addComponent(endPoints.get(i + 1));
> > }
> >
> > rootComponent = treeBuilder.getRoot();
> > +
> > + //System.out.println("Root component: "+rootComponent);
> > }
> >
> > /**
> > @@ -289,28 +290,16 @@ class GeoStandardPath extends GeoBasePath {
> > @Override
> > public double computePathCenterDistance(
> > final DistanceStyle distanceStyle, final double x, final double
> y, final double z) {
> > - // Walk along path and keep track of the closest distance we find
> > - double closestDistance = Double.POSITIVE_INFINITY;
> > - // Segments first
> > - for (PathSegment segment : segments) {
> > - final double segmentDistance =
> segment.pathCenterDistance(distanceStyle, x, y, z);
> > - if (segmentDistance < closestDistance) {
> > - closestDistance = segmentDistance;
> > - }
> > + if (rootComponent == null) {
> > + return Double.POSITIVE_INFINITY;
> > }
> > - // Now, endpoints
> > - for (SegmentEndpoint endpoint : endPoints) {
> > - final double endpointDistance =
> endpoint.pathCenterDistance(distanceStyle, x, y, z);
> > - if (endpointDistance < closestDistance) {
> > - closestDistance = endpointDistance;
> > - }
> > - }
> > - return closestDistance;
> > + return rootComponent.pathCenterDistance(distanceStyle, x, y, z);
> > }
> >
> > @Override
> > public double computeNearestDistance(
> > final DistanceStyle distanceStyle, final double x, final double
> y, final double z) {
> > + // MHL - need another abstraction method for this
> > double currentDistance = 0.0;
> > double minPathCenterDistance = Double.POSITIVE_INFINITY;
> > double bestDistance = Double.POSITIVE_INFINITY;
> > @@ -344,6 +333,8 @@ class GeoStandardPath extends GeoBasePath {
> > @Override
> > protected double distance(
> > final DistanceStyle distanceStyle, final double x, final double
> y, final double z) {
> > + // MHL - need another method in the abstraction!
> > +
> > // Algorithm:
> > // (1) If the point is within any of the segments along the path,
> return that value.
> > // (2) If the point is within any of the segment end circles along
> the path, return that value.
> > @@ -390,33 +381,10 @@ class GeoStandardPath extends GeoBasePath {
> > @Override
> > protected double deltaDistance(
> > final DistanceStyle distanceStyle, final double x, final double
> y, final double z) {
> > - // Algorithm:
> > - // (1) If the point is within any of the segments along the path,
> return that value.
> > - // (2) If the point is within any of the segment end circles along
> the path, return that value.
> > - // Finds best distance
> > - double bestDistance = Double.POSITIVE_INFINITY;
> > -
> > - for (final PathSegment segment : segments) {
> > - final double distance = segment.pathDeltaDistance(distanceStyle,
> x, y, z);
> > - if (distance != Double.POSITIVE_INFINITY) {
> > - final double thisDistance =
> distanceStyle.fromAggregationForm(distance);
> > - if (thisDistance < bestDistance) {
> > - bestDistance = thisDistance;
> > - }
> > - }
> > + if (rootComponent == null) {
> > + return Double.POSITIVE_INFINITY;
> > }
> > -
> > - for (final SegmentEndpoint endpoint : endPoints) {
> > - final double distance = endpoint.pathDeltaDistance(distanceStyle,
> x, y, z);
> > - if (distance != Double.POSITIVE_INFINITY) {
> > - final double thisDistance =
> distanceStyle.fromAggregationForm(distance);
> > - if (thisDistance < bestDistance) {
> > - bestDistance = thisDistance;
> > - }
> > - }
> > - }
> > -
> > - return bestDistance;
> > + return
> distanceStyle.fromAggregationForm(rootComponent.pathDeltaDistance(distanceStyle,
> x, y, z));
> > }
> >
> > @Override
> > @@ -429,35 +397,18 @@ class GeoStandardPath extends GeoBasePath {
> > @Override
> > protected double outsideDistance(
> > final DistanceStyle distanceStyle, final double x, final double
> y, final double z) {
> > - double minDistance = Double.POSITIVE_INFINITY;
> > - for (final SegmentEndpoint endpoint : endPoints) {
> > - final double newDistance =
> endpoint.outsideDistance(distanceStyle, x, y, z);
> > - if (newDistance < minDistance) {
> > - minDistance = newDistance;
> > - }
> > + if (rootComponent == null) {
> > + return Double.POSITIVE_INFINITY;
> > }
> > - for (final PathSegment segment : segments) {
> > - final double newDistance = segment.outsideDistance(distanceStyle,
> x, y, z);
> > - if (newDistance < minDistance) {
> > - minDistance = newDistance;
> > - }
> > - }
> > - return minDistance;
> > + return rootComponent.outsideDistance(distanceStyle, x, y, z);
> > }
> >
> > @Override
> > public boolean isWithin(final double x, final double y, final double
> z) {
> > - for (SegmentEndpoint pathPoint : endPoints) {
> > - if (pathPoint.isWithin(x, y, z)) {
> > - return true;
> > - }
> > - }
> > - for (PathSegment pathSegment : segments) {
> > - if (pathSegment.isWithin(x, y, z)) {
> > - return true;
> > - }
> > + if (rootComponent == null) {
> > + return false;
> > }
> > - return false;
> > + return rootComponent.isWithin(x, y, z);
> > }
> >
> > @Override
> > @@ -478,49 +429,25 @@ class GeoStandardPath extends GeoBasePath {
> > // Well, sort of. We can detect intersections also due to overlap
> of segments with each other.
> > // But that's an edge case and we won't be optimizing for it.
> > // System.err.println(" Looking for intersection of plane " + plane
> + " with path " + this);
> > - for (final SegmentEndpoint pathPoint : endPoints) {
> > - if (pathPoint.intersects(plane, notablePoints, bounds)) {
> > - return true;
> > - }
> > - }
> > -
> > - for (final PathSegment pathSegment : segments) {
> > - if (pathSegment.intersects(plane, notablePoints, bounds)) {
> > - return true;
> > - }
> > + if (rootComponent == null) {
> > + return false;
> > }
> > -
> > - return false;
> > + return rootComponent.intersects(plane, notablePoints, bounds);
> > }
> >
> > @Override
> > public boolean intersects(GeoShape geoShape) {
> > - for (final SegmentEndpoint pathPoint : endPoints) {
> > - if (pathPoint.intersects(geoShape)) {
> > - return true;
> > - }
> > - }
> > -
> > - for (final PathSegment pathSegment : segments) {
> > - if (pathSegment.intersects(geoShape)) {
> > - return true;
> > - }
> > + if (rootComponent == null) {
> > + return false;
> > }
> > -
> > - return false;
> > + return rootComponent.intersects(geoShape);
> > }
> >
> > @Override
> > public void getBounds(Bounds bounds) {
> > super.getBounds(bounds);
> > - // For building bounds, order matters. We want to traverse
> > - // never more than 180 degrees longitude at a pop or we risk having
> the
> > - // bounds object get itself inverted. So do the edges first.
> > - for (PathSegment pathSegment : segments) {
> > - pathSegment.getBounds(bounds);
> > - }
> > - for (SegmentEndpoint pathPoint : endPoints) {
> > - pathPoint.getBounds(bounds);
> > + if (rootComponent != null) {
> > + rootComponent.getBounds(bounds);
> > }
> > }
> >
> > @@ -700,6 +627,7 @@ class GeoStandardPath extends GeoBasePath {
> > bounds = new XYZBounds();
> > child1.getBounds(bounds);
> > child2.getBounds(bounds);
> > + //System.out.println("Constructed PathNode with child1="+child1+"
> and child2="+child2+" with computed bounds "+bounds);
> > }
> >
> > @Override
> > @@ -711,6 +639,8 @@ class GeoStandardPath extends GeoBasePath {
> > public boolean isWithin(final double x, final double y, final
> double z) {
> > // We computed the bounds for the node already, so use that as an
> "early-out".
> > // If we don't leave early, we need to check both children.
> > + // This code breaks things; not sure why yet. TBD
> > +
> > if (x < bounds.getMinimumX() || x > bounds.getMaximumX()) {
> > return false;
> > }
> > @@ -720,6 +650,7 @@ class GeoStandardPath extends GeoBasePath {
> > if (z < bounds.getMinimumZ() || z > bounds.getMaximumZ()) {
> > return false;
> > }
> > +
> > return child1.isWithin(x, y, z) || child2.isWithin(x, y, z);
> > }
> >
> > @@ -809,6 +740,11 @@ class GeoStandardPath extends GeoBasePath {
> > child2.getBounds(bounds);
> > }
> > }
> > +
> > + @Override
> > + public String toString() {
> > + return "PathNode ("+child1+") ("+child2+")";
> > + }
> > }
> >
> > /**
> > @@ -827,9 +763,7 @@ class GeoStandardPath extends GeoBasePath {
> > private interface SegmentEndpoint extends PathComponent {}
> >
> > /** Base implementation of SegmentEndpoint */
> > - private static class BaseSegmentEndpoint implements SegmentEndpoint {
> > - /** The planet model */
> > - protected final PlanetModel planetModel;
> > + private static class BaseSegmentEndpoint extends GeoBaseBounds
> implements SegmentEndpoint {
> > /** The previous path element */
> > protected final PathComponent previous;
> > /** The center point of the endpoint */
> > @@ -839,7 +773,7 @@ class GeoStandardPath extends GeoBasePath {
> >
> > public BaseSegmentEndpoint(
> > final PlanetModel planetModel, final PathComponent previous,
> final GeoPoint point) {
> > - this.planetModel = planetModel;
> > + super(planetModel);
> > this.previous = previous;
> > this.point = point;
> > }
> > @@ -918,6 +852,7 @@ class GeoStandardPath extends GeoBasePath {
> >
> > @Override
> > public void getBounds(final Bounds bounds) {
> > + super.getBounds(bounds);
> > bounds.addPoint(point);
> > }
> >
> > @@ -937,7 +872,7 @@ class GeoStandardPath extends GeoBasePath {
> >
> > @Override
> > public String toString() {
> > - return point.toString();
> > + return "SegmentEndpoint ("+point+")";
> > }
> > }
> >
> > @@ -1269,9 +1204,7 @@ class GeoStandardPath extends GeoBasePath {
> > }
> >
> > /** This is the pre-calculated data for a path segment. */
> > - private static class PathSegment implements PathComponent {
> > - /** Planet model */
> > - public final PlanetModel planetModel;
> > + private static class PathSegment extends GeoBaseBounds implements
> PathComponent {
> > /** Previous path component */
> > public final PathComponent previous;
> > /** Starting point of the segment */
> > @@ -1319,7 +1252,7 @@ class GeoStandardPath extends GeoBasePath {
> > final GeoPoint end,
> > final Plane normalizedConnectingPlane,
> > final double planeBoundingOffset) {
> > - this.planetModel = planetModel;
> > + super(planetModel);
> > this.previous = previous;
> > this.start = start;
> > this.end = end;
> > @@ -1724,6 +1657,7 @@ class GeoStandardPath extends GeoBasePath {
> >
> > @Override
> > public void getBounds(final Bounds bounds) {
> > + super.getBounds(bounds);
> > // We need to do all bounding planes as well as corner points
> > bounds
> > .addPoint(start)
> > @@ -1781,6 +1715,11 @@ class GeoStandardPath extends GeoBasePath {
> > startCutoffPlane,
> > lowerConnectingPlane);
> > }
> > +
> > + @Override
> > + public String toString() {
> > + return "PathSegment ("+ULHC+", "+URHC+", "+LRHC+", "+LLHC+")";
> > + }
> > }
> >
> > private static class TreeBuilder {
> > @@ -1816,9 +1755,9 @@ class GeoStandardPath extends GeoBasePath {
> >
> > private void mergeTop() {
> > depthStack.remove(depthStack.size() - 1);
> > - PathComponent firstComponent =
> componentStack.remove(componentStack.size() - 1);
> > - int newDepth = depthStack.remove(depthStack.size() - 1);
> > PathComponent secondComponent =
> componentStack.remove(componentStack.size() - 1);
> > + int newDepth = depthStack.remove(depthStack.size() - 1) + 1;
> > + PathComponent firstComponent =
> componentStack.remove(componentStack.size() - 1);
> > depthStack.add(newDepth);
> > componentStack.add(new PathNode(firstComponent, secondComponent));
> > }
> >
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail: dev-help@lucene.apache.org
>
>
Re: [lucene] 02/03: Fix longstanding bug in path bounds calculation, and hook up efficient isWithin() and distance logic
Posted by Robert Muir <rc...@gmail.com>.
Multiple spatial tests are failing in jenkins... bisected them to this commit.
Can you please look into it? https://github.com/apache/lucene/issues/11956
On Sat, Nov 19, 2022 at 8:22 PM <kw...@apache.org> wrote:
>
> This is an automated email from the ASF dual-hosted git repository.
>
> kwright pushed a commit to branch main
> in repository https://gitbox.apache.org/repos/asf/lucene.git
>
> commit 9bca7a70e10db81b39a5afb4498aab1006402031
> Author: Karl David Wright <kw...@apache.org>
> AuthorDate: Sat Nov 19 17:35:30 2022 -0500
>
> Fix longstanding bug in path bounds calculation, and hook up efficient isWithin() and distance logic
> ---
> .../geom/{GeoBaseShape.java => GeoBaseBounds.java} | 6 +-
> .../apache/lucene/spatial3d/geom/GeoBaseShape.java | 24 +-
> .../apache/lucene/spatial3d/geom/GeoBounds.java | 27 ++
> .../org/apache/lucene/spatial3d/geom/GeoShape.java | 2 +-
> .../lucene/spatial3d/geom/GeoStandardPath.java | 277 ++++++++-------------
> 5 files changed, 140 insertions(+), 196 deletions(-)
>
> diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseBounds.java
> similarity index 90%
> copy from lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
> copy to lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseBounds.java
> index a5992392563..52030b333d3 100644
> --- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
> +++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseBounds.java
> @@ -17,18 +17,18 @@
> package org.apache.lucene.spatial3d.geom;
>
> /**
> - * Base extended shape object.
> + * Base object that supports bounds operations.
> *
> * @lucene.internal
> */
> -public abstract class GeoBaseShape extends BasePlanetObject implements GeoShape {
> +public abstract class GeoBaseBounds extends BasePlanetObject implements GeoBounds {
>
> /**
> * Constructor.
> *
> * @param planetModel is the planet model to use.
> */
> - public GeoBaseShape(final PlanetModel planetModel) {
> + public GeoBaseBounds(final PlanetModel planetModel) {
> super(planetModel);
> }
>
> diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
> index a5992392563..a4b5cd18a62 100644
> --- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
> +++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
> @@ -21,7 +21,7 @@ package org.apache.lucene.spatial3d.geom;
> *
> * @lucene.internal
> */
> -public abstract class GeoBaseShape extends BasePlanetObject implements GeoShape {
> +public abstract class GeoBaseShape extends GeoBaseBounds implements GeoShape {
>
> /**
> * Constructor.
> @@ -31,26 +31,4 @@ public abstract class GeoBaseShape extends BasePlanetObject implements GeoShape
> public GeoBaseShape(final PlanetModel planetModel) {
> super(planetModel);
> }
> -
> - @Override
> - public void getBounds(Bounds bounds) {
> - if (isWithin(planetModel.NORTH_POLE)) {
> - bounds.noTopLatitudeBound().noLongitudeBound().addPoint(planetModel.NORTH_POLE);
> - }
> - if (isWithin(planetModel.SOUTH_POLE)) {
> - bounds.noBottomLatitudeBound().noLongitudeBound().addPoint(planetModel.SOUTH_POLE);
> - }
> - if (isWithin(planetModel.MIN_X_POLE)) {
> - bounds.addPoint(planetModel.MIN_X_POLE);
> - }
> - if (isWithin(planetModel.MAX_X_POLE)) {
> - bounds.addPoint(planetModel.MAX_X_POLE);
> - }
> - if (isWithin(planetModel.MIN_Y_POLE)) {
> - bounds.addPoint(planetModel.MIN_Y_POLE);
> - }
> - if (isWithin(planetModel.MAX_Y_POLE)) {
> - bounds.addPoint(planetModel.MAX_Y_POLE);
> - }
> - }
> }
> diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBounds.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBounds.java
> new file mode 100644
> index 00000000000..935366c5a08
> --- /dev/null
> +++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBounds.java
> @@ -0,0 +1,27 @@
> +/*
> + * Licensed to the Apache Software Foundation (ASF) under one or more
> + * contributor license agreements. See the NOTICE file distributed with
> + * this work for additional information regarding copyright ownership.
> + * The ASF licenses this file to You under the Apache License, Version 2.0
> + * (the "License"); you may not use this file except in compliance with
> + * the License. You may obtain a copy of the License at
> + *
> + * http://www.apache.org/licenses/LICENSE-2.0
> + *
> + * Unless required by applicable law or agreed to in writing, software
> + * distributed under the License is distributed on an "AS IS" BASIS,
> + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
> + * See the License for the specific language governing permissions and
> + * limitations under the License.
> + */
> +package org.apache.lucene.spatial3d.geom;
> +
> +/**
> + * Generic shape that supports bounds. This describes methods that help
> + * shapes compute their bounds.
> + *
> + * @lucene.experimental
> + */
> +public interface GeoBounds extends Bounded, Membership, PlanetObject {
> +
> +}
> diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoShape.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoShape.java
> index 8262ecf5a9e..4e32b9e03e8 100755
> --- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoShape.java
> +++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoShape.java
> @@ -22,7 +22,7 @@ package org.apache.lucene.spatial3d.geom;
> *
> * @lucene.experimental
> */
> -public interface GeoShape extends Bounded, Membership, PlanetObject {
> +public interface GeoShape extends GeoBounds {
>
> /**
> * Return a sample point that is on the outside edge/boundary of the shape.
> diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoStandardPath.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoStandardPath.java
> index 1f997100e1a..16a07009b64 100755
> --- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoStandardPath.java
> +++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoStandardPath.java
> @@ -188,82 +188,83 @@ class GeoStandardPath extends GeoBasePath {
> new GeoPoint[] {
> onlyEndpoint.circlePlane.getSampleIntersectionPoint(planetModel, normalPlane)
> };
> - return;
> - }
> -
> - // Create segment endpoints. Use an appropriate constructor for the start and end of the path.
> - for (int i = 0; i < segments.size(); i++) {
> - final PathSegment currentSegment = segments.get(i);
> -
> - if (i == 0) {
> - // Starting endpoint
> - final SegmentEndpoint startEndpoint =
> + } else {
> + // Create segment endpoints. Use an appropriate constructor for the start and end of the path.
> + for (int i = 0; i < segments.size(); i++) {
> + final PathSegment currentSegment = segments.get(i);
> +
> + if (i == 0) {
> + // Starting endpoint
> + final SegmentEndpoint startEndpoint =
> new CutoffSingleCircleSegmentEndpoint(
> - planetModel,
> - null,
> - currentSegment.start,
> - currentSegment.startCutoffPlane,
> - currentSegment.ULHC,
> - currentSegment.LLHC);
> - endPoints.add(startEndpoint);
> - this.edgePoints = new GeoPoint[] {currentSegment.ULHC};
> - continue;
> - }
> + planetModel,
> + null,
> + currentSegment.start,
> + currentSegment.startCutoffPlane,
> + currentSegment.ULHC,
> + currentSegment.LLHC);
> + endPoints.add(startEndpoint);
> + this.edgePoints = new GeoPoint[] {currentSegment.ULHC};
> + continue;
> + }
>
> - // General intersection case
> - final PathSegment prevSegment = segments.get(i - 1);
> - if (prevSegment.endCutoffPlane.isWithin(currentSegment.ULHC)
> - && prevSegment.endCutoffPlane.isWithin(currentSegment.LLHC)
> - && currentSegment.startCutoffPlane.isWithin(prevSegment.URHC)
> - && currentSegment.startCutoffPlane.isWithin(prevSegment.LRHC)) {
> - // The planes are identical. We wouldn't need a circle at all except for the possibility of
> - // backing up, which is hard to detect here.
> - final SegmentEndpoint midEndpoint =
> + // General intersection case
> + final PathSegment prevSegment = segments.get(i - 1);
> + if (prevSegment.endCutoffPlane.isWithin(currentSegment.ULHC)
> + && prevSegment.endCutoffPlane.isWithin(currentSegment.LLHC)
> + && currentSegment.startCutoffPlane.isWithin(prevSegment.URHC)
> + && currentSegment.startCutoffPlane.isWithin(prevSegment.LRHC)) {
> + // The planes are identical. We wouldn't need a circle at all except for the possibility of
> + // backing up, which is hard to detect here.
> + final SegmentEndpoint midEndpoint =
> new CutoffSingleCircleSegmentEndpoint(
> - planetModel,
> - prevSegment,
> - currentSegment.start,
> - prevSegment.endCutoffPlane,
> - currentSegment.startCutoffPlane,
> - currentSegment.ULHC,
> - currentSegment.LLHC);
> - // don't need a circle at all. Special constructor...
> - endPoints.add(midEndpoint);
> - } else {
> - endPoints.add(
> - new CutoffDualCircleSegmentEndpoint(
> - planetModel,
> - prevSegment,
> - currentSegment.start,
> - prevSegment.endCutoffPlane,
> - currentSegment.startCutoffPlane,
> - prevSegment.URHC,
> - prevSegment.LRHC,
> - currentSegment.ULHC,
> - currentSegment.LLHC));
> + planetModel,
> + prevSegment,
> + currentSegment.start,
> + prevSegment.endCutoffPlane,
> + currentSegment.startCutoffPlane,
> + currentSegment.ULHC,
> + currentSegment.LLHC);
> + // don't need a circle at all. Special constructor...
> + endPoints.add(midEndpoint);
> + } else {
> + endPoints.add(
> + new CutoffDualCircleSegmentEndpoint(
> + planetModel,
> + prevSegment,
> + currentSegment.start,
> + prevSegment.endCutoffPlane,
> + currentSegment.startCutoffPlane,
> + prevSegment.URHC,
> + prevSegment.LRHC,
> + currentSegment.ULHC,
> + currentSegment.LLHC));
> + }
> }
> + // Do final endpoint
> + final PathSegment lastSegment = segments.get(segments.size() - 1);
> + endPoints.add(
> + new CutoffSingleCircleSegmentEndpoint(
> + planetModel,
> + lastSegment,
> + lastSegment.end,
> + lastSegment.endCutoffPlane,
> + lastSegment.URHC,
> + lastSegment.LRHC));
> }
> - // Do final endpoint
> - final PathSegment lastSegment = segments.get(segments.size() - 1);
> - endPoints.add(
> - new CutoffSingleCircleSegmentEndpoint(
> - planetModel,
> - lastSegment,
> - lastSegment.end,
> - lastSegment.endCutoffPlane,
> - lastSegment.URHC,
> - lastSegment.LRHC));
>
> final TreeBuilder treeBuilder = new TreeBuilder(segments.size() + endPoints.size());
> // Segments will have one less than the number of endpoints.
> // So, we add the first endpoint, and then do it pairwise.
> - treeBuilder.addComponent(segments.get(0));
> + treeBuilder.addComponent(endPoints.get(0));
> for (int i = 0; i < segments.size(); i++) {
> treeBuilder.addComponent(segments.get(i));
> treeBuilder.addComponent(endPoints.get(i + 1));
> }
>
> rootComponent = treeBuilder.getRoot();
> +
> + //System.out.println("Root component: "+rootComponent);
> }
>
> /**
> @@ -289,28 +290,16 @@ class GeoStandardPath extends GeoBasePath {
> @Override
> public double computePathCenterDistance(
> final DistanceStyle distanceStyle, final double x, final double y, final double z) {
> - // Walk along path and keep track of the closest distance we find
> - double closestDistance = Double.POSITIVE_INFINITY;
> - // Segments first
> - for (PathSegment segment : segments) {
> - final double segmentDistance = segment.pathCenterDistance(distanceStyle, x, y, z);
> - if (segmentDistance < closestDistance) {
> - closestDistance = segmentDistance;
> - }
> + if (rootComponent == null) {
> + return Double.POSITIVE_INFINITY;
> }
> - // Now, endpoints
> - for (SegmentEndpoint endpoint : endPoints) {
> - final double endpointDistance = endpoint.pathCenterDistance(distanceStyle, x, y, z);
> - if (endpointDistance < closestDistance) {
> - closestDistance = endpointDistance;
> - }
> - }
> - return closestDistance;
> + return rootComponent.pathCenterDistance(distanceStyle, x, y, z);
> }
>
> @Override
> public double computeNearestDistance(
> final DistanceStyle distanceStyle, final double x, final double y, final double z) {
> + // MHL - need another abstraction method for this
> double currentDistance = 0.0;
> double minPathCenterDistance = Double.POSITIVE_INFINITY;
> double bestDistance = Double.POSITIVE_INFINITY;
> @@ -344,6 +333,8 @@ class GeoStandardPath extends GeoBasePath {
> @Override
> protected double distance(
> final DistanceStyle distanceStyle, final double x, final double y, final double z) {
> + // MHL - need another method in the abstraction!
> +
> // Algorithm:
> // (1) If the point is within any of the segments along the path, return that value.
> // (2) If the point is within any of the segment end circles along the path, return that value.
> @@ -390,33 +381,10 @@ class GeoStandardPath extends GeoBasePath {
> @Override
> protected double deltaDistance(
> final DistanceStyle distanceStyle, final double x, final double y, final double z) {
> - // Algorithm:
> - // (1) If the point is within any of the segments along the path, return that value.
> - // (2) If the point is within any of the segment end circles along the path, return that value.
> - // Finds best distance
> - double bestDistance = Double.POSITIVE_INFINITY;
> -
> - for (final PathSegment segment : segments) {
> - final double distance = segment.pathDeltaDistance(distanceStyle, x, y, z);
> - if (distance != Double.POSITIVE_INFINITY) {
> - final double thisDistance = distanceStyle.fromAggregationForm(distance);
> - if (thisDistance < bestDistance) {
> - bestDistance = thisDistance;
> - }
> - }
> + if (rootComponent == null) {
> + return Double.POSITIVE_INFINITY;
> }
> -
> - for (final SegmentEndpoint endpoint : endPoints) {
> - final double distance = endpoint.pathDeltaDistance(distanceStyle, x, y, z);
> - if (distance != Double.POSITIVE_INFINITY) {
> - final double thisDistance = distanceStyle.fromAggregationForm(distance);
> - if (thisDistance < bestDistance) {
> - bestDistance = thisDistance;
> - }
> - }
> - }
> -
> - return bestDistance;
> + return distanceStyle.fromAggregationForm(rootComponent.pathDeltaDistance(distanceStyle, x, y, z));
> }
>
> @Override
> @@ -429,35 +397,18 @@ class GeoStandardPath extends GeoBasePath {
> @Override
> protected double outsideDistance(
> final DistanceStyle distanceStyle, final double x, final double y, final double z) {
> - double minDistance = Double.POSITIVE_INFINITY;
> - for (final SegmentEndpoint endpoint : endPoints) {
> - final double newDistance = endpoint.outsideDistance(distanceStyle, x, y, z);
> - if (newDistance < minDistance) {
> - minDistance = newDistance;
> - }
> + if (rootComponent == null) {
> + return Double.POSITIVE_INFINITY;
> }
> - for (final PathSegment segment : segments) {
> - final double newDistance = segment.outsideDistance(distanceStyle, x, y, z);
> - if (newDistance < minDistance) {
> - minDistance = newDistance;
> - }
> - }
> - return minDistance;
> + return rootComponent.outsideDistance(distanceStyle, x, y, z);
> }
>
> @Override
> public boolean isWithin(final double x, final double y, final double z) {
> - for (SegmentEndpoint pathPoint : endPoints) {
> - if (pathPoint.isWithin(x, y, z)) {
> - return true;
> - }
> - }
> - for (PathSegment pathSegment : segments) {
> - if (pathSegment.isWithin(x, y, z)) {
> - return true;
> - }
> + if (rootComponent == null) {
> + return false;
> }
> - return false;
> + return rootComponent.isWithin(x, y, z);
> }
>
> @Override
> @@ -478,49 +429,25 @@ class GeoStandardPath extends GeoBasePath {
> // Well, sort of. We can detect intersections also due to overlap of segments with each other.
> // But that's an edge case and we won't be optimizing for it.
> // System.err.println(" Looking for intersection of plane " + plane + " with path " + this);
> - for (final SegmentEndpoint pathPoint : endPoints) {
> - if (pathPoint.intersects(plane, notablePoints, bounds)) {
> - return true;
> - }
> - }
> -
> - for (final PathSegment pathSegment : segments) {
> - if (pathSegment.intersects(plane, notablePoints, bounds)) {
> - return true;
> - }
> + if (rootComponent == null) {
> + return false;
> }
> -
> - return false;
> + return rootComponent.intersects(plane, notablePoints, bounds);
> }
>
> @Override
> public boolean intersects(GeoShape geoShape) {
> - for (final SegmentEndpoint pathPoint : endPoints) {
> - if (pathPoint.intersects(geoShape)) {
> - return true;
> - }
> - }
> -
> - for (final PathSegment pathSegment : segments) {
> - if (pathSegment.intersects(geoShape)) {
> - return true;
> - }
> + if (rootComponent == null) {
> + return false;
> }
> -
> - return false;
> + return rootComponent.intersects(geoShape);
> }
>
> @Override
> public void getBounds(Bounds bounds) {
> super.getBounds(bounds);
> - // For building bounds, order matters. We want to traverse
> - // never more than 180 degrees longitude at a pop or we risk having the
> - // bounds object get itself inverted. So do the edges first.
> - for (PathSegment pathSegment : segments) {
> - pathSegment.getBounds(bounds);
> - }
> - for (SegmentEndpoint pathPoint : endPoints) {
> - pathPoint.getBounds(bounds);
> + if (rootComponent != null) {
> + rootComponent.getBounds(bounds);
> }
> }
>
> @@ -700,6 +627,7 @@ class GeoStandardPath extends GeoBasePath {
> bounds = new XYZBounds();
> child1.getBounds(bounds);
> child2.getBounds(bounds);
> + //System.out.println("Constructed PathNode with child1="+child1+" and child2="+child2+" with computed bounds "+bounds);
> }
>
> @Override
> @@ -711,6 +639,8 @@ class GeoStandardPath extends GeoBasePath {
> public boolean isWithin(final double x, final double y, final double z) {
> // We computed the bounds for the node already, so use that as an "early-out".
> // If we don't leave early, we need to check both children.
> + // This code breaks things; not sure why yet. TBD
> +
> if (x < bounds.getMinimumX() || x > bounds.getMaximumX()) {
> return false;
> }
> @@ -720,6 +650,7 @@ class GeoStandardPath extends GeoBasePath {
> if (z < bounds.getMinimumZ() || z > bounds.getMaximumZ()) {
> return false;
> }
> +
> return child1.isWithin(x, y, z) || child2.isWithin(x, y, z);
> }
>
> @@ -809,6 +740,11 @@ class GeoStandardPath extends GeoBasePath {
> child2.getBounds(bounds);
> }
> }
> +
> + @Override
> + public String toString() {
> + return "PathNode ("+child1+") ("+child2+")";
> + }
> }
>
> /**
> @@ -827,9 +763,7 @@ class GeoStandardPath extends GeoBasePath {
> private interface SegmentEndpoint extends PathComponent {}
>
> /** Base implementation of SegmentEndpoint */
> - private static class BaseSegmentEndpoint implements SegmentEndpoint {
> - /** The planet model */
> - protected final PlanetModel planetModel;
> + private static class BaseSegmentEndpoint extends GeoBaseBounds implements SegmentEndpoint {
> /** The previous path element */
> protected final PathComponent previous;
> /** The center point of the endpoint */
> @@ -839,7 +773,7 @@ class GeoStandardPath extends GeoBasePath {
>
> public BaseSegmentEndpoint(
> final PlanetModel planetModel, final PathComponent previous, final GeoPoint point) {
> - this.planetModel = planetModel;
> + super(planetModel);
> this.previous = previous;
> this.point = point;
> }
> @@ -918,6 +852,7 @@ class GeoStandardPath extends GeoBasePath {
>
> @Override
> public void getBounds(final Bounds bounds) {
> + super.getBounds(bounds);
> bounds.addPoint(point);
> }
>
> @@ -937,7 +872,7 @@ class GeoStandardPath extends GeoBasePath {
>
> @Override
> public String toString() {
> - return point.toString();
> + return "SegmentEndpoint ("+point+")";
> }
> }
>
> @@ -1269,9 +1204,7 @@ class GeoStandardPath extends GeoBasePath {
> }
>
> /** This is the pre-calculated data for a path segment. */
> - private static class PathSegment implements PathComponent {
> - /** Planet model */
> - public final PlanetModel planetModel;
> + private static class PathSegment extends GeoBaseBounds implements PathComponent {
> /** Previous path component */
> public final PathComponent previous;
> /** Starting point of the segment */
> @@ -1319,7 +1252,7 @@ class GeoStandardPath extends GeoBasePath {
> final GeoPoint end,
> final Plane normalizedConnectingPlane,
> final double planeBoundingOffset) {
> - this.planetModel = planetModel;
> + super(planetModel);
> this.previous = previous;
> this.start = start;
> this.end = end;
> @@ -1724,6 +1657,7 @@ class GeoStandardPath extends GeoBasePath {
>
> @Override
> public void getBounds(final Bounds bounds) {
> + super.getBounds(bounds);
> // We need to do all bounding planes as well as corner points
> bounds
> .addPoint(start)
> @@ -1781,6 +1715,11 @@ class GeoStandardPath extends GeoBasePath {
> startCutoffPlane,
> lowerConnectingPlane);
> }
> +
> + @Override
> + public String toString() {
> + return "PathSegment ("+ULHC+", "+URHC+", "+LRHC+", "+LLHC+")";
> + }
> }
>
> private static class TreeBuilder {
> @@ -1816,9 +1755,9 @@ class GeoStandardPath extends GeoBasePath {
>
> private void mergeTop() {
> depthStack.remove(depthStack.size() - 1);
> - PathComponent firstComponent = componentStack.remove(componentStack.size() - 1);
> - int newDepth = depthStack.remove(depthStack.size() - 1);
> PathComponent secondComponent = componentStack.remove(componentStack.size() - 1);
> + int newDepth = depthStack.remove(depthStack.size() - 1) + 1;
> + PathComponent firstComponent = componentStack.remove(componentStack.size() - 1);
> depthStack.add(newDepth);
> componentStack.add(new PathNode(firstComponent, secondComponent));
> }
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[lucene] 02/03: Fix longstanding bug in path bounds calculation, and hook up efficient isWithin() and distance logic
Posted by kw...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
kwright pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git
commit 9bca7a70e10db81b39a5afb4498aab1006402031
Author: Karl David Wright <kw...@apache.org>
AuthorDate: Sat Nov 19 17:35:30 2022 -0500
Fix longstanding bug in path bounds calculation, and hook up efficient isWithin() and distance logic
---
.../geom/{GeoBaseShape.java => GeoBaseBounds.java} | 6 +-
.../apache/lucene/spatial3d/geom/GeoBaseShape.java | 24 +-
.../apache/lucene/spatial3d/geom/GeoBounds.java | 27 ++
.../org/apache/lucene/spatial3d/geom/GeoShape.java | 2 +-
.../lucene/spatial3d/geom/GeoStandardPath.java | 277 ++++++++-------------
5 files changed, 140 insertions(+), 196 deletions(-)
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseBounds.java
similarity index 90%
copy from lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
copy to lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseBounds.java
index a5992392563..52030b333d3 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseBounds.java
@@ -17,18 +17,18 @@
package org.apache.lucene.spatial3d.geom;
/**
- * Base extended shape object.
+ * Base object that supports bounds operations.
*
* @lucene.internal
*/
-public abstract class GeoBaseShape extends BasePlanetObject implements GeoShape {
+public abstract class GeoBaseBounds extends BasePlanetObject implements GeoBounds {
/**
* Constructor.
*
* @param planetModel is the planet model to use.
*/
- public GeoBaseShape(final PlanetModel planetModel) {
+ public GeoBaseBounds(final PlanetModel planetModel) {
super(planetModel);
}
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
index a5992392563..a4b5cd18a62 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBaseShape.java
@@ -21,7 +21,7 @@ package org.apache.lucene.spatial3d.geom;
*
* @lucene.internal
*/
-public abstract class GeoBaseShape extends BasePlanetObject implements GeoShape {
+public abstract class GeoBaseShape extends GeoBaseBounds implements GeoShape {
/**
* Constructor.
@@ -31,26 +31,4 @@ public abstract class GeoBaseShape extends BasePlanetObject implements GeoShape
public GeoBaseShape(final PlanetModel planetModel) {
super(planetModel);
}
-
- @Override
- public void getBounds(Bounds bounds) {
- if (isWithin(planetModel.NORTH_POLE)) {
- bounds.noTopLatitudeBound().noLongitudeBound().addPoint(planetModel.NORTH_POLE);
- }
- if (isWithin(planetModel.SOUTH_POLE)) {
- bounds.noBottomLatitudeBound().noLongitudeBound().addPoint(planetModel.SOUTH_POLE);
- }
- if (isWithin(planetModel.MIN_X_POLE)) {
- bounds.addPoint(planetModel.MIN_X_POLE);
- }
- if (isWithin(planetModel.MAX_X_POLE)) {
- bounds.addPoint(planetModel.MAX_X_POLE);
- }
- if (isWithin(planetModel.MIN_Y_POLE)) {
- bounds.addPoint(planetModel.MIN_Y_POLE);
- }
- if (isWithin(planetModel.MAX_Y_POLE)) {
- bounds.addPoint(planetModel.MAX_Y_POLE);
- }
- }
}
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBounds.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBounds.java
new file mode 100644
index 00000000000..935366c5a08
--- /dev/null
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBounds.java
@@ -0,0 +1,27 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.spatial3d.geom;
+
+/**
+ * Generic shape that supports bounds. This describes methods that help
+ * shapes compute their bounds.
+ *
+ * @lucene.experimental
+ */
+public interface GeoBounds extends Bounded, Membership, PlanetObject {
+
+}
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoShape.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoShape.java
index 8262ecf5a9e..4e32b9e03e8 100755
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoShape.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoShape.java
@@ -22,7 +22,7 @@ package org.apache.lucene.spatial3d.geom;
*
* @lucene.experimental
*/
-public interface GeoShape extends Bounded, Membership, PlanetObject {
+public interface GeoShape extends GeoBounds {
/**
* Return a sample point that is on the outside edge/boundary of the shape.
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoStandardPath.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoStandardPath.java
index 1f997100e1a..16a07009b64 100755
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoStandardPath.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoStandardPath.java
@@ -188,82 +188,83 @@ class GeoStandardPath extends GeoBasePath {
new GeoPoint[] {
onlyEndpoint.circlePlane.getSampleIntersectionPoint(planetModel, normalPlane)
};
- return;
- }
-
- // Create segment endpoints. Use an appropriate constructor for the start and end of the path.
- for (int i = 0; i < segments.size(); i++) {
- final PathSegment currentSegment = segments.get(i);
-
- if (i == 0) {
- // Starting endpoint
- final SegmentEndpoint startEndpoint =
+ } else {
+ // Create segment endpoints. Use an appropriate constructor for the start and end of the path.
+ for (int i = 0; i < segments.size(); i++) {
+ final PathSegment currentSegment = segments.get(i);
+
+ if (i == 0) {
+ // Starting endpoint
+ final SegmentEndpoint startEndpoint =
new CutoffSingleCircleSegmentEndpoint(
- planetModel,
- null,
- currentSegment.start,
- currentSegment.startCutoffPlane,
- currentSegment.ULHC,
- currentSegment.LLHC);
- endPoints.add(startEndpoint);
- this.edgePoints = new GeoPoint[] {currentSegment.ULHC};
- continue;
- }
+ planetModel,
+ null,
+ currentSegment.start,
+ currentSegment.startCutoffPlane,
+ currentSegment.ULHC,
+ currentSegment.LLHC);
+ endPoints.add(startEndpoint);
+ this.edgePoints = new GeoPoint[] {currentSegment.ULHC};
+ continue;
+ }
- // General intersection case
- final PathSegment prevSegment = segments.get(i - 1);
- if (prevSegment.endCutoffPlane.isWithin(currentSegment.ULHC)
- && prevSegment.endCutoffPlane.isWithin(currentSegment.LLHC)
- && currentSegment.startCutoffPlane.isWithin(prevSegment.URHC)
- && currentSegment.startCutoffPlane.isWithin(prevSegment.LRHC)) {
- // The planes are identical. We wouldn't need a circle at all except for the possibility of
- // backing up, which is hard to detect here.
- final SegmentEndpoint midEndpoint =
+ // General intersection case
+ final PathSegment prevSegment = segments.get(i - 1);
+ if (prevSegment.endCutoffPlane.isWithin(currentSegment.ULHC)
+ && prevSegment.endCutoffPlane.isWithin(currentSegment.LLHC)
+ && currentSegment.startCutoffPlane.isWithin(prevSegment.URHC)
+ && currentSegment.startCutoffPlane.isWithin(prevSegment.LRHC)) {
+ // The planes are identical. We wouldn't need a circle at all except for the possibility of
+ // backing up, which is hard to detect here.
+ final SegmentEndpoint midEndpoint =
new CutoffSingleCircleSegmentEndpoint(
- planetModel,
- prevSegment,
- currentSegment.start,
- prevSegment.endCutoffPlane,
- currentSegment.startCutoffPlane,
- currentSegment.ULHC,
- currentSegment.LLHC);
- // don't need a circle at all. Special constructor...
- endPoints.add(midEndpoint);
- } else {
- endPoints.add(
- new CutoffDualCircleSegmentEndpoint(
- planetModel,
- prevSegment,
- currentSegment.start,
- prevSegment.endCutoffPlane,
- currentSegment.startCutoffPlane,
- prevSegment.URHC,
- prevSegment.LRHC,
- currentSegment.ULHC,
- currentSegment.LLHC));
+ planetModel,
+ prevSegment,
+ currentSegment.start,
+ prevSegment.endCutoffPlane,
+ currentSegment.startCutoffPlane,
+ currentSegment.ULHC,
+ currentSegment.LLHC);
+ // don't need a circle at all. Special constructor...
+ endPoints.add(midEndpoint);
+ } else {
+ endPoints.add(
+ new CutoffDualCircleSegmentEndpoint(
+ planetModel,
+ prevSegment,
+ currentSegment.start,
+ prevSegment.endCutoffPlane,
+ currentSegment.startCutoffPlane,
+ prevSegment.URHC,
+ prevSegment.LRHC,
+ currentSegment.ULHC,
+ currentSegment.LLHC));
+ }
}
+ // Do final endpoint
+ final PathSegment lastSegment = segments.get(segments.size() - 1);
+ endPoints.add(
+ new CutoffSingleCircleSegmentEndpoint(
+ planetModel,
+ lastSegment,
+ lastSegment.end,
+ lastSegment.endCutoffPlane,
+ lastSegment.URHC,
+ lastSegment.LRHC));
}
- // Do final endpoint
- final PathSegment lastSegment = segments.get(segments.size() - 1);
- endPoints.add(
- new CutoffSingleCircleSegmentEndpoint(
- planetModel,
- lastSegment,
- lastSegment.end,
- lastSegment.endCutoffPlane,
- lastSegment.URHC,
- lastSegment.LRHC));
final TreeBuilder treeBuilder = new TreeBuilder(segments.size() + endPoints.size());
// Segments will have one less than the number of endpoints.
// So, we add the first endpoint, and then do it pairwise.
- treeBuilder.addComponent(segments.get(0));
+ treeBuilder.addComponent(endPoints.get(0));
for (int i = 0; i < segments.size(); i++) {
treeBuilder.addComponent(segments.get(i));
treeBuilder.addComponent(endPoints.get(i + 1));
}
rootComponent = treeBuilder.getRoot();
+
+ //System.out.println("Root component: "+rootComponent);
}
/**
@@ -289,28 +290,16 @@ class GeoStandardPath extends GeoBasePath {
@Override
public double computePathCenterDistance(
final DistanceStyle distanceStyle, final double x, final double y, final double z) {
- // Walk along path and keep track of the closest distance we find
- double closestDistance = Double.POSITIVE_INFINITY;
- // Segments first
- for (PathSegment segment : segments) {
- final double segmentDistance = segment.pathCenterDistance(distanceStyle, x, y, z);
- if (segmentDistance < closestDistance) {
- closestDistance = segmentDistance;
- }
+ if (rootComponent == null) {
+ return Double.POSITIVE_INFINITY;
}
- // Now, endpoints
- for (SegmentEndpoint endpoint : endPoints) {
- final double endpointDistance = endpoint.pathCenterDistance(distanceStyle, x, y, z);
- if (endpointDistance < closestDistance) {
- closestDistance = endpointDistance;
- }
- }
- return closestDistance;
+ return rootComponent.pathCenterDistance(distanceStyle, x, y, z);
}
@Override
public double computeNearestDistance(
final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ // MHL - need another abstraction method for this
double currentDistance = 0.0;
double minPathCenterDistance = Double.POSITIVE_INFINITY;
double bestDistance = Double.POSITIVE_INFINITY;
@@ -344,6 +333,8 @@ class GeoStandardPath extends GeoBasePath {
@Override
protected double distance(
final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ // MHL - need another method in the abstraction!
+
// Algorithm:
// (1) If the point is within any of the segments along the path, return that value.
// (2) If the point is within any of the segment end circles along the path, return that value.
@@ -390,33 +381,10 @@ class GeoStandardPath extends GeoBasePath {
@Override
protected double deltaDistance(
final DistanceStyle distanceStyle, final double x, final double y, final double z) {
- // Algorithm:
- // (1) If the point is within any of the segments along the path, return that value.
- // (2) If the point is within any of the segment end circles along the path, return that value.
- // Finds best distance
- double bestDistance = Double.POSITIVE_INFINITY;
-
- for (final PathSegment segment : segments) {
- final double distance = segment.pathDeltaDistance(distanceStyle, x, y, z);
- if (distance != Double.POSITIVE_INFINITY) {
- final double thisDistance = distanceStyle.fromAggregationForm(distance);
- if (thisDistance < bestDistance) {
- bestDistance = thisDistance;
- }
- }
+ if (rootComponent == null) {
+ return Double.POSITIVE_INFINITY;
}
-
- for (final SegmentEndpoint endpoint : endPoints) {
- final double distance = endpoint.pathDeltaDistance(distanceStyle, x, y, z);
- if (distance != Double.POSITIVE_INFINITY) {
- final double thisDistance = distanceStyle.fromAggregationForm(distance);
- if (thisDistance < bestDistance) {
- bestDistance = thisDistance;
- }
- }
- }
-
- return bestDistance;
+ return distanceStyle.fromAggregationForm(rootComponent.pathDeltaDistance(distanceStyle, x, y, z));
}
@Override
@@ -429,35 +397,18 @@ class GeoStandardPath extends GeoBasePath {
@Override
protected double outsideDistance(
final DistanceStyle distanceStyle, final double x, final double y, final double z) {
- double minDistance = Double.POSITIVE_INFINITY;
- for (final SegmentEndpoint endpoint : endPoints) {
- final double newDistance = endpoint.outsideDistance(distanceStyle, x, y, z);
- if (newDistance < minDistance) {
- minDistance = newDistance;
- }
+ if (rootComponent == null) {
+ return Double.POSITIVE_INFINITY;
}
- for (final PathSegment segment : segments) {
- final double newDistance = segment.outsideDistance(distanceStyle, x, y, z);
- if (newDistance < minDistance) {
- minDistance = newDistance;
- }
- }
- return minDistance;
+ return rootComponent.outsideDistance(distanceStyle, x, y, z);
}
@Override
public boolean isWithin(final double x, final double y, final double z) {
- for (SegmentEndpoint pathPoint : endPoints) {
- if (pathPoint.isWithin(x, y, z)) {
- return true;
- }
- }
- for (PathSegment pathSegment : segments) {
- if (pathSegment.isWithin(x, y, z)) {
- return true;
- }
+ if (rootComponent == null) {
+ return false;
}
- return false;
+ return rootComponent.isWithin(x, y, z);
}
@Override
@@ -478,49 +429,25 @@ class GeoStandardPath extends GeoBasePath {
// Well, sort of. We can detect intersections also due to overlap of segments with each other.
// But that's an edge case and we won't be optimizing for it.
// System.err.println(" Looking for intersection of plane " + plane + " with path " + this);
- for (final SegmentEndpoint pathPoint : endPoints) {
- if (pathPoint.intersects(plane, notablePoints, bounds)) {
- return true;
- }
- }
-
- for (final PathSegment pathSegment : segments) {
- if (pathSegment.intersects(plane, notablePoints, bounds)) {
- return true;
- }
+ if (rootComponent == null) {
+ return false;
}
-
- return false;
+ return rootComponent.intersects(plane, notablePoints, bounds);
}
@Override
public boolean intersects(GeoShape geoShape) {
- for (final SegmentEndpoint pathPoint : endPoints) {
- if (pathPoint.intersects(geoShape)) {
- return true;
- }
- }
-
- for (final PathSegment pathSegment : segments) {
- if (pathSegment.intersects(geoShape)) {
- return true;
- }
+ if (rootComponent == null) {
+ return false;
}
-
- return false;
+ return rootComponent.intersects(geoShape);
}
@Override
public void getBounds(Bounds bounds) {
super.getBounds(bounds);
- // For building bounds, order matters. We want to traverse
- // never more than 180 degrees longitude at a pop or we risk having the
- // bounds object get itself inverted. So do the edges first.
- for (PathSegment pathSegment : segments) {
- pathSegment.getBounds(bounds);
- }
- for (SegmentEndpoint pathPoint : endPoints) {
- pathPoint.getBounds(bounds);
+ if (rootComponent != null) {
+ rootComponent.getBounds(bounds);
}
}
@@ -700,6 +627,7 @@ class GeoStandardPath extends GeoBasePath {
bounds = new XYZBounds();
child1.getBounds(bounds);
child2.getBounds(bounds);
+ //System.out.println("Constructed PathNode with child1="+child1+" and child2="+child2+" with computed bounds "+bounds);
}
@Override
@@ -711,6 +639,8 @@ class GeoStandardPath extends GeoBasePath {
public boolean isWithin(final double x, final double y, final double z) {
// We computed the bounds for the node already, so use that as an "early-out".
// If we don't leave early, we need to check both children.
+ // This code breaks things; not sure why yet. TBD
+
if (x < bounds.getMinimumX() || x > bounds.getMaximumX()) {
return false;
}
@@ -720,6 +650,7 @@ class GeoStandardPath extends GeoBasePath {
if (z < bounds.getMinimumZ() || z > bounds.getMaximumZ()) {
return false;
}
+
return child1.isWithin(x, y, z) || child2.isWithin(x, y, z);
}
@@ -809,6 +740,11 @@ class GeoStandardPath extends GeoBasePath {
child2.getBounds(bounds);
}
}
+
+ @Override
+ public String toString() {
+ return "PathNode ("+child1+") ("+child2+")";
+ }
}
/**
@@ -827,9 +763,7 @@ class GeoStandardPath extends GeoBasePath {
private interface SegmentEndpoint extends PathComponent {}
/** Base implementation of SegmentEndpoint */
- private static class BaseSegmentEndpoint implements SegmentEndpoint {
- /** The planet model */
- protected final PlanetModel planetModel;
+ private static class BaseSegmentEndpoint extends GeoBaseBounds implements SegmentEndpoint {
/** The previous path element */
protected final PathComponent previous;
/** The center point of the endpoint */
@@ -839,7 +773,7 @@ class GeoStandardPath extends GeoBasePath {
public BaseSegmentEndpoint(
final PlanetModel planetModel, final PathComponent previous, final GeoPoint point) {
- this.planetModel = planetModel;
+ super(planetModel);
this.previous = previous;
this.point = point;
}
@@ -918,6 +852,7 @@ class GeoStandardPath extends GeoBasePath {
@Override
public void getBounds(final Bounds bounds) {
+ super.getBounds(bounds);
bounds.addPoint(point);
}
@@ -937,7 +872,7 @@ class GeoStandardPath extends GeoBasePath {
@Override
public String toString() {
- return point.toString();
+ return "SegmentEndpoint ("+point+")";
}
}
@@ -1269,9 +1204,7 @@ class GeoStandardPath extends GeoBasePath {
}
/** This is the pre-calculated data for a path segment. */
- private static class PathSegment implements PathComponent {
- /** Planet model */
- public final PlanetModel planetModel;
+ private static class PathSegment extends GeoBaseBounds implements PathComponent {
/** Previous path component */
public final PathComponent previous;
/** Starting point of the segment */
@@ -1319,7 +1252,7 @@ class GeoStandardPath extends GeoBasePath {
final GeoPoint end,
final Plane normalizedConnectingPlane,
final double planeBoundingOffset) {
- this.planetModel = planetModel;
+ super(planetModel);
this.previous = previous;
this.start = start;
this.end = end;
@@ -1724,6 +1657,7 @@ class GeoStandardPath extends GeoBasePath {
@Override
public void getBounds(final Bounds bounds) {
+ super.getBounds(bounds);
// We need to do all bounding planes as well as corner points
bounds
.addPoint(start)
@@ -1781,6 +1715,11 @@ class GeoStandardPath extends GeoBasePath {
startCutoffPlane,
lowerConnectingPlane);
}
+
+ @Override
+ public String toString() {
+ return "PathSegment ("+ULHC+", "+URHC+", "+LRHC+", "+LLHC+")";
+ }
}
private static class TreeBuilder {
@@ -1816,9 +1755,9 @@ class GeoStandardPath extends GeoBasePath {
private void mergeTop() {
depthStack.remove(depthStack.size() - 1);
- PathComponent firstComponent = componentStack.remove(componentStack.size() - 1);
- int newDepth = depthStack.remove(depthStack.size() - 1);
PathComponent secondComponent = componentStack.remove(componentStack.size() - 1);
+ int newDepth = depthStack.remove(depthStack.size() - 1) + 1;
+ PathComponent firstComponent = componentStack.remove(componentStack.size() - 1);
depthStack.add(newDepth);
componentStack.add(new PathNode(firstComponent, secondComponent));
}
[lucene] 01/03: Add node structures and fast operations for them.
Posted by kw...@apache.org.
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 fbdb655221216e3c4d1837199e9d9a94059a9fb6
Author: Karl David Wright <kw...@apache.org>
AuthorDate: Sat Nov 19 07:49:31 2022 -0500
Add node structures and fast operations for them.
---
.../lucene/spatial3d/geom/GeoStandardPath.java | 321 +++++++++++++++++++--
.../apache/lucene/spatial3d/geom/XYZBounds.java | 26 ++
2 files changed, 322 insertions(+), 25 deletions(-)
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 f25d385a77c..1f997100e1a 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
@@ -48,6 +48,8 @@ class GeoStandardPath extends GeoBasePath {
protected List<SegmentEndpoint> endPoints;
/** A list of PathSegments */
protected List<PathSegment> segments;
+ /** The b-tree of PathComponents */
+ protected PathComponent rootComponent;
/** A point on the edge */
protected GeoPoint[] edgePoints;
@@ -114,13 +116,36 @@ class GeoStandardPath extends GeoBasePath {
// the entire ellipsoid.
final double cutoffOffset = this.sinAngle * planetModel.getMinimumMagnitude();
+ // The major output we want to produce here is a balanced binary tree of PathComponents.
+ // This code first produces a list of path segments and segment endpoints, and then we do
+ // the following:
+ // (0) Initialize a "stack", which contains ordered path components
+ // (1) Walk through the path components in order
+ // (2) Add the next path component to the stack
+ // (3) If there are two path components of the same depth, remove them and add a PathNode
+ // with them as children
+ // (4) At the end, if there are more than one thing on the stack, build a final PathNode
+ // with those two
+ // (5) Use the top element as the root.
+ // I've structured this as its own class that just receives path components in order,
+ // and returns the final one at the end.
+
// First, build all segments. We'll then go back and build corresponding segment endpoints.
GeoPoint lastPoint = null;
+ PathComponent lastComponent = null;
for (final GeoPoint end : points) {
if (lastPoint != null) {
final Plane normalizedConnectingPlane = new Plane(lastPoint, end);
- segments.add(
- new PathSegment(planetModel, lastPoint, end, normalizedConnectingPlane, cutoffOffset));
+ final PathSegment newComponent =
+ new PathSegment(
+ planetModel,
+ lastComponent,
+ lastPoint,
+ end,
+ normalizedConnectingPlane,
+ cutoffOffset);
+ segments.add(newComponent);
+ lastComponent = newComponent;
}
lastPoint = end;
}
@@ -157,7 +182,7 @@ class GeoStandardPath extends GeoBasePath {
final Plane normalPlane = Plane.constructNormalizedZPlane(upperPoint, lowerPoint, point);
final CircleSegmentEndpoint onlyEndpoint =
- new CircleSegmentEndpoint(planetModel, point, normalPlane, upperPoint, lowerPoint);
+ new CircleSegmentEndpoint(planetModel, null, point, normalPlane, upperPoint, lowerPoint);
endPoints.add(onlyEndpoint);
this.edgePoints =
new GeoPoint[] {
@@ -175,6 +200,7 @@ class GeoStandardPath extends GeoBasePath {
final SegmentEndpoint startEndpoint =
new CutoffSingleCircleSegmentEndpoint(
planetModel,
+ null,
currentSegment.start,
currentSegment.startCutoffPlane,
currentSegment.ULHC,
@@ -195,6 +221,7 @@ class GeoStandardPath extends GeoBasePath {
final SegmentEndpoint midEndpoint =
new CutoffSingleCircleSegmentEndpoint(
planetModel,
+ prevSegment,
currentSegment.start,
prevSegment.endCutoffPlane,
currentSegment.startCutoffPlane,
@@ -206,6 +233,7 @@ class GeoStandardPath extends GeoBasePath {
endPoints.add(
new CutoffDualCircleSegmentEndpoint(
planetModel,
+ prevSegment,
currentSegment.start,
prevSegment.endCutoffPlane,
currentSegment.startCutoffPlane,
@@ -220,10 +248,22 @@ class GeoStandardPath extends GeoBasePath {
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));
+ for (int i = 0; i < segments.size(); i++) {
+ treeBuilder.addComponent(segments.get(i));
+ treeBuilder.addComponent(endPoints.get(i + 1));
+ }
+
+ rootComponent = treeBuilder.getRoot();
}
/**
@@ -544,6 +584,22 @@ class GeoStandardPath extends GeoBasePath {
*/
boolean isWithin(final double x, final double y, final double z);
+ /**
+ * Retrieve the starting distance along the path for this path element.
+ *
+ * @param distanceStyle is the distance style
+ * @return the starting path distance in aggregation form
+ */
+ double getStartingDistance(final DistanceStyle distanceStyle);
+
+ /**
+ * Compute the total distance this path component adds to the path.
+ *
+ * @param distanceStyle is the distance style.
+ * @return the full path distance.
+ */
+ double fullPathDistance(final DistanceStyle distanceStyle);
+
/**
* Compute path distance.
*
@@ -632,6 +688,129 @@ class GeoStandardPath extends GeoBasePath {
void getBounds(final Bounds bounds);
}
+ private static class PathNode implements PathComponent {
+ protected final PathComponent child1;
+ protected final PathComponent child2;
+
+ protected final XYZBounds bounds;
+
+ public PathNode(final PathComponent child1, final PathComponent child2) {
+ this.child1 = child1;
+ this.child2 = child2;
+ bounds = new XYZBounds();
+ child1.getBounds(bounds);
+ child2.getBounds(bounds);
+ }
+
+ @Override
+ public boolean isWithin(final Vector point) {
+ return isWithin(point.x, point.y, point.z);
+ }
+
+ @Override
+ 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.
+ if (x < bounds.getMinimumX() || x > bounds.getMaximumX()) {
+ return false;
+ }
+ if (y < bounds.getMinimumY() || y > bounds.getMaximumY()) {
+ return false;
+ }
+ if (z < bounds.getMinimumZ() || z > bounds.getMaximumZ()) {
+ return false;
+ }
+ return child1.isWithin(x, y, z) || child2.isWithin(x, y, z);
+ }
+
+ @Override
+ public double getStartingDistance(final DistanceStyle distanceStyle) {
+ return child1.getStartingDistance(distanceStyle);
+ }
+
+ @Override
+ public double fullPathDistance(final DistanceStyle distanceStyle) {
+ return distanceStyle.aggregateDistances(
+ child1.fullPathDistance(distanceStyle), child2.fullPathDistance(distanceStyle));
+ }
+
+ @Override
+ public double pathDistance(
+ final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ if (!isWithin(x, y, z)) {
+ return Double.POSITIVE_INFINITY;
+ }
+ return Math.min(
+ child1.pathDistance(distanceStyle, x, y, z),
+ distanceStyle.aggregateDistances(
+ child1.fullPathDistance(distanceStyle), child2.pathDistance(distanceStyle, x, y, z)));
+ }
+
+ @Override
+ public double pathDeltaDistance(
+ final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ if (!isWithin(x, y, z)) {
+ return Double.POSITIVE_INFINITY;
+ }
+ return Math.min(
+ child1.pathDeltaDistance(distanceStyle, x, y, z),
+ child2.pathDeltaDistance(distanceStyle, x, y, z));
+ }
+
+ @Override
+ public double nearestPathDistance(
+ final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ if (!isWithin(x, y, z)) {
+ return Double.POSITIVE_INFINITY;
+ }
+ return Math.min(
+ child1.nearestPathDistance(distanceStyle, x, y, z),
+ child2.nearestPathDistance(distanceStyle, x, y, z));
+ }
+
+ @Override
+ public double pathCenterDistance(
+ final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ if (!isWithin(x, y, z)) {
+ return Double.POSITIVE_INFINITY;
+ }
+ return Math.min(
+ child1.pathCenterDistance(distanceStyle, x, y, z),
+ child2.pathCenterDistance(distanceStyle, x, y, z));
+ }
+
+ @Override
+ public double outsideDistance(
+ final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ // No early-out for this one; all sections must be considered
+ return Math.min(
+ child1.outsideDistance(distanceStyle, x, y, z),
+ child2.outsideDistance(distanceStyle, x, y, z));
+ }
+
+ @Override
+ public boolean intersects(
+ final Plane p, final GeoPoint[] notablePoints, final Membership[] bounds) {
+ return child1.intersects(p, notablePoints, bounds)
+ || child2.intersects(p, notablePoints, bounds);
+ }
+
+ @Override
+ public boolean intersects(final GeoShape geoShape) {
+ return child1.intersects(geoShape) || child2.intersects(geoShape);
+ }
+
+ @Override
+ public void getBounds(final Bounds bounds) {
+ if (bounds instanceof XYZBounds) {
+ this.bounds.addBounds((XYZBounds) bounds);
+ } else {
+ child1.getBounds(bounds);
+ child2.getBounds(bounds);
+ }
+ }
+ }
+
/**
* Internal interface describing segment endpoint implementations. There are several different
* such implementations, each corresponding to a different geometric conformation. Note well: This
@@ -651,13 +830,17 @@ class GeoStandardPath extends GeoBasePath {
private static class BaseSegmentEndpoint implements SegmentEndpoint {
/** The planet model */
protected final PlanetModel planetModel;
+ /** The previous path element */
+ protected final PathComponent previous;
/** The center point of the endpoint */
protected final GeoPoint point;
/** Null membership */
protected static final Membership[] NO_MEMBERSHIP = new Membership[0];
- public BaseSegmentEndpoint(final PlanetModel planetModel, final GeoPoint point) {
+ public BaseSegmentEndpoint(
+ final PlanetModel planetModel, final PathComponent previous, final GeoPoint point) {
this.planetModel = planetModel;
+ this.previous = previous;
this.point = point;
}
@@ -671,6 +854,19 @@ class GeoStandardPath extends GeoBasePath {
return false;
}
+ @Override
+ public double getStartingDistance(DistanceStyle distanceStyle) {
+ if (previous == null) {
+ return 0.0;
+ }
+ return previous.getStartingDistance(distanceStyle);
+ }
+
+ @Override
+ public double fullPathDistance(final DistanceStyle distanceStyle) {
+ return 0.0;
+ }
+
@Override
public double pathDeltaDistance(
final DistanceStyle distanceStyle, final double x, final double y, final double z) {
@@ -762,11 +958,12 @@ class GeoStandardPath extends GeoBasePath {
*/
public CircleSegmentEndpoint(
final PlanetModel planetModel,
+ final PathComponent previous,
final GeoPoint point,
final Plane normalPlane,
final GeoPoint upperPoint,
final GeoPoint lowerPoint) {
- super(planetModel, point);
+ super(planetModel, previous, point);
// Construct a sided plane that goes through the two points and whose normal is in the
// normalPlane.
this.circlePlane =
@@ -781,8 +978,11 @@ class GeoStandardPath extends GeoBasePath {
* @param circlePlane is the circle plane.
*/
protected CircleSegmentEndpoint(
- final PlanetModel planetModel, final GeoPoint point, final SidedPlane circlePlane) {
- super(planetModel, point);
+ final PlanetModel planetModel,
+ final PathComponent previous,
+ final GeoPoint point,
+ final SidedPlane circlePlane) {
+ super(planetModel, previous, point);
this.circlePlane = circlePlane;
}
@@ -836,11 +1036,12 @@ class GeoStandardPath extends GeoBasePath {
*/
public CutoffSingleCircleSegmentEndpoint(
final PlanetModel planetModel,
+ final PathComponent previous,
final GeoPoint point,
final SidedPlane cutoffPlane,
final GeoPoint topEdgePoint,
final GeoPoint bottomEdgePoint) {
- super(planetModel, point, cutoffPlane, topEdgePoint, bottomEdgePoint);
+ super(planetModel, previous, point, cutoffPlane, topEdgePoint, bottomEdgePoint);
this.cutoffPlanes = new Membership[] {new SidedPlane(cutoffPlane)};
this.notablePoints = new GeoPoint[] {topEdgePoint, bottomEdgePoint};
}
@@ -859,12 +1060,13 @@ class GeoStandardPath extends GeoBasePath {
*/
public CutoffSingleCircleSegmentEndpoint(
final PlanetModel planetModel,
+ final PathComponent previous,
final GeoPoint point,
final SidedPlane cutoffPlane1,
final SidedPlane cutoffPlane2,
final GeoPoint topEdgePoint,
final GeoPoint bottomEdgePoint) {
- super(planetModel, point, cutoffPlane1, topEdgePoint, bottomEdgePoint);
+ super(planetModel, previous, point, cutoffPlane1, topEdgePoint, bottomEdgePoint);
this.cutoffPlanes =
new Membership[] {new SidedPlane(cutoffPlane1), new SidedPlane(cutoffPlane2)};
this.notablePoints = new GeoPoint[] {topEdgePoint, bottomEdgePoint};
@@ -955,6 +1157,7 @@ class GeoStandardPath extends GeoBasePath {
public CutoffDualCircleSegmentEndpoint(
final PlanetModel planetModel,
+ final PathComponent previous,
final GeoPoint point,
final SidedPlane prevCutoffPlane,
final SidedPlane nextCutoffPlane,
@@ -963,7 +1166,7 @@ class GeoStandardPath extends GeoBasePath {
final GeoPoint currentULHC,
final GeoPoint currentLLHC) {
// Initialize superclass
- super(planetModel, point);
+ super(planetModel, previous, point);
// First plane consists of prev endpoints plus one of the current endpoints (the one past the
// end of the prev segment)
if (!prevCutoffPlane.isWithin(currentULHC)) {
@@ -1069,12 +1272,14 @@ class GeoStandardPath extends GeoBasePath {
private static class PathSegment implements PathComponent {
/** Planet model */
public final PlanetModel planetModel;
+ /** Previous path component */
+ public final PathComponent previous;
/** Starting point of the segment */
public final GeoPoint start;
/** End point of the segment */
public final GeoPoint end;
/** Place to keep any complete segment distances we've calculated so far */
- public final Map<DistanceStyle, Double> fullDistanceCache = new ConcurrentHashMap<>();
+ public final Map<DistanceStyle, Double> startDistanceCache = new ConcurrentHashMap<>(1);
/** Normalized plane connecting the two points and going through world center */
public final Plane normalizedConnectingPlane;
/** Cutoff plane parallel to connecting plane representing one side of the path segment */
@@ -1109,11 +1314,13 @@ class GeoStandardPath extends GeoBasePath {
*/
public PathSegment(
final PlanetModel planetModel,
+ final PathComponent previous,
final GeoPoint start,
final GeoPoint end,
final Plane normalizedConnectingPlane,
final double planeBoundingOffset) {
this.planetModel = planetModel;
+ this.previous = previous;
this.start = start;
this.end = end;
this.normalizedConnectingPlane = normalizedConnectingPlane;
@@ -1173,21 +1380,10 @@ class GeoStandardPath extends GeoBasePath {
lowerConnectingPlanePoints = new GeoPoint[] {LLHC, LRHC};
}
- /**
- * Compute the full distance along this path segment.
- *
- * @param distanceStyle is the distance style.
- * @return the distance metric, in aggregation form.
- */
+ @Override
public double fullPathDistance(final DistanceStyle distanceStyle) {
- Double dist = fullDistanceCache.get(distanceStyle);
- if (dist == null) {
- dist =
- distanceStyle.toAggregationForm(
- distanceStyle.computeDistance(start, end.x, end.y, end.z));
- fullDistanceCache.put(distanceStyle, dist);
- }
- return dist.doubleValue();
+ return distanceStyle.toAggregationForm(
+ distanceStyle.computeDistance(start, end.x, end.y, end.z));
}
@Override
@@ -1203,9 +1399,30 @@ class GeoStandardPath extends GeoBasePath {
return isWithin(v.x, v.y, v.z);
}
+ @Override
+ public double getStartingDistance(final DistanceStyle distanceStyle) {
+ Double dist = startDistanceCache.get(distanceStyle);
+ if (dist == null) {
+ dist = computeStartingDistance(distanceStyle);
+ startDistanceCache.put(distanceStyle, dist);
+ }
+ return dist.doubleValue();
+ }
+
+ private double computeStartingDistance(final DistanceStyle distanceStyle) {
+ if (previous == null) {
+ return 0.0;
+ }
+ return distanceStyle.aggregateDistances(
+ previous.getStartingDistance(distanceStyle), previous.fullPathDistance(distanceStyle));
+ }
+
@Override
public double pathCenterDistance(
final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ // Computes the distance to the path center from the specified point, or returns
+ // POSITIVE_INFINITY if the point is outside the path.
+
// First, if this point is outside the endplanes of the segment, return POSITIVE_INFINITY.
if (!startCutoffPlane.isWithin(x, y, z) || !endCutoffPlane.isWithin(x, y, z)) {
return Double.POSITIVE_INFINITY;
@@ -1252,6 +1469,9 @@ class GeoStandardPath extends GeoBasePath {
@Override
public double nearestPathDistance(
final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ // Computes the distance along the path to a point on the path where a perpendicular plane
+ // goes through the specified point.
+
// First, if this point is outside the endplanes of the segment, return POSITIVE_INFINITY.
if (!startCutoffPlane.isWithin(x, y, z) || !endCutoffPlane.isWithin(x, y, z)) {
return Double.POSITIVE_INFINITY;
@@ -1299,6 +1519,9 @@ class GeoStandardPath extends GeoBasePath {
@Override
public double pathDeltaDistance(
final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ // Returns 2x the pathCenterDistance. Represents the cost of an "excursion" to and
+ // from the path.
+
if (!isWithin(x, y, z)) {
return Double.POSITIVE_INFINITY;
}
@@ -1351,6 +1574,10 @@ class GeoStandardPath extends GeoBasePath {
@Override
public double pathDistance(
final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+
+ // Computes the distance along the path to a perpendicular point to the desired point,
+ // and adds the distance from the path to the desired point.
+
if (!isWithin(x, y, z)) {
return Double.POSITIVE_INFINITY;
}
@@ -1404,6 +1631,9 @@ class GeoStandardPath extends GeoBasePath {
@Override
public double outsideDistance(
final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+
+ // Computes the minimum distance from the point to any of the segment's bounding planes.
+ // Only computes distances outside of the shape; inside, a value of 0.0 is returned.
final double upperDistance =
distanceStyle.computeDistance(
planetModel,
@@ -1552,4 +1782,45 @@ class GeoStandardPath extends GeoBasePath {
lowerConnectingPlane);
}
}
+
+ private static class TreeBuilder {
+ private final List<PathComponent> componentStack;
+ private final List<Integer> depthStack;
+
+ public TreeBuilder(final int max) {
+ componentStack = new ArrayList<>(max);
+ depthStack = new ArrayList<>(max);
+ }
+
+ public void addComponent(final PathComponent component) {
+ componentStack.add(component);
+ depthStack.add(0);
+ while (depthStack.size() >= 2) {
+ if (depthStack.get(depthStack.size() - 1) == depthStack.get(depthStack.size() - 2)) {
+ mergeTop();
+ } else {
+ break;
+ }
+ }
+ }
+
+ public PathComponent getRoot() {
+ if (componentStack.size() == 0) {
+ return null;
+ }
+ while (componentStack.size() > 1) {
+ mergeTop();
+ }
+ return componentStack.get(0);
+ }
+
+ 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);
+ depthStack.add(newDepth);
+ componentStack.add(new PathNode(firstComponent, secondComponent));
+ }
+ }
}
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/XYZBounds.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/XYZBounds.java
index 31835ae6b0a..27ed4d571ae 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/XYZBounds.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/XYZBounds.java
@@ -178,6 +178,32 @@ public class XYZBounds implements Bounds {
// Modification methods
+ /**
+ * Add a fully-formed XYZBounds to the current one.
+ *
+ * @param bounds is the bounds object to modify
+ */
+ public void addBounds(final XYZBounds bounds) {
+ if (bounds.maxX == null || maxX > bounds.maxX) {
+ bounds.maxX = maxX;
+ }
+ if (bounds.minX == null || minX < bounds.minX) {
+ bounds.minX = minX;
+ }
+ if (bounds.maxY == null || maxY > bounds.maxY) {
+ bounds.maxY = maxY;
+ }
+ if (bounds.minY == null || minY < bounds.minY) {
+ bounds.minY = minY;
+ }
+ if (bounds.maxZ == null || maxZ > bounds.maxZ) {
+ bounds.maxZ = maxZ;
+ }
+ if (bounds.minZ == null || minZ < bounds.minZ) {
+ bounds.minZ = minZ;
+ }
+ }
+
@Override
public Bounds addPlane(
final PlanetModel planetModel, final Plane plane, final Membership... bounds) {
[lucene] 03/03: Fix up formatting
Posted by kw...@apache.org.
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 1e236090af55f4ba01003ac96946a121de724cb0
Author: Karl David Wright <kw...@apache.org>
AuthorDate: Sat Nov 19 17:44:24 2022 -0500
Fix up formatting
---
.../apache/lucene/spatial3d/geom/GeoBounds.java | 7 +-
.../lucene/spatial3d/geom/GeoStandardPath.java | 88 +++++++++++-----------
2 files changed, 48 insertions(+), 47 deletions(-)
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
index 935366c5a08..3e72fbb1c17 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBounds.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoBounds.java
@@ -17,11 +17,8 @@
package org.apache.lucene.spatial3d.geom;
/**
- * Generic shape that supports bounds. This describes methods that help
- * shapes compute their bounds.
+ * Generic shape that supports bounds. This describes methods that help shapes compute their bounds.
*
* @lucene.experimental
*/
-public interface GeoBounds extends Bounded, Membership, PlanetObject {
-
-}
+public interface GeoBounds extends Bounded, Membership, PlanetObject {}
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 16a07009b64..f975ecac4e2 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
@@ -189,20 +189,21 @@ class GeoStandardPath extends GeoBasePath {
onlyEndpoint.circlePlane.getSampleIntersectionPoint(planetModel, normalPlane)
};
} else {
- // Create segment endpoints. Use an appropriate constructor for the start and end of the path.
+ // 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);
+ new CutoffSingleCircleSegmentEndpoint(
+ planetModel,
+ null,
+ currentSegment.start,
+ currentSegment.startCutoffPlane,
+ currentSegment.ULHC,
+ currentSegment.LLHC);
endPoints.add(startEndpoint);
this.edgePoints = new GeoPoint[] {currentSegment.ULHC};
continue;
@@ -214,43 +215,44 @@ class GeoStandardPath extends GeoBasePath {
&& 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
+ // 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);
+ 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));
+ 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));
+ new CutoffSingleCircleSegmentEndpoint(
+ planetModel,
+ lastSegment,
+ lastSegment.end,
+ lastSegment.endCutoffPlane,
+ lastSegment.URHC,
+ lastSegment.LRHC));
}
final TreeBuilder treeBuilder = new TreeBuilder(segments.size() + endPoints.size());
@@ -264,7 +266,7 @@ class GeoStandardPath extends GeoBasePath {
rootComponent = treeBuilder.getRoot();
- //System.out.println("Root component: "+rootComponent);
+ // System.out.println("Root component: "+rootComponent);
}
/**
@@ -334,7 +336,7 @@ class GeoStandardPath extends GeoBasePath {
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.
@@ -384,7 +386,8 @@ class GeoStandardPath extends GeoBasePath {
if (rootComponent == null) {
return Double.POSITIVE_INFINITY;
}
- return distanceStyle.fromAggregationForm(rootComponent.pathDeltaDistance(distanceStyle, x, y, z));
+ return distanceStyle.fromAggregationForm(
+ rootComponent.pathDeltaDistance(distanceStyle, x, y, z));
}
@Override
@@ -627,7 +630,8 @@ 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);
+ // System.out.println("Constructed PathNode with child1="+child1+" and child2="+child2+" with
+ // computed bounds "+bounds);
}
@Override
@@ -640,7 +644,7 @@ class GeoStandardPath extends GeoBasePath {
// 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;
}
@@ -743,7 +747,7 @@ class GeoStandardPath extends GeoBasePath {
@Override
public String toString() {
- return "PathNode ("+child1+") ("+child2+")";
+ return "PathNode (" + child1 + ") (" + child2 + ")";
}
}
@@ -872,7 +876,7 @@ class GeoStandardPath extends GeoBasePath {
@Override
public String toString() {
- return "SegmentEndpoint ("+point+")";
+ return "SegmentEndpoint (" + point + ")";
}
}
@@ -1718,7 +1722,7 @@ class GeoStandardPath extends GeoBasePath {
@Override
public String toString() {
- return "PathSegment ("+ULHC+", "+URHC+", "+LRHC+", "+LLHC+")";
+ return "PathSegment (" + ULHC + ", " + URHC + ", " + LRHC + ", " + LLHC + ")";
}
}