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/22 01:02:23 UTC
[lucene] 01/03: Refactor and make hierarchical GeoStandardPath. Some tests fail and will need to be researched further.
This is an automated email from the ASF dual-hosted git repository.
kwright pushed a commit to branch revamp_geopath
in repository https://gitbox.apache.org/repos/asf/lucene.git
commit 20fcd0b757c038cf9566941a2192aab3712854e0
Author: Karl David Wright <kw...@apache.org>
AuthorDate: Mon Nov 21 18:39:50 2022 -0500
Refactor and make hierarchical GeoStandardPath. Some tests fail and will need to be researched further.
---
.../lucene/spatial3d/geom/GeoStandardPath.java | 659 ++++++++++-----------
.../org/apache/lucene/spatial3d/geom/Plane.java | 155 +++++
.../apache/lucene/spatial3d/geom/SidedPlane.java | 10 +
.../apache/lucene/spatial3d/geom/TestGeoPath.java | 1 +
4 files changed, 478 insertions(+), 347 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 db2879686ce..c761b7453b2 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
@@ -179,6 +179,7 @@ class GeoStandardPath extends GeoBasePath {
final GeoPoint point = points.get(0);
// Construct normal plane
+ // TBD - what does this actually do? Why Z??
final Plane normalPlane = Plane.constructNormalizedZPlane(upperPoint, lowerPoint, point);
final CircleSegmentEndpoint onlyEndpoint =
@@ -188,48 +189,53 @@ 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 =
- new CutoffSingleCircleSegmentEndpoint(
- planetModel,
- null,
- currentSegment.start,
- currentSegment.startCutoffPlane,
- currentSegment.ULHC,
- currentSegment.LLHC);
- endPoints.add(startEndpoint);
- this.edgePoints = new GeoPoint[] {currentSegment.ULHC};
- continue;
- }
+ } 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;
+ }
- // 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 {
+ // General intersection case.
+ // The CutoffDualCircleSegmentEndpoint is advanced enough now to handle
+ // joinings that are perfectly in a line, I believe, so I am disabling
+ // the special code for that situation. TBD (and testing) to remove it.
+ 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,
@@ -241,29 +247,32 @@ class GeoStandardPath extends GeoBasePath {
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,134 +298,38 @@ 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;
- }
- }
- // Now, endpoints
- for (SegmentEndpoint endpoint : endPoints) {
- final double endpointDistance = endpoint.pathCenterDistance(distanceStyle, x, y, z);
- if (endpointDistance < closestDistance) {
- closestDistance = endpointDistance;
- }
+ if (rootComponent == null) {
+ return Double.POSITIVE_INFINITY;
}
- 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) {
- double currentDistance = 0.0;
- double minPathCenterDistance = Double.POSITIVE_INFINITY;
- double bestDistance = Double.POSITIVE_INFINITY;
- int segmentIndex = 0;
-
- for (final SegmentEndpoint endpoint : endPoints) {
- final double endpointPathCenterDistance = endpoint.pathCenterDistance(distanceStyle, x, y, z);
- if (endpointPathCenterDistance < minPathCenterDistance) {
- // Use this endpoint
- minPathCenterDistance = endpointPathCenterDistance;
- bestDistance = currentDistance;
- }
- // Look at the following segment, if any
- if (segmentIndex < segments.size()) {
- final PathSegment segment = segments.get(segmentIndex++);
- final double segmentPathCenterDistance = segment.pathCenterDistance(distanceStyle, x, y, z);
- if (segmentPathCenterDistance < minPathCenterDistance) {
- minPathCenterDistance = segmentPathCenterDistance;
- bestDistance =
- distanceStyle.aggregateDistances(
- currentDistance, segment.nearestPathDistance(distanceStyle, x, y, z));
- }
- currentDistance =
- distanceStyle.aggregateDistances(
- currentDistance, segment.fullPathDistance(distanceStyle));
- }
+ if (rootComponent == null) {
+ return Double.POSITIVE_INFINITY;
}
- return bestDistance;
+ return rootComponent.nearestDistance(distanceStyle, x, y, z);
}
@Override
protected double distance(
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.
- // The algorithm loops over the whole path to get the shortest distance
- double bestDistance = Double.POSITIVE_INFINITY;
-
- double currentDistance = 0.0;
- for (final PathSegment segment : segments) {
- double distance = segment.pathDistance(distanceStyle, x, y, z);
- if (distance != Double.POSITIVE_INFINITY) {
- final double thisDistance =
- distanceStyle.fromAggregationForm(
- distanceStyle.aggregateDistances(currentDistance, distance));
- if (thisDistance < bestDistance) {
- bestDistance = thisDistance;
- }
- }
- currentDistance =
- distanceStyle.aggregateDistances(
- currentDistance, segment.fullPathDistance(distanceStyle));
- }
-
- int segmentIndex = 0;
- currentDistance = 0.0;
- for (final SegmentEndpoint endpoint : endPoints) {
- double distance = endpoint.pathDistance(distanceStyle, x, y, z);
- if (distance != Double.POSITIVE_INFINITY) {
- final double thisDistance =
- distanceStyle.fromAggregationForm(
- distanceStyle.aggregateDistances(currentDistance, distance));
- if (thisDistance < bestDistance) {
- bestDistance = thisDistance;
- }
- }
- if (segmentIndex < segments.size())
- currentDistance =
- distanceStyle.aggregateDistances(
- currentDistance, segments.get(segmentIndex++).fullPathDistance(distanceStyle));
+ if (rootComponent == null) {
+ return Double.POSITIVE_INFINITY;
}
-
- return bestDistance;
+ return rootComponent.distance(distanceStyle, x, y, z);
}
@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;
- }
- }
- }
-
- 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;
- }
- }
+ if (rootComponent == null) {
+ return Double.POSITIVE_INFINITY;
}
-
- return bestDistance;
+ return distanceStyle.fromAggregationForm(
+ rootComponent.pathDeltaDistance(distanceStyle, x, y, z));
}
@Override
@@ -429,35 +342,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;
- }
- }
- for (final PathSegment segment : segments) {
- final double newDistance = segment.outsideDistance(distanceStyle, x, y, z);
- if (newDistance < minDistance) {
- minDistance = newDistance;
- }
+ if (rootComponent == null) {
+ return Double.POSITIVE_INFINITY;
}
- 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 +374,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);
}
}
@@ -600,6 +472,33 @@ class GeoStandardPath extends GeoBasePath {
*/
double fullPathDistance(final DistanceStyle distanceStyle);
+ /**
+ * Compute distance measure starting from beginning of the path and including perpendicular
+ * dog-leg to a point within the corridor.
+ *
+ * @param distanceStyle is the distance style
+ * @param x is the x coordinate of the point we want to get the distance to
+ * @param y is the y coordinate of the point we want to get the distance to
+ * @param z is the z coordinate of the point we want to get the distance to
+ * @return the distance from start of path
+ */
+ double distance(
+ final DistanceStyle distanceStyle, final double x, final double y, final double z);
+
+ /**
+ * Compute distance starting from the beginning of the path all along the center of the
+ * corridor, and then for the last section to a point perpendicular to mentioned point, unless
+ * that point is outside of the corridor.
+ *
+ * @param distanceStyle is the distance style
+ * @param x is the x coordinate of the point we want to get the distance to
+ * @param y is the y coordinate of the point we want to get the distance to
+ * @param z is the z coordinate of the point we want to get the distance to
+ * @return the distance from start of path
+ */
+ double nearestDistance(
+ final DistanceStyle distanceStyle, final double x, final double y, final double z);
+
/**
* Compute path distance.
*
@@ -638,7 +537,8 @@ class GeoStandardPath extends GeoBasePath {
final DistanceStyle distanceStyle, final double x, final double y, final double z);
/**
- * Compute path center distance.
+ * Compute path center distance. Returns POSITIVE_INFINITY if the point is outside of the
+ * bounds.
*
* @param distanceStyle is the distance style.
* @param x is the point x.
@@ -700,6 +600,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);
}
@Override
@@ -711,15 +613,27 @@ 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.
- 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()) {
+ if (x < bounds.getMinimumX()
+ || x > bounds.getMaximumX()
+ || y < bounds.getMinimumY()
+ || y > bounds.getMaximumY()
+ || z < bounds.getMinimumZ()
+ || z > bounds.getMaximumZ()) {
+ // Debugging: check that this really is true.
+ /*
+ if (child1.isWithin(x, y, z) || child2.isWithin(x, y, z)) {
+ System.out.println("XYZBounds of PathNode inconsistent with isWithin of children! XYZBounds="+bounds+" child1="+child1+" child2="+child2+" Point=["+x+", "+y+", "+z+"]");
+ XYZBounds ch1Bounds = new XYZBounds();
+ child1.getBounds(ch1Bounds);
+ XYZBounds ch2Bounds = new XYZBounds();
+ child2.getBounds(ch2Bounds);
+ System.out.println("Child1: Bounds="+ch1Bounds+" isWithin="+child1.isWithin(x,y,z));
+ System.out.println("Child2: Bounds="+ch2Bounds+" isWithin="+child2.isWithin(x,y,z));
+ }
+ */
return false;
}
+
return child1.isWithin(x, y, z) || child2.isWithin(x, y, z);
}
@@ -728,6 +642,30 @@ class GeoStandardPath extends GeoBasePath {
return child1.getStartingDistance(distanceStyle);
}
+ @Override
+ public double distance(
+ final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ if (!isWithin(x, y, z)) {
+ return Double.POSITIVE_INFINITY;
+ }
+ final double child1Distance = child1.distance(distanceStyle, x, y, z);
+ final double child2Distance = child2.distance(distanceStyle, x, y, z);
+ // System.out.println("In PathNode.distance(), returning child1 distance = "+child1Distance+"
+ // and child2 distance = "+child2Distance);
+ return Math.min(child1Distance, child2Distance);
+ }
+
+ @Override
+ public double nearestDistance(
+ 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.nearestDistance(distanceStyle, x, y, z),
+ child2.nearestDistance(distanceStyle, x, y, z));
+ }
+
@Override
public double fullPathDistance(final DistanceStyle distanceStyle) {
return distanceStyle.aggregateDistances(
@@ -809,6 +747,11 @@ class GeoStandardPath extends GeoBasePath {
child2.getBounds(bounds);
}
}
+
+ @Override
+ public String toString() {
+ return "PathNode (" + child1 + ") (" + child2 + ")";
+ }
}
/**
@@ -827,9 +770,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 +780,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;
}
@@ -857,14 +798,36 @@ class GeoStandardPath extends GeoBasePath {
@Override
public double getStartingDistance(DistanceStyle distanceStyle) {
if (previous == null) {
- return 0.0;
+ return distanceStyle.toAggregationForm(0.0);
+ }
+ return distanceStyle.aggregateDistances(
+ previous.getStartingDistance(distanceStyle), previous.fullPathDistance(distanceStyle));
+ }
+
+ @Override
+ public double distance(
+ final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ if (!isWithin(x, y, z)) {
+ return Double.POSITIVE_INFINITY;
+ }
+ final double startingDistance = getStartingDistance(distanceStyle);
+ final double pathDistance = pathDistance(distanceStyle, x, y, z);
+ return distanceStyle.fromAggregationForm(
+ distanceStyle.aggregateDistances(startingDistance, pathDistance));
+ }
+
+ @Override
+ public double nearestDistance(
+ final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ if (!isWithin(x, y, z)) {
+ return Double.POSITIVE_INFINITY;
}
- return previous.getStartingDistance(distanceStyle);
+ return distanceStyle.fromAggregationForm(getStartingDistance(distanceStyle));
}
@Override
public double fullPathDistance(final DistanceStyle distanceStyle) {
- return 0.0;
+ return distanceStyle.toAggregationForm(0.0);
}
@Override
@@ -890,12 +853,18 @@ class GeoStandardPath extends GeoBasePath {
@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 distanceStyle.toAggregationForm(0.0);
}
@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 distanceStyle.computeDistance(this.point, x, y, z);
}
@@ -918,6 +887,7 @@ class GeoStandardPath extends GeoBasePath {
@Override
public void getBounds(final Bounds bounds) {
+ super.getBounds(bounds);
bounds.addPoint(point);
}
@@ -937,7 +907,7 @@ class GeoStandardPath extends GeoBasePath {
@Override
public String toString() {
- return point.toString();
+ return "SegmentEndpoint (" + point + ")";
}
}
@@ -948,6 +918,21 @@ class GeoStandardPath extends GeoBasePath {
/** No notable points from the circle itself */
protected static final GeoPoint[] circlePoints = new GeoPoint[0];
+ public CircleSegmentEndpoint(
+ final PlanetModel planetModel,
+ final PathComponent previous,
+ final GeoPoint point,
+ final GeoPoint upperPoint,
+ final GeoPoint lowerPoint) {
+ super(planetModel, previous, point);
+ circlePlane = SidedPlane.constructSidedPlaneFromTwoPoints(point, upperPoint, lowerPoint);
+ }
+
+ // Note: we need a method of constructing a plane as follows:
+ // (1) We start with two points (edge points of the adjoining segment)
+ // (2) We construct a plane with those two points through the center of the earth
+ // (3) We construct a plane perpendicular to the first plane that goes through the two points.
+ // TBD
/**
* Constructor for case (1). Generate a simple circle cutoff plane.
*
@@ -1012,6 +997,11 @@ class GeoStandardPath extends GeoBasePath {
super.getBounds(bounds);
bounds.addPlane(planetModel, circlePlane);
}
+
+ @Override
+ public String toString() {
+ return "CircleSegmentEndpoint: " + super.toString();
+ }
}
/** Endpoint that's a single circle with cutoff(s). */
@@ -1022,6 +1012,8 @@ class GeoStandardPath extends GeoBasePath {
/** Notable points for this segment endpoint */
private final GeoPoint[] notablePoints;
+ private final SidedPlane cutoffPlane;
+
/**
* Constructor for case (2). Generate an endpoint, given a single cutoff plane plus upper and
* lower edge points.
@@ -1041,83 +1033,20 @@ class GeoStandardPath extends GeoBasePath {
final SidedPlane cutoffPlane,
final GeoPoint topEdgePoint,
final GeoPoint bottomEdgePoint) {
- super(planetModel, previous, point, cutoffPlane, topEdgePoint, bottomEdgePoint);
- this.cutoffPlanes = new Membership[] {new SidedPlane(cutoffPlane)};
- this.notablePoints = new GeoPoint[] {topEdgePoint, bottomEdgePoint};
- }
-
- /**
- * Constructor for case (2.5). Generate an endpoint, given two cutoff planes plus upper and
- * lower edge points.
- *
- * @param planetModel is the planet model.
- * @param point is the center.
- * @param cutoffPlane1 is one adjoining path segment cutoff plane.
- * @param cutoffPlane2 is another adjoining path segment cutoff plane.
- * @param topEdgePoint is a point on the cutoffPlane that should be also on the circle plane.
- * @param bottomEdgePoint is another point on the cutoffPlane that should be also on the circle
- * plane.
- */
- 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, previous, point, cutoffPlane1, topEdgePoint, bottomEdgePoint);
- this.cutoffPlanes =
- new Membership[] {new SidedPlane(cutoffPlane1), new SidedPlane(cutoffPlane2)};
+ super(planetModel, previous, point, topEdgePoint, bottomEdgePoint);
+ this.cutoffPlane = new SidedPlane(cutoffPlane);
+ this.cutoffPlanes = new Membership[] {cutoffPlane};
this.notablePoints = new GeoPoint[] {topEdgePoint, bottomEdgePoint};
}
@Override
public boolean isWithin(final Vector point) {
- if (!super.isWithin(point)) {
- return false;
- }
- for (final Membership m : cutoffPlanes) {
- if (!m.isWithin(point)) {
- return false;
- }
- }
- return true;
+ return cutoffPlane.isWithin(point) && super.isWithin(point);
}
@Override
public boolean isWithin(final double x, final double y, final double z) {
- if (!super.isWithin(x, y, z)) {
- return false;
- }
- for (final Membership m : cutoffPlanes) {
- if (!m.isWithin(x, y, z)) {
- return false;
- }
- }
- return true;
- }
-
- @Override
- public double nearestPathDistance(
- final DistanceStyle distanceStyle, final double x, final double y, final double z) {
- for (final Membership m : cutoffPlanes) {
- if (!m.isWithin(x, y, z)) {
- return Double.POSITIVE_INFINITY;
- }
- }
- return super.nearestPathDistance(distanceStyle, x, y, z);
- }
-
- @Override
- public double pathCenterDistance(
- final DistanceStyle distanceStyle, final double x, final double y, final double z) {
- for (final Membership m : cutoffPlanes) {
- if (!m.isWithin(x, y, z)) {
- return Double.POSITIVE_INFINITY;
- }
- }
- return super.pathCenterDistance(distanceStyle, x, y, z);
+ return cutoffPlane.isWithin(x, y, z) && super.isWithin(x, y, z);
}
@Override
@@ -1131,16 +1060,30 @@ class GeoStandardPath extends GeoBasePath {
public boolean intersects(final GeoShape geoShape) {
return geoShape.intersects(circlePlane, this.notablePoints, this.cutoffPlanes);
}
+
+ @Override
+ public void getBounds(final Bounds bounds) {
+ super.getBounds(bounds);
+ bounds.addPlane(planetModel, circlePlane, cutoffPlane);
+ bounds.addPlane(planetModel, cutoffPlane, circlePlane);
+ bounds.addIntersection(planetModel, circlePlane, cutoffPlane);
+ bounds.addIntersection(planetModel, cutoffPlane, circlePlane);
+ }
+
+ @Override
+ public String toString() {
+ return "CutoffSingleCircleSegmentEndpoint: " + super.toString();
+ }
}
/**
* Endpoint that's a dual circle with cutoff(s). This SegmentEndpoint is used when we have two
- * adjoining segments that are not colinear, and when we are on a non-spherical world. (1) We
- * construct two circles. Each circle uses the two segment endpoints for one of the two segments,
- * plus the one segment endpoint that is on the other side of the segment's cutoff plane. (2)
- * isWithin() is computed using both circles, using just the portion that is within both segments'
- * cutoff planes. If either matches, the point is included. (3) intersects() is computed using
- * both circles, with similar cutoffs. (4) bounds() uses both circles too.
+ * adjoining segments. (1) We construct two circles. Each circle uses the two segment endpoints
+ * for one of the two segments, plus the one segment endpoint that is on the other side of the
+ * segment's cutoff plane. (2) isWithin() is computed using both circles, using just the portion
+ * that is within both segments' cutoff planes. If either matches, the point is included. (3)
+ * intersects() is computed using both circles, with similar cutoffs. (4) bounds() uses both
+ * circles too.
*/
private static class CutoffDualCircleSegmentEndpoint extends BaseSegmentEndpoint {
@@ -1155,6 +1098,9 @@ class GeoStandardPath extends GeoBasePath {
/** Both cutoff planes are included here */
protected final Membership[] cutoffPlanes;
+ protected final SidedPlane boundaryPlane1;
+ protected final SidedPlane boundaryPlane2;
+
public CutoffDualCircleSegmentEndpoint(
final PlanetModel planetModel,
final PathComponent previous,
@@ -1180,8 +1126,8 @@ class GeoStandardPath extends GeoBasePath {
point, prevURHC, prevLRHC, currentLLHC);
notablePoints1 = new GeoPoint[] {prevURHC, prevLRHC, currentLLHC};
} else {
- throw new IllegalArgumentException(
- "Constructing CutoffDualCircleSegmentEndpoint with colinear segments");
+ circlePlane1 = SidedPlane.constructSidedPlaneFromTwoPoints(point, prevURHC, prevLRHC);
+ notablePoints1 = new GeoPoint[] {prevURHC, prevLRHC};
}
// Second plane consists of current endpoints plus one of the prev endpoints (the one past the
// end of the current segment)
@@ -1196,11 +1142,12 @@ class GeoStandardPath extends GeoBasePath {
point, currentULHC, currentLLHC, prevLRHC);
notablePoints2 = new GeoPoint[] {currentULHC, currentLLHC, prevLRHC};
} else {
- throw new IllegalArgumentException(
- "Constructing CutoffDualCircleSegmentEndpoint with colinear segments");
+ circlePlane2 = SidedPlane.constructSidedPlaneFromTwoPoints(point, currentULHC, currentLLHC);
+ notablePoints2 = new GeoPoint[] {currentULHC, currentLLHC};
}
- this.cutoffPlanes =
- new Membership[] {new SidedPlane(prevCutoffPlane), new SidedPlane(nextCutoffPlane)};
+ this.boundaryPlane1 = new SidedPlane(prevCutoffPlane);
+ this.boundaryPlane2 = new SidedPlane(nextCutoffPlane);
+ this.cutoffPlanes = new Membership[] {boundaryPlane1, boundaryPlane2};
}
@Override
@@ -1223,28 +1170,6 @@ class GeoStandardPath extends GeoBasePath {
return circlePlane1.isWithin(x, y, z) || circlePlane2.isWithin(x, y, z);
}
- @Override
- public double nearestPathDistance(
- final DistanceStyle distanceStyle, final double x, final double y, final double z) {
- for (final Membership m : cutoffPlanes) {
- if (!m.isWithin(x, y, z)) {
- return Double.POSITIVE_INFINITY;
- }
- }
- return super.nearestPathDistance(distanceStyle, x, y, z);
- }
-
- @Override
- public double pathCenterDistance(
- final DistanceStyle distanceStyle, final double x, final double y, final double z) {
- for (final Membership m : cutoffPlanes) {
- if (!m.isWithin(x, y, z)) {
- return Double.POSITIVE_INFINITY;
- }
- }
- return super.pathCenterDistance(distanceStyle, x, y, z);
- }
-
@Override
public boolean intersects(
final Plane p, final GeoPoint[] notablePoints, final Membership[] bounds) {
@@ -1263,15 +1188,28 @@ class GeoStandardPath extends GeoBasePath {
@Override
public void getBounds(final Bounds bounds) {
super.getBounds(bounds);
- bounds.addPlane(planetModel, circlePlane1);
- bounds.addPlane(planetModel, circlePlane2);
+ // System.out.println("Computing bounds for circlePlane1="+circlePlane1);
+ bounds.addPlane(planetModel, circlePlane1, boundaryPlane1, boundaryPlane2);
+ // System.out.println("Computing bounds for circlePlane2="+circlePlane2);
+ bounds.addPlane(planetModel, circlePlane2, boundaryPlane1, boundaryPlane2);
+ bounds.addPlane(planetModel, boundaryPlane1, circlePlane1, boundaryPlane2);
+ bounds.addPlane(planetModel, boundaryPlane1, circlePlane2, boundaryPlane2);
+ bounds.addPlane(planetModel, boundaryPlane2, circlePlane1, boundaryPlane1);
+ bounds.addPlane(planetModel, boundaryPlane2, circlePlane2, boundaryPlane1);
+ bounds.addIntersection(planetModel, circlePlane1, boundaryPlane1, boundaryPlane2);
+ bounds.addIntersection(planetModel, circlePlane1, boundaryPlane2, boundaryPlane1);
+ bounds.addIntersection(planetModel, circlePlane2, boundaryPlane1, boundaryPlane2);
+ bounds.addIntersection(planetModel, circlePlane2, boundaryPlane2, boundaryPlane1);
+ }
+
+ @Override
+ public String toString() {
+ return "CutoffDualCircleSegmentEndpoint: " + super.toString();
}
}
/** 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 +1257,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;
@@ -1409,6 +1347,31 @@ class GeoStandardPath extends GeoBasePath {
return dist.doubleValue();
}
+ @Override
+ public double distance(
+ final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ if (!isWithin(x, y, z)) {
+ return Double.POSITIVE_INFINITY;
+ }
+ final double startingDistance = getStartingDistance(distanceStyle);
+ final double pathDistance = pathDistance(distanceStyle, x, y, z);
+ // System.out.println("In PathSegment distance(), startingDistance = "+startingDistance+"
+ // pathDistance = "+pathDistance);
+ return distanceStyle.fromAggregationForm(
+ distanceStyle.aggregateDistances(startingDistance, pathDistance));
+ }
+
+ @Override
+ public double nearestDistance(
+ final DistanceStyle distanceStyle, final double x, final double y, final double z) {
+ if (!isWithin(x, y, z)) {
+ return Double.POSITIVE_INFINITY;
+ }
+ return distanceStyle.fromAggregationForm(
+ distanceStyle.aggregateDistances(
+ getStartingDistance(distanceStyle), nearestPathDistance(distanceStyle, x, y, z)));
+ }
+
private double computeStartingDistance(final DistanceStyle distanceStyle) {
if (previous == null) {
return 0.0;
@@ -1472,10 +1435,6 @@ class GeoStandardPath extends GeoBasePath {
// 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;
- }
// (1) Compute normalizedPerpPlane. If degenerate, then there is no such plane, which means
// that the point given is insufficient to distinguish between a family of such planes.
// This can happen only if the point is one of the "poles", imagining the normalized plane
@@ -1724,6 +1683,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 +1741,11 @@ class GeoStandardPath extends GeoBasePath {
startCutoffPlane,
lowerConnectingPlane);
}
+
+ @Override
+ public String toString() {
+ return "PathSegment (" + ULHC + ", " + URHC + ", " + LRHC + ", " + LLHC + ")";
+ }
}
private static class TreeBuilder {
@@ -1796,7 +1761,7 @@ class GeoStandardPath extends GeoBasePath {
componentStack.add(component);
depthStack.add(0);
while (depthStack.size() >= 2) {
- if (depthStack.get(depthStack.size() - 1).equals(depthStack.get(depthStack.size() - 2))) {
+ if (depthStack.get(depthStack.size() - 1) == depthStack.get(depthStack.size() - 2)) {
mergeTop();
} else {
break;
@@ -1816,9 +1781,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));
}
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Plane.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Plane.java
index 80a66d476a1..e13fa2587fd 100755
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Plane.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Plane.java
@@ -126,6 +126,161 @@ public class Plane extends Vector {
: Math.nextDown(basePlane.D - MINIMUM_RESOLUTION));
}
+ /**
+ * Given two points, construct a plane that goes through them and the origin. Then, find a plane
+ * that is perpendicular to that which also goes through the original two points. This is useful
+ * for building path endpoints on worlds that can be ellipsoids.
+ *
+ * @param M is the first vector (point)
+ * @param N is the second vector (point)
+ * @return the plane, or throw an exception if the points given cannot be turned into the plane
+ * desired.
+ */
+ public static Plane constructPerpendicularCenterPlaneTwoPoints(final Vector M, final Vector N) {
+ final Plane centerPlane = new Plane(M, N);
+
+ // First plane:
+ // A0x + B0y + C0z = 0 (D0 = 0)
+
+ final double A0 = centerPlane.x;
+ final double B0 = centerPlane.y;
+ final double C0 = centerPlane.z;
+
+ // Second plane equations:
+ // A1Mx + B1My + C1Mz + D1 = 0
+ // A1Nx + B1Ny + C1Nz + D1 = 0
+ // simplifying:
+ // A1(Mx-Nx) + B1(My-Ny) + C1(Mz-Nz) = 0
+ // A0*A1 + B0*B1 + C0*C1 = 0
+ // A1^2 + B1^2 + C1^2 = 1
+
+ // Basic strategy: Pick a variable and set it to 1.
+ // e.g. A1 = 1.
+ // Then:
+ // B1 = (-C1(Mz-Nz) - (Mx-Nx)) / (My-Ny)
+ // A0 + B0 * (-C1(Mz-Nz) - (Mx-Nx)) / (My-Ny) + C0 * C1 = 0
+ // C1 * ((-B0 * (Mz-Nz) - (Mx-Nx))/ (My-Ny) + C0) = -A0
+ // C1 = -A0 / ((-B0 * (Mz-Nz) - (Mx-Nx))/ (My-Ny) + C0)
+ // and B1 can be found from above. Then normalized.
+
+ // So the variable we pick has the greatest delta between M and N, but the basic process is
+ // identical.
+ // To find D1 after A1, B1, C1 are found, just plug in one of the points, either M or N.
+
+ final double xDiff = M.x - N.x;
+ final double yDiff = M.y - N.y;
+ final double zDiff = M.z - N.z;
+
+ if (xDiff * xDiff + yDiff * yDiff + zDiff * zDiff < MINIMUM_RESOLUTION_SQUARED) {
+ throw new IllegalArgumentException("Chosen points are numerically identical");
+ }
+
+ final double A1;
+ final double B1;
+ final double C1;
+ // Pick the equations we want to use based on the denominators we will encounter.
+ // There are two levels to this. The first level involves a denominator choice based on
+ // which coefficient we set to 1. The second level involves a denominator choice between
+ // diffs in the other two dimensions.
+ final double A1choice = (C0 * yDiff - B0 * zDiff);
+ final double B1choice = (C0 * xDiff - A0 * zDiff);
+ final double C1choice = (B0 * xDiff - A0 * yDiff);
+ if (Math.abs(A1choice) >= Math.abs(B1choice) && Math.abs(A1choice) >= Math.abs(C1choice)) {
+ // System.out.println("Choosing A1=1");
+ // A1 = 1.0
+ // 1.0 * xDiff + B1 * yDiff + C1 * zDiff = 0
+ // B1 * yDiff = -C1 * zDiff - 1.0 * xDiff
+ // B1 = (-C1 * zDiff - xDiff) / yDiff
+ // A0 + B0 * (-C1 * zDiff - xDiff) / yDiff + C0 * C1 = 0
+ // A0 - B0 * C1 * zDiff / yDiff - B0 * xDiff / yDiff + C0 * C1 = 0
+ // A0 * yDiff - B0 * C1 * zDiff - B0 * xDiff + C0 * C1 * yDiff = 0
+ // C1 * C0 * yDiff - C1 * B0 * zDiff = B0 * xDiff - A0 * yDiff
+ // C1 = (B0 * xDiff - A0 * yDiff) / (C0 * yDiff - B0 * zDiff);
+ A1 = 1.0;
+ if (Math.abs(yDiff) >= Math.abs(zDiff)) {
+ // A1choice is C-B, so numerator is B-A
+ C1 = (B0 * xDiff - A0 * yDiff) / A1choice;
+ B1 = (-C1 * zDiff - xDiff) / yDiff;
+ } else {
+ // A1choice is C-B, so numerator is A-C
+ // 1.0 * xDiff + B1 * yDiff + C1 * zDiff = 0
+ // C1 * zDiff = -B1 * yDiff - 1.0 * xDiff
+ // C1 = (-B1 * yDiff - xDiff) / zDiff
+ // A0 + B0 * B1 - C0 * (B1 * yDiff - xDiff) / zDiff = 0
+ // A0 * zDiff + B0 * B1 * zDiff - C0 * B1 * yDiff - C0 * xDiff = 0
+ // B1 * B0 * zDiff - B1 * C0 * yDiff = C0 * xDiff - A0 * zDiff
+ // B1 = (C0 * xDiff - A0 * zDiff) / (B0 * zDiff - C0 * yDiff);
+ B1 = (A0 * zDiff - C0 * xDiff) / A1choice;
+ C1 = (-B1 * yDiff - xDiff) / zDiff;
+ }
+ } else if (Math.abs(B1choice) >= Math.abs(A1choice)
+ && Math.abs(B1choice) >= Math.abs(C1choice)) {
+ // System.out.println("Choosing B1=1");
+ // Pick B1 = 1.0
+ // A1 * xDiff + 1.0 * yDiff + C1 * zDiff = 0
+ // A1 * xDiff = -C1 * zDiff - 1.0 * yDiff
+ // A1 = (-C1 * zDiff - yDiff) / xDiff
+ // A0 * (-C1 * zDiff - yDiff) / xDiff + B0 * 1.0 + C0 * C1 = 0
+ // B0 + C0 * C1 - A0 * C1 * zDiff / xDiff - A0 * yDiff / xDiff = 0
+ // B0 * xDiff - A0 * C1 * zDiff - A0 * yDiff + C0 * C1 * xDiff = 0
+ // C1 * C0 * xDiff - C1 * A0 * zDiff = A0 * yDiff - B0 * xDiff
+ // C1 = (A0 * yDiff - B0 * xDiff) / (C0 * xDiff - A0 * zDiff);
+ B1 = 1.0;
+ if (Math.abs(xDiff) >= Math.abs(zDiff)) {
+ // B1choice is C-A, so numerator is A-B
+ C1 = (A0 * yDiff - B0 * xDiff) / B1choice;
+ A1 = (-C1 * zDiff - yDiff) / xDiff;
+ } else {
+ // B1choice is C-A, so numerator is B-C
+ A1 = (B0 * xDiff - C0 * yDiff) / B1choice;
+ C1 = (-A1 * xDiff - yDiff) / zDiff;
+ }
+ } else if (Math.abs(C1choice) >= Math.abs(A1choice)
+ && Math.abs(C1choice) >= Math.abs(B1choice)) {
+ // System.out.println("Choosing C1=1");
+ // Pick C1 = 1.0
+ // A1 * xDiff + B1 * yDiff + 1.0 * zDiff = 0
+ // A1 * xDiff = -B1 * yDiff - 1.0 * zDiff
+ // A1 = (-B1 * yDiff - zDiff) / xDiff
+ // A0 * (-B1 * yDiff - zDiff) / xDiff + B0 * B1 + C0 * 1.0 = 0
+ // -B1 * A0 * yDiff - A0 * zDiff + B1 * B0 * xDiff + C0 * xDiff = 0
+ // B1 * B0 * xDiff - B1 * A0 * yDiff = A0 * zDiff - C0 * xDiff
+ // B1 = (A0 * zDiff - C0 * xDiff) / (B0 * xDiff - A0 * yDiff)
+ C1 = 1.0;
+ if (Math.abs(xDiff) >= Math.abs(yDiff)) {
+ // C1choice is B - A, so numerator is C-B
+ B1 = (A0 * zDiff - C0 * xDiff) / C1choice;
+ A1 = (-B1 * yDiff - zDiff) / xDiff;
+ } else {
+ // A1 * xDiff + B1 * yDiff + 1.0 * zDiff = 0
+ // A1 * xDiff = -B1 * yDiff - 1.0 * zDiff
+ // B1 = (-A1 * xDiff - zDiff) / yDiff
+ // A0 * A1 + B0 * (-A1 * xDiff - zDiff) / yDiff + C0 * 1.0 = 0
+ // A1 * A0 * yDiff - A1 * B0 * xDiff - B0 * zDiff + C0 * yDiff = 0
+ // A1 * A0 * yDiff - A1 * B0 * xDiff = B0 * zDiff - C0 * yDiff
+ // A1 = (B0 * zDiff - C0 * yDiff) / (A0 * yDiff - A1 * B0 * xDiff)
+ A1 = (C0 * yDiff - B0 * zDiff) / C1choice;
+ B1 = (-A1 * xDiff - zDiff) / yDiff;
+ }
+
+ } else {
+ throw new IllegalArgumentException("Equation appears to be unsolveable");
+ }
+
+ // Normalize the vector
+ final double normFactor = 1.0 / Math.sqrt(A1 * A1 + B1 * B1 + C1 * C1);
+ final Vector v = new Vector(A1 * normFactor, B1 * normFactor, C1 * normFactor);
+ final Plane rval = new Plane(v, -(v.x * M.x + v.y * M.y + v.z * M.z));
+ assert rval.evaluateIsZero(N);
+ // System.out.println(
+ // "M and N both on plane! Dotproduct with centerplane = "
+ // + (rval.x * centerPlane.x + rval.y * centerPlane.y + rval.z * centerPlane.z));
+
+ assert Math.abs(rval.x * centerPlane.x + rval.y * centerPlane.y + rval.z * centerPlane.z)
+ < MINIMUM_RESOLUTION;
+ return rval;
+ }
+
/**
* Construct the most accurate normalized plane through an x-y point and including the Z axis. If
* none of the points can determine the plane, return null.
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/SidedPlane.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/SidedPlane.java
index 5c6d879c1aa..cee6aa6c5ab 100755
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/SidedPlane.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/SidedPlane.java
@@ -227,6 +227,16 @@ public class SidedPlane extends Plane implements Membership {
}
}
+ /**
+ * Construct sided plane from two points. This first constructs a plane that goes through the
+ * center, then finds one that is perpendicular that goes through the same two points.
+ */
+ public static SidedPlane constructSidedPlaneFromTwoPoints(
+ final Vector insidePoint, final Vector upperPoint, final Vector lowerPoint) {
+ final Plane plane = Plane.constructPerpendicularCenterPlaneTwoPoints(upperPoint, lowerPoint);
+ return new SidedPlane(insidePoint, plane.x, plane.y, plane.z, plane.D);
+ }
+
/** Construct a sided plane from three points. */
public static SidedPlane constructNormalizedThreePointSidedPlane(
final Vector insidePoint, final Vector point1, final Vector point2, final Vector point3) {
diff --git a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/TestGeoPath.java b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/TestGeoPath.java
index 965d860cf7f..72d86c07b58 100755
--- a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/TestGeoPath.java
+++ b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/TestGeoPath.java
@@ -40,6 +40,7 @@ public class TestGeoPath extends LuceneTestCase {
gp = new GeoPoint(PlanetModel.SPHERE, -0.15, 0.05);
assertEquals(Double.POSITIVE_INFINITY, p.computeDistance(DistanceStyle.ARC, gp), 0.000001);
gp = new GeoPoint(PlanetModel.SPHERE, 0.0, 0.25);
+ System.out.println("Calling problematic computeDistance...");
assertEquals(0.20 + 0.05, p.computeDistance(DistanceStyle.ARC, gp), 0.000001);
gp = new GeoPoint(PlanetModel.SPHERE, 0.0, -0.05);
assertEquals(0.0 + 0.05, p.computeDistance(DistanceStyle.ARC, gp), 0.000001);