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 2018/04/10 15:11:20 UTC
[1/2] lucene-solr:master: LUCENE-8245: Adopt a more-rigorous way of
finding intersections with envelope planes.
Repository: lucene-solr
Updated Branches:
refs/heads/master ce061a519 -> b7dd782d9
LUCENE-8245: Adopt a more-rigorous way of finding intersections with envelope planes.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/14b313f4
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/14b313f4
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/14b313f4
Branch: refs/heads/master
Commit: 14b313f42bbc061704232eda0d0c3ff1405fe9e3
Parents: b65229c
Author: Karl Wright <Da...@gmail.com>
Authored: Tue Apr 10 11:10:40 2018 -0400
Committer: Karl Wright <Da...@gmail.com>
Committed: Tue Apr 10 11:10:40 2018 -0400
----------------------------------------------------------------------
.../spatial3d/geom/GeoComplexPolygon.java | 187 ++++++++++++++++---
.../lucene/spatial3d/geom/GeoPolygonTest.java | 1 -
2 files changed, 159 insertions(+), 29 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/14b313f4/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java
index 5c3521c..3c63559 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java
@@ -572,6 +572,144 @@ class GeoComplexPolygon extends GeoBasePolygon {
return minimumDistance;
}
+ /** Create a linear crossing edge iterator with the appropriate cutoff planes given the geometry.
+ */
+ private CountingEdgeIterator createLinearCrossingEdgeIterator(final Plane plane, final Plane abovePlane, final Plane belowPlane, final double thePointX, final double thePointY, final double thePointZ) {
+ // If thePoint and testPoint are parallel, we won't be able to determine sidedness of the bounding planes. So detect that case, and build the iterator differently if we find it.
+ // This didn't work; not sure why not:
+ //if (testPoint.isParallel(thePointX, thePointY, thePointZ)) {
+ // return new FullLinearCrossingEdgeIterator(plane, abovePlane, belowPlane, thePointX, thePointY, thePointZ);
+ //}
+ //return new SectorLinearCrossingEdgeIterator(plane, abovePlane, belowPlane, thePointX, thePointY, thePointZ);
+ //
+ try {
+ return new SectorLinearCrossingEdgeIterator(plane, abovePlane, belowPlane, thePointX, thePointY, thePointZ);
+ } catch (IllegalArgumentException e) {
+ // Assume we failed because we could not construct bounding planes, so do it another way.
+ return new FullLinearCrossingEdgeIterator(plane, abovePlane, belowPlane, thePointX, thePointY, thePointZ);
+ }
+ }
+
+ private final static GeoPoint[] NO_POINTS = new GeoPoint[0];
+
+ /** Compute crossings of an envelope plane by an edge.
+ */
+ private GeoPoint[] computeCrossings(final Plane envelopePlane, final Edge edge, final Membership... envelopeBounds) {
+ // Note: there is a possibility that one or both endpoints of the edge actually lies in the inside/outside planes. If this is the case, those endpoints may or may not show up as crossings.
+ // And yet, we absolutely cannot count each crossing more than once. So, how do we proceed?
+ // The solution is to recognize that excluded crossings will be excluded for two reasons: (1) bounds, and (2) because there's only one solution to the intersection equation, which means
+ // we never actually crossed the envelope plane. So, the way we proceed is to look for intersections, but NOT do edge bounds at all. Then, we consider the results in the context of
+ // the plane we're trying to assess.
+ //System.out.println(" Computing crossings between "+envelopePlane+" and ["+edge.startPoint+"->"+edge.endPoint+"]");
+
+ final GeoPoint[] unboundedIntersectionPoints = envelopePlane.findIntersections(planetModel, edge.plane);
+ // Go through the intersection points one at a time. Notes:
+ // (1) So that we don't double-count, we can only include at most one point in the result per intersection.
+ // (2) Single-solution results imply that the plane was not crossed. The only time we consider them is if the edge ends on the plane, in which case we count it as a crossing.
+ // (3) We tried to detect the case where the edge ends on the envelope plane by seeing if the intersection point was numerically identical to an endpoint, but that
+ // was still too strict.
+ // (4) The intersection points will be on both planes, for sure. The question is whether an intersection point "lines up" with an edge endpoint. If the edge endpoint
+ // lies in the envelope plane, then we have the possibility of a detection. The detection is confirmed if the distance "is small" between the edge endpoint and
+ // the intersection point. I see squared linear distance numbers of about 1.35e-24, which is still barely outside of the 1e-12 envelope, so a straight distance
+ // check won't work. So this is what I think we need to do:
+ // (a) Check if endpoint is on envelope plane; if not, we keep going.
+ // (b) If on envelope plane, we confirm that entire section of plane between intersection point and endpoint lies within envelope plane. (How??)
+
+ // If no points, just return. (I'm not even sure this can happen)
+ if (unboundedIntersectionPoints.length == 0) {
+ //System.out.println(" None found.");
+ return unboundedIntersectionPoints;
+ }
+
+ // Single solution has special logic
+ if (unboundedIntersectionPoints.length == 1) {
+ //System.out.println(" One found.");
+ final GeoPoint thePoint = unboundedIntersectionPoints[0];
+ if (withinBounds(thePoint, envelopeBounds) &&
+ (pointMatches(envelopePlane, thePoint, edge.startPoint) || pointMatches(envelopePlane, thePoint, edge.endPoint) ||
+ (edge.startPlane.isWithin(thePoint) && edge.endPlane.isWithin(thePoint)))) {
+ return unboundedIntersectionPoints;
+ }
+ return NO_POINTS;
+ }
+
+ // Two solutions: we could return none, one, the other one, or both.
+ //System.out.println(" Two found.");
+
+ final GeoPoint firstPoint = unboundedIntersectionPoints[0];
+ final GeoPoint secondPoint = unboundedIntersectionPoints[1];
+
+ final boolean useFirstPoint;
+ if (withinBounds(firstPoint, envelopeBounds) &&
+ (pointMatches(envelopePlane, firstPoint, edge.startPoint) || pointMatches(envelopePlane, firstPoint, edge.endPoint) ||
+ (edge.startPlane.isWithin(firstPoint) && edge.endPlane.isWithin(firstPoint)))) {
+ //System.out.println(" Point "+firstPoint+" accepted.");
+ useFirstPoint = true;
+ } else {
+ /*System.out.println(" Point "+firstPoint+" rejected; withinBounds="+withinBounds(firstPoint, envelopeBounds)+
+ "; edgeBounds="+(edge.startPlane.isWithin(firstPoint) && edge.endPlane.isWithin(firstPoint))+
+ "; startPointDist="+edge.startPoint.linearDistanceSquared(firstPoint)+"; endPointDist="+edge.endPoint.linearDistanceSquared(firstPoint)); */
+ useFirstPoint = false;
+ }
+
+ final boolean useSecondPoint;
+ if (withinBounds(secondPoint, envelopeBounds) &&
+ (pointMatches(envelopePlane, secondPoint, edge.startPoint) || pointMatches(envelopePlane, secondPoint, edge.endPoint) ||
+ (edge.startPlane.isWithin(secondPoint) && edge.endPlane.isWithin(secondPoint)))) {
+ //System.out.println(" Point "+secondPoint+" accepted.");
+ useSecondPoint = true;
+ } else {
+ /*System.out.println(" Point "+secondPoint+" rejected; withinBounds="+withinBounds(secondPoint, envelopeBounds)+
+ "; edgeBounds="+(edge.startPlane.isWithin(secondPoint) && edge.endPlane.isWithin(secondPoint))+
+ "; startPointDist="+edge.startPoint.linearDistanceSquared(secondPoint)+"; endPointDist="+edge.endPoint.linearDistanceSquared(secondPoint)); */
+ useSecondPoint = false;
+ }
+
+ if (useFirstPoint && useSecondPoint) {
+ return unboundedIntersectionPoints;
+ }
+
+ if (useFirstPoint) {
+ return new GeoPoint[]{firstPoint};
+ }
+
+ if (useSecondPoint) {
+ return new GeoPoint[]{secondPoint};
+ }
+
+ return NO_POINTS;
+ }
+
+ /** This distance is arbitrary, but it must NOT allow non-intersections to be detected.
+ */
+ private final static double MATCH_MAXIMUM_DISTANCE_SQUARED = Vector.MINIMUM_RESOLUTION_SQUARED * 2.0;
+
+ /** Return true of the point matches the edge endpoint, or false otherwise.
+ * This method is here to compensate for the fact that we don't always detect an intersection due to the bounds interfering.
+ */
+ private static boolean pointMatches(final Plane envelopePlane, final GeoPoint intersectionPoint, final GeoPoint edgePoint) {
+ // If edge isn't on the envelope plane, no match
+ if (!envelopePlane.evaluateIsZero(edgePoint)) {
+ return false;
+ }
+ // As a proxy for staying "within" the envelope plane, compute linear squared distance. If clearly too close to be anything other than local, we can
+ // just return true. Otherwise, we'll need to add more complicated fallback computations.
+ if (edgePoint.linearDistanceSquared(intersectionPoint) <= MATCH_MAXIMUM_DISTANCE_SQUARED) {
+ return true;
+ }
+ // More to be done? Cross that bridge if we come to it.
+ return false;
+ }
+
+ private static boolean withinBounds(final GeoPoint point, final Membership[] bounds) {
+ for (final Membership bound : bounds) {
+ if (!bound.isWithin(point)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
/**
* An instance of this class describes a single edge, and includes what is necessary to reliably determine intersection
* in the context of the even/odd algorithm used.
@@ -942,8 +1080,8 @@ class GeoComplexPolygon extends GeoBasePolygon {
}
// Determine crossings of this edge against all inside/outside planes. There's no further need to look at the actual travel plane itself.
- final GeoPoint[] aboveCrossings = abovePlane.findCrossings(planetModel, edge.plane, bound, edge.startPlane, edge.endPlane);
- final GeoPoint[] belowCrossings = belowPlane.findCrossings(planetModel, edge.plane, bound, edge.startPlane, edge.endPlane);
+ final GeoPoint[] aboveCrossings = computeCrossings(abovePlane, edge, bound);
+ final GeoPoint[] belowCrossings = computeCrossings(belowPlane, edge, bound);
if (aboveCrossings != null) {
aboveCrossingCount += aboveCrossings.length;
@@ -957,24 +1095,6 @@ class GeoComplexPolygon extends GeoBasePolygon {
}
- /** Create a linear crossing edge iterator with the appropriate cutoff planes given the geometry.
- */
- private CountingEdgeIterator createLinearCrossingEdgeIterator(final Plane plane, final Plane abovePlane, final Plane belowPlane, final double thePointX, final double thePointY, final double thePointZ) {
- // If thePoint and testPoint are parallel, we won't be able to determine sidedness of the bounding planes. So detect that case, and build the iterator differently if we find it.
- // This didn't work; not sure why not:
- //if (testPoint.isParallel(thePointX, thePointY, thePointZ)) {
- // return new FullLinearCrossingEdgeIterator(plane, abovePlane, belowPlane, thePointX, thePointY, thePointZ);
- //}
- //return new SectorLinearCrossingEdgeIterator(plane, abovePlane, belowPlane, thePointX, thePointY, thePointZ);
- //
- try {
- return new SectorLinearCrossingEdgeIterator(plane, abovePlane, belowPlane, thePointX, thePointY, thePointZ);
- } catch (IllegalArgumentException e) {
- // Assume we failed because we could not construct bounding planes, so do it another way.
- return new FullLinearCrossingEdgeIterator(plane, abovePlane, belowPlane, thePointX, thePointY, thePointZ);
- }
- }
-
/** Count the number of verifiable edge crossings for less than 1/2 a world.
*/
private class SectorLinearCrossingEdgeIterator implements CountingEdgeIterator {
@@ -1030,8 +1150,8 @@ class GeoComplexPolygon extends GeoBasePolygon {
}
// Determine crossings of this edge against all inside/outside planes. There's no further need to look at the actual travel plane itself.
- final GeoPoint[] aboveCrossings = abovePlane.findCrossings(planetModel, edge.plane, bound1, bound2, edge.startPlane, edge.endPlane);
- final GeoPoint[] belowCrossings = belowPlane.findCrossings(planetModel, edge.plane, bound1, bound2, edge.startPlane, edge.endPlane);
+ final GeoPoint[] aboveCrossings = computeCrossings(abovePlane, edge, bound1, bound2);
+ final GeoPoint[] belowCrossings = computeCrossings(belowPlane, edge, bound1, bound2);
if (aboveCrossings != null) {
aboveCrossingCount += aboveCrossings.length;
@@ -1047,7 +1167,7 @@ class GeoComplexPolygon extends GeoBasePolygon {
/** Count the number of verifiable edge crossings for a dual-leg journey.
*/
- private class DualCrossingEdgeIterator implements EdgeIterator {
+ private class DualCrossingEdgeIterator implements CountingEdgeIterator {
// This is a hash of which edges we've already looked at and tallied, so we don't repeat ourselves.
// It is lazily initialized since most transitions cross no edges at all.
@@ -1218,6 +1338,7 @@ class GeoComplexPolygon extends GeoBasePolygon {
}
}
+ @Override
public int getCrossingCount() {
// Doesn't return the actual crossing count -- just gets the even/odd part right
if (innerCrossingCount < outerCrossingCount) {
@@ -1272,25 +1393,35 @@ class GeoComplexPolygon extends GeoBasePolygon {
break;
}
}
- System.out.println("");
*/
+ //System.out.println("");
//System.out.println("Considering edge "+(edge.startPoint)+" -> "+(edge.endPoint));
// Some edges are going to be given to us even when there's no real intersection, so do that as a sanity check, first.
final GeoPoint[] travelCrossings = travelPlane.findIntersections(planetModel, edge.plane, checkPointCutoffPlane, checkPointOtherCutoffPlane, edge.startPlane, edge.endPlane);
if (travelCrossings != null && travelCrossings.length == 0) {
+ //System.out.println(" No intersections with travel plane...");
final GeoPoint[] testPointCrossings = testPointPlane.findIntersections(planetModel, edge.plane, testPointCutoffPlane, testPointOtherCutoffPlane, edge.startPlane, edge.endPlane);
if (testPointCrossings != null && testPointCrossings.length == 0) {
// As a last resort, see if the edge endpoints are on either plane. This is sometimes necessary because the
// intersection computation logic might not detect near-miss edges otherwise.
+ //System.out.println(" No intersections with testpoint plane...");
if (!travelPlane.evaluateIsZero(edge.startPoint) && !travelPlane.evaluateIsZero(edge.endPoint) &&
!testPointPlane.evaluateIsZero(edge.startPoint) && !testPointPlane.evaluateIsZero(edge.endPoint)) {
return true;
+ } else {
+ //System.out.println(" Startpoint/travelPlane="+travelPlane.evaluate(edge.startPoint)+" Startpoint/testPointPlane="+testPointPlane.evaluate(edge.startPoint));
+ //System.out.println(" Endpoint/travelPlane="+travelPlane.evaluate(edge.endPoint)+" Endpoint/testPointPlane="+testPointPlane.evaluate(edge.endPoint));
}
+ } else {
+ //System.out.println(" Intersection found with testPoint plane...");
}
+ } else {
+ //System.out.println(" Intersection found with travel plane...");
}
+ //System.out.println(" Edge intersects travel or testPoint plane");
/*
System.out.println(
" start point travel dist="+travelPlane.evaluate(edge.startPoint)+"; end point travel dist="+travelPlane.evaluate(edge.endPoint));
@@ -1307,10 +1438,10 @@ class GeoComplexPolygon extends GeoBasePolygon {
*/
// Determine crossings of this edge against all inside/outside planes. There's no further need to look at the actual travel plane itself.
- final GeoPoint[] travelInnerCrossings = travelInsidePlane.findCrossings(planetModel, edge.plane, checkPointCutoffPlane, insideTravelCutoffPlane, edge.startPlane, edge.endPlane);
- final GeoPoint[] travelOuterCrossings = travelOutsidePlane.findCrossings(planetModel, edge.plane, checkPointCutoffPlane, outsideTravelCutoffPlane, edge.startPlane, edge.endPlane);
- final GeoPoint[] testPointInnerCrossings = testPointInsidePlane.findCrossings(planetModel, edge.plane, testPointCutoffPlane, insideTestPointCutoffPlane, edge.startPlane, edge.endPlane);
- final GeoPoint[] testPointOuterCrossings = testPointOutsidePlane.findCrossings(planetModel, edge.plane, testPointCutoffPlane, outsideTestPointCutoffPlane, edge.startPlane, edge.endPlane);
+ final GeoPoint[] travelInnerCrossings = computeCrossings(travelInsidePlane, edge, checkPointCutoffPlane, insideTravelCutoffPlane);
+ final GeoPoint[] travelOuterCrossings = computeCrossings(travelOutsidePlane, edge, checkPointCutoffPlane, outsideTravelCutoffPlane);
+ final GeoPoint[] testPointInnerCrossings = computeCrossings(testPointInsidePlane, edge, testPointCutoffPlane, insideTestPointCutoffPlane);
+ final GeoPoint[] testPointOuterCrossings = computeCrossings(testPointOutsidePlane, edge, testPointCutoffPlane, outsideTestPointCutoffPlane);
// If the edge goes through the inner-inner intersection point, or the outer-outer intersection point, we need to be sure we count that only once.
// It may appear in both lists. Use a hash for this right now.
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/14b313f4/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java
index 46750d4..455eee6 100755
--- a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java
+++ b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java
@@ -1522,7 +1522,6 @@ shape:
}
@Test
- @AwaitsFix(bugUrl="https://issues.apache.org/jira/browse/LUCENE-8245")
public void testLUCENE8245_case2() {
//POLYGON((5.512285089810178 -26.833721534785912,12.13983320542565 -16.085163683089583,4.868755337835201 -9.167423203860656,0.0 -5.261747514529465,-15.696549288211289 -21.362181191487718,5.512285089810178 -26.833721534785912))
final List<GeoPoint> points = new ArrayList<>();
[2/2] lucene-solr:master: Merge branch 'master' of
https://git-wip-us.apache.org/repos/asf/lucene-solr
Posted by kw...@apache.org.
Merge branch 'master' of https://git-wip-us.apache.org/repos/asf/lucene-solr
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/b7dd782d
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/b7dd782d
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/b7dd782d
Branch: refs/heads/master
Commit: b7dd782d98d83a8b3e08076834e5cdbaa29df4cb
Parents: 14b313f ce061a5
Author: Karl Wright <Da...@gmail.com>
Authored: Tue Apr 10 11:10:51 2018 -0400
Committer: Karl Wright <Da...@gmail.com>
Committed: Tue Apr 10 11:10:51 2018 -0400
----------------------------------------------------------------------
solr/solr-ref-guide/src/json-request-api.adoc | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)
----------------------------------------------------------------------