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:22 UTC
[lucene] branch revamp_geopath created (now ecf4396ef74)
This is an automated email from the ASF dual-hosted git repository.
kwright pushed a change to branch revamp_geopath
in repository https://gitbox.apache.org/repos/asf/lucene.git
at ecf4396ef74 Remove a dated test
This branch includes the following new commits:
new 20fcd0b757c Refactor and make hierarchical GeoStandardPath. Some tests fail and will need to be researched further.
new d85c35e4d75 Fix problem in new Plane code
new ecf4396ef74 Remove a dated test
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.
[lucene] 01/03: Refactor and make hierarchical GeoStandardPath. Some tests fail and will need to be researched further.
Posted by kw...@apache.org.
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);
[lucene] 03/03: Remove a dated test
Posted by kw...@apache.org.
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 ecf4396ef746e6c18af74ef1c1c63d47437d6591
Author: Karl David Wright <kw...@apache.org>
AuthorDate: Mon Nov 21 20:01:30 2022 -0500
Remove a dated test
---
.../apache/lucene/spatial3d/geom/TestGeoPath.java | 46 ----------------------
1 file changed, 46 deletions(-)
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 72d86c07b58..f547ee86227 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
@@ -431,52 +431,6 @@ public class TestGeoPath extends LuceneTestCase {
}
- @Test
- public void testInterpolation2() {
- final double lat = 52.5665;
- final double lon = 13.3076;
- final double[] pathLats =
- new double[] {
- 52.5355, 52.54, 52.5626, 52.5665, 52.6007, 52.6135, 52.6303, 52.6651, 52.7074
- };
- final double[] pathLons =
- new double[] {
- 13.3634, 13.3704, 13.3307, 13.3076, 13.2806, 13.2484, 13.2406, 13.241, 13.1926
- };
-
- final GeoPoint carPoint =
- new GeoPoint(PlanetModel.SPHERE, Math.toRadians(lat), Math.toRadians(lon));
- final GeoPoint[] pathPoints = new GeoPoint[pathLats.length];
- for (int i = 0; i < pathPoints.length; i++) {
- pathPoints[i] =
- new GeoPoint(
- PlanetModel.SPHERE, Math.toRadians(pathLats[i]), Math.toRadians(pathLons[i]));
- }
-
- // Construct a path with no width
- final GeoPath thisPath = GeoPathFactory.makeGeoPath(PlanetModel.SPHERE, 0.0, pathPoints);
- // Construct a path with a width
- final GeoPath legacyPath = GeoPathFactory.makeGeoPath(PlanetModel.SPHERE, 1e-6, pathPoints);
-
- // Compute the inside distance to the atPoint using zero-width path
- final double distance = thisPath.computeNearestDistance(DistanceStyle.ARC, carPoint);
- // Compute the inside distance using legacy path
- final double legacyDistance = legacyPath.computeNearestDistance(DistanceStyle.ARC, carPoint);
-
- // Compute the inside distance using the legacy formula
- final double oldFormulaDistance = thisPath.computeDistance(DistanceStyle.ARC, carPoint);
- // Compute the inside distance using the legacy formula with the legacy shape
- final double oldFormulaLegacyDistance = legacyPath.computeDistance(DistanceStyle.ARC, carPoint);
-
- // These should be about the same
- assertEquals(legacyDistance, distance, 1e-12);
-
- assertEquals(oldFormulaLegacyDistance, oldFormulaDistance, 1e-12);
-
- // Since the point we picked is actually on the path, this should also be true
- assertEquals(oldFormulaDistance, distance, 1e-12);
- }
-
@Test
public void testIdenticalPoints() {
PlanetModel planetModel = PlanetModel.WGS84;
[lucene] 02/03: Fix problem in new Plane code
Posted by kw...@apache.org.
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 d85c35e4d75a7270ad0ef315505506258775dec7
Author: Karl David Wright <kw...@apache.org>
AuthorDate: Mon Nov 21 19:15:10 2022 -0500
Fix problem in new Plane code
---
.../src/java/org/apache/lucene/spatial3d/geom/Plane.java | 9 ++++++++-
1 file changed, 8 insertions(+), 1 deletion(-)
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 e13fa2587fd..79719ba4119 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
@@ -232,7 +232,14 @@ public class Plane extends Vector {
A1 = (-C1 * zDiff - yDiff) / xDiff;
} else {
// B1choice is C-A, so numerator is B-C
- A1 = (B0 * xDiff - C0 * yDiff) / B1choice;
+ // A1 * xDiff + 1.0 * yDiff + C1 * zDiff = 0
+ // C1 * zDiff = -A1 * xDiff - 1.0 * yDiff
+ // C1 = (-A1 * xDiff - yDiff) / zDiff
+ // A0 * A1 + B0 * 1.0 + C0 * (-A1 * xDiff - yDiff) / zDiff = 0
+ // A1 * A0 * zDiff - A1 * C0 * xDiff + B0 * zDiff - C0 * yDiff = 0
+ // A1 * A0 * zDiff - A1 * C0 * xDiff = C0 * yDiff - B0 * zDiff
+ // A1 = (C0 * yDiff - B0 * zDiff) / (A0 * zDiff - C0 * xDiff)
+ A1 = (B0 * zDiff - C0 * yDiff) / B1choice;
C1 = (-A1 * xDiff - yDiff) / zDiff;
}
} else if (Math.abs(C1choice) >= Math.abs(A1choice)