in lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java [252:760]
private boolean isInSet(
final double x,
final double y,
final double z,
final GeoPoint testPoint,
final boolean testPointInSet,
final Plane testPointFixedXPlane,
final Plane testPointFixedXAbovePlane,
final Plane testPointFixedXBelowPlane,
final Plane testPointFixedYPlane,
final Plane testPointFixedYAbovePlane,
final Plane testPointFixedYBelowPlane,
final Plane testPointFixedZPlane,
final Plane testPointFixedZAbovePlane,
final Plane testPointFixedZBelowPlane) {
// System.out.println("\nIsInSet called for [" + x + "," + y + "," + z + "], testPoint="
// + testPoint + "; is in set? " + testPointInSet);
// If we're right on top of the point, we know the answer.
if (testPoint.isNumericallyIdentical(x, y, z)) {
return testPointInSet;
}
// If we're right on top of any of the test planes, we navigate solely on that plane.
if (testPointFixedYAbovePlane != null
&& testPointFixedYBelowPlane != null
&& testPointFixedYPlane.evaluateIsZero(x, y, z)) {
// Use the XZ plane exclusively.
// System.out.println(" Using XZ plane alone");
final CountingEdgeIterator crossingEdgeIterator =
createLinearCrossingEdgeIterator(
testPoint,
testPointFixedYPlane,
testPointFixedYAbovePlane,
testPointFixedYBelowPlane,
x,
y,
z);
// Traverse our way from the test point to the check point. Use the y tree because that's
// fixed.
yTree.traverse(crossingEdgeIterator, testPoint.y);
return crossingEdgeIterator.isOnEdge()
|| (((crossingEdgeIterator.getCrossingCount() & 1) == 0)
? testPointInSet
: !testPointInSet);
} else if (testPointFixedXAbovePlane != null
&& testPointFixedXBelowPlane != null
&& testPointFixedXPlane.evaluateIsZero(x, y, z)) {
// Use the YZ plane exclusively.
// System.out.println(" Using YZ plane alone");
final CountingEdgeIterator crossingEdgeIterator =
createLinearCrossingEdgeIterator(
testPoint,
testPointFixedXPlane,
testPointFixedXAbovePlane,
testPointFixedXBelowPlane,
x,
y,
z);
// Traverse our way from the test point to the check point. Use the x tree because that's
// fixed.
xTree.traverse(crossingEdgeIterator, testPoint.x);
return crossingEdgeIterator.isOnEdge()
|| (((crossingEdgeIterator.getCrossingCount() & 1) == 0)
? testPointInSet
: !testPointInSet);
} else if (testPointFixedZAbovePlane != null
&& testPointFixedZBelowPlane != null
&& testPointFixedZPlane.evaluateIsZero(x, y, z)) {
// System.out.println(" Using XY plane alone");
final CountingEdgeIterator crossingEdgeIterator =
createLinearCrossingEdgeIterator(
testPoint,
testPointFixedZPlane,
testPointFixedZAbovePlane,
testPointFixedZBelowPlane,
x,
y,
z);
// Traverse our way from the test point to the check point. Use the z tree because that's
// fixed.
zTree.traverse(crossingEdgeIterator, testPoint.z);
return crossingEdgeIterator.isOnEdge()
|| (((crossingEdgeIterator.getCrossingCount() & 1) == 0)
? testPointInSet
: !testPointInSet);
} else {
// System.out.println(" Using two planes");
// This is the expensive part!!
// Changing the code below has an enormous impact on the queries per second we see with the
// benchmark.
// We need to use two planes to get there. We don't know which two planes will do it but we
// can figure it out.
final Plane travelPlaneFixedX = new Plane(1.0, 0.0, 0.0, -x);
final Plane travelPlaneFixedY = new Plane(0.0, 1.0, 0.0, -y);
final Plane travelPlaneFixedZ = new Plane(0.0, 0.0, 1.0, -z);
Plane fixedYAbovePlane = new Plane(travelPlaneFixedY, true);
if (-fixedYAbovePlane.D - planetModel.getMaximumYValue() > NEAR_EDGE_CUTOFF
|| planetModel.getMinimumYValue() + fixedYAbovePlane.D > NEAR_EDGE_CUTOFF) {
fixedYAbovePlane = null;
}
Plane fixedYBelowPlane = new Plane(travelPlaneFixedY, false);
if (-fixedYBelowPlane.D - planetModel.getMaximumYValue() > NEAR_EDGE_CUTOFF
|| planetModel.getMinimumYValue() + fixedYBelowPlane.D > NEAR_EDGE_CUTOFF) {
fixedYBelowPlane = null;
}
Plane fixedXAbovePlane = new Plane(travelPlaneFixedX, true);
if (-fixedXAbovePlane.D - planetModel.getMaximumXValue() > NEAR_EDGE_CUTOFF
|| planetModel.getMinimumXValue() + fixedXAbovePlane.D > NEAR_EDGE_CUTOFF) {
fixedXAbovePlane = null;
}
Plane fixedXBelowPlane = new Plane(travelPlaneFixedX, false);
if (-fixedXBelowPlane.D - planetModel.getMaximumXValue() > NEAR_EDGE_CUTOFF
|| planetModel.getMinimumXValue() + fixedXBelowPlane.D > NEAR_EDGE_CUTOFF) {
fixedXBelowPlane = null;
}
Plane fixedZAbovePlane = new Plane(travelPlaneFixedZ, true);
if (-fixedZAbovePlane.D - planetModel.getMaximumZValue() > NEAR_EDGE_CUTOFF
|| planetModel.getMinimumZValue() + fixedZAbovePlane.D > NEAR_EDGE_CUTOFF) {
fixedZAbovePlane = null;
}
Plane fixedZBelowPlane = new Plane(travelPlaneFixedZ, false);
if (-fixedZBelowPlane.D - planetModel.getMaximumZValue() > NEAR_EDGE_CUTOFF
|| planetModel.getMinimumZValue() + fixedZBelowPlane.D > NEAR_EDGE_CUTOFF) {
fixedZBelowPlane = null;
}
// Find the intersection points for each one of these and the complementary test point planes.
final List<TraversalStrategy> traversalStrategies = new ArrayList<>(12);
if (testPointFixedYAbovePlane != null
&& testPointFixedYBelowPlane != null
&& fixedXAbovePlane != null
&& fixedXBelowPlane != null) {
// check if planes intersects inside world
final double checkAbove =
4.0
* (fixedXAbovePlane.D * fixedXAbovePlane.D * planetModel.inverseXYScalingSquared
+ testPointFixedYAbovePlane.D
* testPointFixedYAbovePlane.D
* planetModel.inverseXYScalingSquared
- 1.0);
final double checkBelow =
4.0
* (fixedXBelowPlane.D * fixedXBelowPlane.D * planetModel.inverseXYScalingSquared
+ testPointFixedYBelowPlane.D
* testPointFixedYBelowPlane.D
* planetModel.inverseXYScalingSquared
- 1.0);
if (checkAbove < Vector.MINIMUM_RESOLUTION_SQUARED
&& checkBelow < Vector.MINIMUM_RESOLUTION_SQUARED) {
// System.out.println(" Looking for intersections between travel and test point
// planes...");
final GeoPoint[] XIntersectionsY =
travelPlaneFixedX.findIntersections(planetModel, testPointFixedYPlane);
for (final GeoPoint p : XIntersectionsY) {
// Travel would be in YZ plane (fixed x) then in XZ (fixed y)
// We compute distance we need to travel as a placeholder for the number of
// intersections we might encounter.
// final double newDistance = p.arcDistance(testPoint) + p.arcDistance(thePoint);
final double tpDelta1 = testPoint.x - p.x;
final double tpDelta2 = testPoint.z - p.z;
final double cpDelta1 = y - p.y;
final double cpDelta2 = z - p.z;
final double newDistance =
tpDelta1 * tpDelta1
+ tpDelta2 * tpDelta2
+ cpDelta1 * cpDelta1
+ cpDelta2 * cpDelta2;
// final double newDistance = (testPoint.x - p.x) * (testPoint.x - p.x) + (testPoint.z -
// p.z) * (testPoint.z - p.z) + (thePoint.y - p.y) * (thePoint.y - p.y) + (thePoint.z -
// p.z) * (thePoint.z - p.z);
// final double newDistance = Math.abs(testPoint.x - p.x) + Math.abs(thePoint.y - p.y);
traversalStrategies.add(
new TraversalStrategy(
newDistance,
testPoint.y,
x,
testPointFixedYPlane,
testPointFixedYAbovePlane,
testPointFixedYBelowPlane,
travelPlaneFixedX,
fixedXAbovePlane,
fixedXBelowPlane,
yTree,
xTree,
p));
}
}
}
if (testPointFixedZAbovePlane != null
&& testPointFixedZBelowPlane != null
&& fixedXAbovePlane != null
&& fixedXBelowPlane != null) {
// check if planes intersects inside world
final double checkAbove =
4.0
* (fixedXAbovePlane.D * fixedXAbovePlane.D * planetModel.inverseXYScalingSquared
+ testPointFixedZAbovePlane.D
* testPointFixedZAbovePlane.D
* planetModel.inverseZScalingSquared
- 1.0);
final double checkBelow =
4.0
* (fixedXBelowPlane.D * fixedXBelowPlane.D * planetModel.inverseXYScalingSquared
+ testPointFixedZBelowPlane.D
* testPointFixedZBelowPlane.D
* planetModel.inverseZScalingSquared
- 1.0);
if (checkAbove < Vector.MINIMUM_RESOLUTION_SQUARED
&& checkBelow < Vector.MINIMUM_RESOLUTION_SQUARED) {
// System.out.println(" Looking for intersections between travel and test point
// planes...");
final GeoPoint[] XIntersectionsZ =
travelPlaneFixedX.findIntersections(planetModel, testPointFixedZPlane);
for (final GeoPoint p : XIntersectionsZ) {
// Travel would be in YZ plane (fixed x) then in XY (fixed z)
// final double newDistance = p.arcDistance(testPoint) + p.arcDistance(thePoint);
final double tpDelta1 = testPoint.x - p.x;
final double tpDelta2 = testPoint.y - p.y;
final double cpDelta1 = y - p.y;
final double cpDelta2 = z - p.z;
final double newDistance =
tpDelta1 * tpDelta1
+ tpDelta2 * tpDelta2
+ cpDelta1 * cpDelta1
+ cpDelta2 * cpDelta2;
// final double newDistance = (testPoint.x - p.x) * (testPoint.x - p.x) + (testPoint.y -
// p.y) * (testPoint.y - p.y) + (thePoint.y - p.y) * (thePoint.y - p.y) + (thePoint.z -
// p.z) * (thePoint.z - p.z);
// final double newDistance = Math.abs(testPoint.x - p.x) + Math.abs(thePoint.z - p.z);
traversalStrategies.add(
new TraversalStrategy(
newDistance,
testPoint.z,
x,
testPointFixedZPlane,
testPointFixedZAbovePlane,
testPointFixedZBelowPlane,
travelPlaneFixedX,
fixedXAbovePlane,
fixedXBelowPlane,
zTree,
xTree,
p));
}
}
}
if (testPointFixedXAbovePlane != null
&& testPointFixedXBelowPlane != null
&& fixedYAbovePlane != null
&& fixedYBelowPlane != null) {
// check if planes intersects inside world
final double checkAbove =
4.0
* (testPointFixedXAbovePlane.D
* testPointFixedXAbovePlane.D
* planetModel.inverseXYScalingSquared
+ fixedYAbovePlane.D * fixedYAbovePlane.D * planetModel.inverseXYScalingSquared
- 1.0);
final double checkBelow =
4.0
* (testPointFixedXBelowPlane.D
* testPointFixedXBelowPlane.D
* planetModel.inverseXYScalingSquared
+ fixedYBelowPlane.D * fixedYBelowPlane.D * planetModel.inverseXYScalingSquared
- 1.0);
if (checkAbove < Vector.MINIMUM_RESOLUTION_SQUARED
&& checkBelow < Vector.MINIMUM_RESOLUTION_SQUARED) {
// System.out.println(" Looking for intersections between travel and test point
// planes...");
final GeoPoint[] YIntersectionsX =
travelPlaneFixedY.findIntersections(planetModel, testPointFixedXPlane);
for (final GeoPoint p : YIntersectionsX) {
// Travel would be in XZ plane (fixed y) then in YZ (fixed x)
// final double newDistance = p.arcDistance(testPoint) + p.arcDistance(thePoint);
final double tpDelta1 = testPoint.y - p.y;
final double tpDelta2 = testPoint.z - p.z;
final double cpDelta1 = x - p.x;
final double cpDelta2 = z - p.z;
final double newDistance =
tpDelta1 * tpDelta1
+ tpDelta2 * tpDelta2
+ cpDelta1 * cpDelta1
+ cpDelta2 * cpDelta2;
// final double newDistance = (testPoint.y - p.y) * (testPoint.y - p.y) + (testPoint.z -
// p.z) * (testPoint.z - p.z) + (thePoint.x - p.x) * (thePoint.x - p.x) + (thePoint.z -
// p.z) * (thePoint.z - p.z);
// final double newDistance = Math.abs(testPoint.y - p.y) + Math.abs(thePoint.x - p.x);
traversalStrategies.add(
new TraversalStrategy(
newDistance,
testPoint.x,
y,
testPointFixedXPlane,
testPointFixedXAbovePlane,
testPointFixedXBelowPlane,
travelPlaneFixedY,
fixedYAbovePlane,
fixedYBelowPlane,
xTree,
yTree,
p));
}
}
}
if (testPointFixedZAbovePlane != null
&& testPointFixedZBelowPlane != null
&& fixedYAbovePlane != null
&& fixedYBelowPlane != null) {
// check if planes intersects inside world
final double checkAbove =
4.0
* (testPointFixedZAbovePlane.D
* testPointFixedZAbovePlane.D
* planetModel.inverseZScalingSquared
+ fixedYAbovePlane.D * fixedYAbovePlane.D * planetModel.inverseXYScalingSquared
- 1.0);
final double checkBelow =
4.0
* (testPointFixedZBelowPlane.D
* testPointFixedZBelowPlane.D
* planetModel.inverseZScalingSquared
+ fixedYBelowPlane.D * fixedYBelowPlane.D * planetModel.inverseXYScalingSquared
- 1.0);
if (checkAbove < Vector.MINIMUM_RESOLUTION_SQUARED
&& checkBelow < Vector.MINIMUM_RESOLUTION_SQUARED) {
// System.out.println(" Looking for intersections between travel and test point
// planes...");
final GeoPoint[] YIntersectionsZ =
travelPlaneFixedY.findIntersections(planetModel, testPointFixedZPlane);
for (final GeoPoint p : YIntersectionsZ) {
// Travel would be in XZ plane (fixed y) then in XY (fixed z)
// final double newDistance = p.arcDistance(testPoint) + p.arcDistance(thePoint);
final double tpDelta1 = testPoint.x - p.x;
final double tpDelta2 = testPoint.y - p.y;
final double cpDelta1 = x - p.x;
final double cpDelta2 = z - p.z;
final double newDistance =
tpDelta1 * tpDelta1
+ tpDelta2 * tpDelta2
+ cpDelta1 * cpDelta1
+ cpDelta2 * cpDelta2;
// final double newDistance = (testPoint.x - p.x) * (testPoint.x - p.x) + (testPoint.y -
// p.y) * (testPoint.y - p.y) + (thePoint.x - p.x) * (thePoint.x - p.x) + (thePoint.z -
// p.z) * (thePoint.z - p.z);
// final double newDistance = Math.abs(testPoint.y - p.y) + Math.abs(thePoint.z - p.z);
traversalStrategies.add(
new TraversalStrategy(
newDistance,
testPoint.z,
y,
testPointFixedZPlane,
testPointFixedZAbovePlane,
testPointFixedZBelowPlane,
travelPlaneFixedY,
fixedYAbovePlane,
fixedYBelowPlane,
zTree,
yTree,
p));
}
}
}
if (testPointFixedXAbovePlane != null
&& testPointFixedXBelowPlane != null
&& fixedZAbovePlane != null
&& fixedZBelowPlane != null) {
// check if planes intersects inside world
final double checkAbove =
4.0
* (testPointFixedXAbovePlane.D
* testPointFixedXAbovePlane.D
* planetModel.inverseXYScalingSquared
+ fixedZAbovePlane.D * fixedZAbovePlane.D * planetModel.inverseZScalingSquared
- 1.0);
final double checkBelow =
4.0
* (testPointFixedXBelowPlane.D
* testPointFixedXBelowPlane.D
* planetModel.inverseXYScalingSquared
+ fixedZBelowPlane.D * fixedZBelowPlane.D * planetModel.inverseZScalingSquared
- 1.0);
if (checkAbove < Vector.MINIMUM_RESOLUTION_SQUARED
&& checkBelow < Vector.MINIMUM_RESOLUTION_SQUARED) {
// System.out.println(" Looking for intersections between travel and test point
// planes...");
final GeoPoint[] ZIntersectionsX =
travelPlaneFixedZ.findIntersections(planetModel, testPointFixedXPlane);
for (final GeoPoint p : ZIntersectionsX) {
// Travel would be in XY plane (fixed z) then in YZ (fixed x)
// final double newDistance = p.arcDistance(testPoint) + p.arcDistance(thePoint);
final double tpDelta1 = testPoint.y - p.y;
final double tpDelta2 = testPoint.z - p.z;
final double cpDelta1 = y - p.y;
final double cpDelta2 = x - p.x;
final double newDistance =
tpDelta1 * tpDelta1
+ tpDelta2 * tpDelta2
+ cpDelta1 * cpDelta1
+ cpDelta2 * cpDelta2;
// final double newDistance = (testPoint.y - p.y) * (testPoint.y - p.y) + (testPoint.z -
// p.z) * (testPoint.z - p.z) + (thePoint.y - p.y) * (thePoint.y - p.y) + (thePoint.x -
// p.x) * (thePoint.x - p.x);
// final double newDistance = Math.abs(testPoint.z - p.z) + Math.abs(thePoint.x - p.x);
traversalStrategies.add(
new TraversalStrategy(
newDistance,
testPoint.x,
z,
testPointFixedXPlane,
testPointFixedXAbovePlane,
testPointFixedXBelowPlane,
travelPlaneFixedZ,
fixedZAbovePlane,
fixedZBelowPlane,
xTree,
zTree,
p));
}
}
}
if (testPointFixedYAbovePlane != null
&& testPointFixedYBelowPlane != null
&& fixedZAbovePlane != null
&& fixedZBelowPlane != null) {
// check if planes intersects inside world
final double checkAbove =
4.0
* (testPointFixedYAbovePlane.D
* testPointFixedYAbovePlane.D
* planetModel.inverseXYScalingSquared
+ fixedZAbovePlane.D * fixedZAbovePlane.D * planetModel.inverseZScalingSquared
- 1.0);
final double checkBelow =
4.0
* (testPointFixedYBelowPlane.D
* testPointFixedYBelowPlane.D
* planetModel.inverseXYScalingSquared
+ fixedZBelowPlane.D * fixedZBelowPlane.D * planetModel.inverseZScalingSquared
- 1.0);
if (checkAbove < Vector.MINIMUM_RESOLUTION_SQUARED
&& checkBelow < Vector.MINIMUM_RESOLUTION_SQUARED) {
// System.out.println(" Looking for intersections between travel and test point
// planes...");
final GeoPoint[] ZIntersectionsY =
travelPlaneFixedZ.findIntersections(planetModel, testPointFixedYPlane);
for (final GeoPoint p : ZIntersectionsY) {
// Travel would be in XY plane (fixed z) then in XZ (fixed y)
// final double newDistance = p.arcDistance(testPoint) + p.arcDistance(thePoint);
final double tpDelta1 = testPoint.x - p.x;
final double tpDelta2 = testPoint.z - p.z;
final double cpDelta1 = y - p.y;
final double cpDelta2 = x - p.x;
final double newDistance =
tpDelta1 * tpDelta1
+ tpDelta2 * tpDelta2
+ cpDelta1 * cpDelta1
+ cpDelta2 * cpDelta2;
// final double newDistance = (testPoint.x - p.x) * (testPoint.x - p.x) + (testPoint.z -
// p.z) * (testPoint.z - p.z) + (thePoint.y - p.y) * (thePoint.y - p.y) + (thePoint.x -
// p.x) * (thePoint.x - p.x);
// final double newDistance = Math.abs(testPoint.z - p.z) + Math.abs(thePoint.y - p.y);
traversalStrategies.add(
new TraversalStrategy(
newDistance,
testPoint.y,
z,
testPointFixedYPlane,
testPointFixedYAbovePlane,
testPointFixedYBelowPlane,
travelPlaneFixedZ,
fixedZAbovePlane,
fixedZBelowPlane,
yTree,
zTree,
p));
}
}
}
Collections.sort(traversalStrategies);
if (traversalStrategies.size() == 0) {
throw new IllegalArgumentException("No dual-plane travel strategies were found");
}
// Loop through travel strategies, in order, until we find one that works.
for (final TraversalStrategy ts : traversalStrategies) {
try {
return ts.apply(testPoint, testPointInSet, x, y, z);
} catch (
@SuppressWarnings("unused")
IllegalArgumentException e) {
// Continue
}
}
throw new IllegalArgumentException("Exhausted all traversal strategies");
}
}