Fix for 11883.
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConvexPolygon.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConvexPolygon.java
index 5d8363d..eed5679 100755
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConvexPolygon.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConvexPolygon.java
@@ -42,14 +42,16 @@
/** A list of edges */
protected SidedPlane[] edges = null;
+ /** A list of edge starting bounding planes */
+ protected SidedPlane[] startBounds = null;
+ /** A list of edge ending bounding planes */
+ protected SidedPlane[] endBounds = null;
/** The set of notable points for each edge */
protected GeoPoint[][] notableEdgePoints = null;
/** A point which is on the boundary of the polygon */
protected GeoPoint[] edgePoints = null;
/** Set to true when the polygon is complete */
protected boolean isDone = false;
- /** A bounds object for each sided plane */
- protected Map<SidedPlane, Membership> eitherBounds = null;
/** Map from edge to its previous non-coplanar brother */
protected Map<SidedPlane, SidedPlane> prevBrotherMap = null;
/** Map from edge to its next non-coplanar brother */
@@ -213,6 +215,8 @@
// Time to construct the planes. If the polygon is truly convex, then any adjacent point
// to a segment can provide an interior measurement.
edges = new SidedPlane[points.size()];
+ startBounds = new SidedPlane[points.size()];
+ endBounds = new SidedPlane[points.size()];
notableEdgePoints = new GeoPoint[points.size()][];
for (int i = 0; i < points.size(); i++) {
@@ -235,11 +239,12 @@
final GeoPoint check = points.get(endPointIndex);
final SidedPlane sp = new SidedPlane(check, start, end);
edges[i] = sp;
+ startBounds[i] = SidedPlane.constructSidedPlaneFromOnePoint(end, sp, start);
+ endBounds[i] = SidedPlane.constructSidedPlaneFromOnePoint(start, sp, end);
notableEdgePoints[i] = new GeoPoint[] {start, end};
}
// For each edge, create a bounds object.
- eitherBounds = CollectionUtil.newHashMap(edges.length);
prevBrotherMap = CollectionUtil.newHashMap(edges.length);
nextBrotherMap = CollectionUtil.newHashMap(edges.length);
for (int edgeIndex = 0; edgeIndex < edges.length; edgeIndex++) {
@@ -273,7 +278,6 @@
"Convex polygon has a side that is more than 180 degrees");
}
}
- eitherBounds.put(edge, new EitherBound(edges[bound1Index], edges[bound2Index]));
// When we are done with this cycle, we'll need to build the intersection bound for each edge
// and its brother. For now, keep track of the relationships.
nextBrotherMap.put(edge, edges[bound1Index]);
@@ -411,7 +415,13 @@
// System.err.println("Checking convex edge " + edge
// + " for intersection against plane " + p);
if (edge.intersects(
- planetModel, p, notablePoints, points, bounds, eitherBounds.get(edge))) {
+ planetModel,
+ p,
+ notablePoints,
+ points,
+ bounds,
+ startBounds[edgeIndex],
+ endBounds[edgeIndex])) {
// System.err.println(" intersects!");
return true;
}
@@ -436,7 +446,7 @@
final SidedPlane edge = edges[edgeIndex];
final GeoPoint[] points = this.notableEdgePoints[edgeIndex];
if (!isInternalEdges.get(edgeIndex)) {
- if (shape.intersects(edge, points, eitherBounds.get(edge))) {
+ if (shape.intersects(edge, points, startBounds[edgeIndex], endBounds[edgeIndex])) {
return true;
}
}
@@ -451,39 +461,6 @@
return false;
}
- /** A membership implementation representing polygon edges that must apply. */
- protected static class EitherBound implements Membership {
-
- protected final SidedPlane sideBound1;
- protected final SidedPlane sideBound2;
-
- /**
- * Constructor.
- *
- * @param sideBound1 is the first side bound.
- * @param sideBound2 is the second side bound.
- */
- public EitherBound(final SidedPlane sideBound1, final SidedPlane sideBound2) {
- this.sideBound1 = sideBound1;
- this.sideBound2 = sideBound2;
- }
-
- @Override
- public boolean isWithin(final Vector v) {
- return sideBound1.isWithin(v) && sideBound2.isWithin(v);
- }
-
- @Override
- public boolean isWithin(final double x, final double y, final double z) {
- return sideBound1.isWithin(x, y, z) && sideBound2.isWithin(x, y, z);
- }
-
- @Override
- public String toString() {
- return "(" + sideBound1 + "," + sideBound2 + ")";
- }
- }
-
@Override
public void getBounds(Bounds bounds) {
// Because of holes, we don't want to use superclass method
@@ -512,8 +489,9 @@
}
// Add planes with membership.
- for (final SidedPlane edge : edges) {
- bounds.addPlane(planetModel, edge, eitherBounds.get(edge));
+ for (int edgeIndex = 0; edgeIndex < edges.length; edgeIndex++) {
+ final SidedPlane edge = edges[edgeIndex];
+ bounds.addPlane(planetModel, edge, startBounds[edgeIndex], endBounds[edgeIndex]);
final SidedPlane nextEdge = nextBrotherMap.get(edge);
bounds.addIntersection(
planetModel, edge, nextEdge, prevBrotherMap.get(edge), nextBrotherMap.get(nextEdge));
@@ -530,10 +508,11 @@
minimumDistance = newDist;
}
}
- for (final SidedPlane edgePlane : edges) {
+ for (int edgeIndex = 0; edgeIndex < edges.length; edgeIndex++) {
+ final SidedPlane edgePlane = edges[edgeIndex];
final double newDist =
distanceStyle.computeDistance(
- planetModel, edgePlane, x, y, z, eitherBounds.get(edgePlane));
+ planetModel, edgePlane, x, y, z, startBounds[edgeIndex], endBounds[edgeIndex]);
if (newDist < minimumDistance) {
minimumDistance = newDist;
}
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Membership.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Membership.java
index 0cf6ff0..5d88950 100755
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Membership.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Membership.java
@@ -42,5 +42,4 @@
* @return true if the point is within this shape
*/
public boolean isWithin(final double x, final double y, final double z);
-
}
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 ce0fce9..f451a22 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
@@ -127,9 +127,9 @@
}
/**
- *
* Given a plane and one point that is on that plane, find a perpendicular plane that goes through
* both the origin and the point.
+ *
* @param plane is the original plane
* @param M is the point on that plane
* @return a plane that goes through M, the origin, and is perpendicular to the original plane
@@ -138,7 +138,7 @@
// Original plane:
// A0x + B0y + C0z = 0 (D0 = 0)
assert plane.evaluateIsZero(M);
-
+
final double A0 = plane.x;
final double B0 = plane.y;
final double C0 = plane.z;
@@ -149,7 +149,7 @@
// A1^2 + B1^2 + C1^2 = 1
// D1 = 0.0 because it goes through origin.
-
+
// Basic strategy: Pick a variable and set it to 1.
final double a1Denom = C0 * M.y - B0 * M.z;
final double b1Denom = C0 * M.x - A0 * M.z;
@@ -158,7 +158,7 @@
final double A1;
final double B1;
final double C1;
-
+
if (Math.abs(a1Denom) >= Math.abs(b1Denom) && Math.abs(a1Denom) >= Math.abs(c1Denom)) {
A1 = 1.0;
if (Math.abs(M.y) >= Math.abs(M.z)) {
@@ -172,9 +172,8 @@
// C1 (C0 * My - B0 * Mz) = B0 * Mx - A0 * My
// C1 = (B0 * Mx - A0 * My) / (C0 * My - B0 * Mz)
C1 = (B0 * M.x - A0 * M.y) / a1Denom;
- B1 = ( -M.x - C1 * M.z) / M.y;
- }
- else {
+ B1 = (-M.x - C1 * M.z) / M.y;
+ } else {
// Alternative substitution sequence:
// C1 = (-Mx - B1 My) / Mz
// A0 + B0 * B1 + C0 * (-Mx - B1 My) / Mz = 0
@@ -182,12 +181,12 @@
// B1 (B0 * Mz - C0 * My) = C0 * Mx - A0 * Mz
// B1 = (C0 * Mx - A0 * Mz) / (B0 * Mz - C0 * My)
B1 = (A0 * M.z - C0 * M.x) / a1Denom;
- C1 = ( -M.x - B1 * M.y) / M.z;
+ C1 = (-M.x - B1 * M.y) / M.z;
}
} else if (Math.abs(b1Denom) >= Math.abs(a1Denom) && Math.abs(b1Denom) >= Math.abs(c1Denom)) {
B1 = 1.0;
if (Math.abs(M.x) >= Math.abs(M.z)) {
-
+
// B1 = 1
// Then:
//
@@ -198,7 +197,7 @@
// C1 (C0 * Mx - A0 * Mz) = A0 * My - B0 * Mx
// C1 = (A0 * My - B0 * Mx) / (C0 * Mx - A0 * Mz)
C1 = (A0 * M.y - B0 * M.x) / b1Denom;
- A1 = ( -M.y - C1 * M.z) / M.x;
+ A1 = (-M.y - C1 * M.z) / M.x;
} else {
// Alternative:
// C1 = (-My - A1 * Mx) / Mz
@@ -207,7 +206,7 @@
// A1 (A0 * Mz - C0 * Mx) = C0 * My - B0 * Mz
// A1 = (C0 * My - B0 * Mz) / (A0 * Mz - C0 * Mx)
A1 = (B0 * M.z - C0 * M.y) / b1Denom;
- C1 = ( -M.y - A1 * M.x) / M.z;
+ C1 = (-M.y - A1 * M.x) / M.z;
}
} else if (Math.abs(c1Denom) >= Math.abs(a1Denom) && Math.abs(c1Denom) >= Math.abs(b1Denom)) {
C1 = 1.0;
@@ -242,9 +241,8 @@
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));
return rval;
-
}
-
+
/**
* 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
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 687efaa..292ead3 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
@@ -242,13 +242,12 @@
* passed-in plane, and goes through both the origin and the point.
*/
public static SidedPlane constructSidedPlaneFromOnePoint(
- final Vector insidePoint,
- final Plane plane,
- final Vector intersectionPoint) {
- final Plane newPlane = Plane.constructPerpendicularCenterPlaneOnePoint(plane, intersectionPoint);
+ final Vector insidePoint, final Plane plane, final Vector intersectionPoint) {
+ final Plane newPlane =
+ Plane.constructPerpendicularCenterPlaneOnePoint(plane, intersectionPoint);
return new SidedPlane(insidePoint, newPlane.x, newPlane.y, newPlane.z, newPlane.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/TestGeoPolygon.java b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/TestGeoPolygon.java
index f956920..e7c756d 100755
--- a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/TestGeoPolygon.java
+++ b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/TestGeoPolygon.java
@@ -41,41 +41,17 @@
addToList(points2, PlanetModel.SPHERE, -64.21000754228744, -39.142217759529174);
addToList(points2, PlanetModel.SPHERE, -64.21006288371667, -39.14228379892317);
addToList(points2, PlanetModel.SPHERE, -64.21001660889377, -39.14236649277811);
-
+
final GeoPolygon polygon1 = GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE, points1);
final GeoPolygon polygon2 = GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE, points2);
- // System.out.println("Polygon1 = "+polygon1);
- // System.out.println("Polygon2 = "+polygon2);
- System.out.println("Assessing whether any points of poly 1 are inside poly2:");
- for (GeoPoint p : points1) {
- if (polygon2.isWithin(p)) {
- System.out.println(" Point "+p+" is within Polygon 2");
- }
- }
- System.out.println("Assessing whether any points of poly 2 are inside poly 1:");
- for (GeoPoint p : points2) {
- if (polygon1.isWithin(p)) {
- System.out.println(" Point "+p+" is within Polygon 1");
- }
- }
- final GeoPoint intersectionPoint = new GeoPoint(0.3374386757253078,-0.6983427934019486,-0.6312309268629938);
- if (polygon1.isWithin(intersectionPoint)) {
- System.out.println("IntersectionPoint "+intersectionPoint+" is within polygon1");
- }
- if (polygon2.isWithin(intersectionPoint)) {
- System.out.println("IntersectionPoint is within polygon2");
- }
assertFalse(polygon1.intersects(polygon2));
}
- private static void addToList(List<GeoPoint> points, PlanetModel planetModel, double lon, double lat) {
- points.add(
- new GeoPoint(
- planetModel,
- Geo3DUtil.fromDegrees(lat),
- Geo3DUtil.fromDegrees(lon)));
+ private static void addToList(
+ List<GeoPoint> points, PlanetModel planetModel, double lon, double lat) {
+ points.add(new GeoPoint(planetModel, Geo3DUtil.fromDegrees(lat), Geo3DUtil.fromDegrees(lon)));
}
-
+
@Test
public void testPolygonPointFiltering() {
final GeoPoint point1 = new GeoPoint(PlanetModel.WGS84, 1.0, 2.0);
