From commits-return-99815-archive-asf-public=cust-asf.ponee.io@lucene.apache.org Wed Mar 28 01:06:44 2018 Return-Path: X-Original-To: archive-asf-public@cust-asf.ponee.io Delivered-To: archive-asf-public@cust-asf.ponee.io Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by mx-eu-01.ponee.io (Postfix) with SMTP id 867E418064E for ; Wed, 28 Mar 2018 01:06:43 +0200 (CEST) Received: (qmail 32301 invoked by uid 500); 27 Mar 2018 23:06:42 -0000 Mailing-List: contact commits-help@lucene.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@lucene.apache.org Delivered-To: mailing list commits@lucene.apache.org Received: (qmail 32288 invoked by uid 99); 27 Mar 2018 23:06:42 -0000 Received: from git1-us-west.apache.org (HELO git1-us-west.apache.org) (140.211.11.23) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 27 Mar 2018 23:06:42 +0000 Received: by git1-us-west.apache.org (ASF Mail Server at git1-us-west.apache.org, from userid 33) id 605EEF68C1; Tue, 27 Mar 2018 23:06:42 +0000 (UTC) Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: kwright@apache.org To: commits@lucene.apache.org Message-Id: <7e0815e16ddb42978ddaf0bc961d1c4c@git.apache.org> X-Mailer: ASF-Git Admin Mailer Subject: lucene-solr:branch_7x: LUCENE-8227: Handle identical planes properly in GeoComplexPolygon. Date: Tue, 27 Mar 2018 23:06:42 +0000 (UTC) Repository: lucene-solr Updated Branches: refs/heads/branch_7x f8b8ac719 -> e65609169 LUCENE-8227: Handle identical planes properly in GeoComplexPolygon. Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/e6560916 Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/e6560916 Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/e6560916 Branch: refs/heads/branch_7x Commit: e656091690b7efc869da5eb2702791152070b388 Parents: f8b8ac7 Author: Karl Wright Authored: Tue Mar 27 19:05:27 2018 -0400 Committer: Karl Wright Committed: Tue Mar 27 19:06:31 2018 -0400 ---------------------------------------------------------------------- .../spatial3d/geom/GeoComplexPolygon.java | 109 +++++++++++-------- 1 file changed, 63 insertions(+), 46 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e6560916/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 da99d50..de12348 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 @@ -1017,19 +1017,26 @@ class GeoComplexPolygon extends GeoBasePolygon { private void countCrossingPoint(final GeoPoint crossingPoint, final Edge edge) { if (crossingPoint.isNumericallyIdentical(edge.startPoint)) { + + // The crossing point is shared by two edges. If we are going to count it, this is the edge we'll count it on. // We have to figure out if this crossing should be counted. + // We look at the above plane and the below plane and see if we cross either of them. + // If we cross NEITHER of them: we're in the "zone" between the planes, and this edge doesn't count. + // Does the crossing for this edge go up, or down? Or can't we tell? - final GeoPoint[] aboveIntersections = abovePlane.findIntersections(planetModel, edge.plane, edge.startPlane, edge.endPlane); - final GeoPoint[] belowIntersections = belowPlane.findIntersections(planetModel, edge.plane, edge.startPlane, edge.endPlane); - - assert !(aboveIntersections.length > 0 && belowIntersections.length > 0) : "edge that ends in a crossing can't both up and down"; - - if (aboveIntersections.length == 0 && belowIntersections.length == 0) { + final GeoPoint[] aboveIntersections = abovePlane.findCrossings(planetModel, edge.plane, edge.startPlane, edge.endPlane); + final GeoPoint[] belowIntersections = belowPlane.findCrossings(planetModel, edge.plane, edge.startPlane, edge.endPlane); + + if ((aboveIntersections == null || aboveIntersections.length == 0) && (belowIntersections == null || belowIntersections.length == 0)) { return; } - - final boolean edgeCrossesAbove = aboveIntersections.length > 0; + + // A null value means we have a situation where the edge is numerically identical. That's not counted as a "crossing". + + assert !(aboveIntersections != null && aboveIntersections.length > 0 && belowIntersections != null && belowIntersections.length > 0) : "edge that ends in a crossing can't be both up and down!"; + + final boolean edgeCrossesAbove = aboveIntersections != null && aboveIntersections.length > 0; // This depends on the previous edge that first departs from identicalness. Edge assessEdge = edge; @@ -1037,12 +1044,10 @@ class GeoComplexPolygon extends GeoBasePolygon { GeoPoint[] assessBelowIntersections; while (true) { assessEdge = assessEdge.previous; - assessAboveIntersections = abovePlane.findIntersections(planetModel, assessEdge.plane, assessEdge.startPlane, assessEdge.endPlane); - assessBelowIntersections = belowPlane.findIntersections(planetModel, assessEdge.plane, assessEdge.startPlane, assessEdge.endPlane); - - assert !(assessAboveIntersections.length > 0 && assessBelowIntersections.length > 0) : "assess edge that ends in a crossing can't both up and down"; + assessAboveIntersections = abovePlane.findCrossings(planetModel, assessEdge.plane, assessEdge.startPlane, assessEdge.endPlane); + assessBelowIntersections = belowPlane.findCrossings(planetModel, assessEdge.plane, assessEdge.startPlane, assessEdge.endPlane); - if (assessAboveIntersections.length == 0 && assessBelowIntersections.length == 0) { + if ((assessAboveIntersections == null || assessAboveIntersections.length == 0) && (assessBelowIntersections == null || assessBelowIntersections.length == 0)) { continue; } break; @@ -1073,7 +1078,7 @@ class GeoComplexPolygon extends GeoBasePolygon { // point where they hit the plane. This may be complicated by the 3D geometry; it may not be safe just to look at the endpoints of the edges // and make an assessment that way, since a single edge can intersect the plane at more than one point. - final boolean assessEdgeAbove = assessAboveIntersections.length > 0; + final boolean assessEdgeAbove = assessAboveIntersections != null && assessAboveIntersections.length > 0; if (assessEdgeAbove != edgeCrossesAbove) { crossingCount++; } @@ -1082,16 +1087,14 @@ class GeoComplexPolygon extends GeoBasePolygon { // Figure out if the crossing should be counted. // Does the crossing for this edge go up, or down? Or can't we tell? - final GeoPoint[] aboveIntersections = abovePlane.findIntersections(planetModel, edge.plane, edge.startPlane, edge.endPlane); - final GeoPoint[] belowIntersections = belowPlane.findIntersections(planetModel, edge.plane, edge.startPlane, edge.endPlane); - - assert !(aboveIntersections.length > 0 && belowIntersections.length > 0) : "edge that ends in a crossing can't both up and down"; + final GeoPoint[] aboveIntersections = abovePlane.findCrossings(planetModel, edge.plane, edge.startPlane, edge.endPlane); + final GeoPoint[] belowIntersections = belowPlane.findCrossings(planetModel, edge.plane, edge.startPlane, edge.endPlane); - if (aboveIntersections.length == 0 && belowIntersections.length == 0) { + if ((aboveIntersections == null || aboveIntersections.length == 0) && (belowIntersections == null || belowIntersections.length == 0)) { return; } - final boolean edgeCrossesAbove = aboveIntersections.length > 0; + final boolean edgeCrossesAbove = aboveIntersections != null && aboveIntersections.length > 0; // This depends on the previous edge that first departs from identicalness. Edge assessEdge = edge; @@ -1099,12 +1102,10 @@ class GeoComplexPolygon extends GeoBasePolygon { GeoPoint[] assessBelowIntersections; while (true) { assessEdge = assessEdge.next; - assessAboveIntersections = abovePlane.findIntersections(planetModel, assessEdge.plane, assessEdge.startPlane, assessEdge.endPlane); - assessBelowIntersections = belowPlane.findIntersections(planetModel, assessEdge.plane, assessEdge.startPlane, assessEdge.endPlane); - - assert !(assessAboveIntersections.length > 0 && assessBelowIntersections.length > 0) : "assess edge that ends in a crossing can't both up and down"; + assessAboveIntersections = abovePlane.findCrossings(planetModel, assessEdge.plane, assessEdge.startPlane, assessEdge.endPlane); + assessBelowIntersections = belowPlane.findCrossings(planetModel, assessEdge.plane, assessEdge.startPlane, assessEdge.endPlane); - if (assessAboveIntersections.length == 0 && assessBelowIntersections.length == 0) { + if (assessAboveIntersections != null && assessAboveIntersections.length == 0 && assessBelowIntersections != null && assessBelowIntersections.length == 0) { continue; } break; @@ -1121,7 +1122,7 @@ class GeoComplexPolygon extends GeoBasePolygon { // point where they hit the plane. This may be complicated by the 3D geometry; it may not be safe just to look at the endpoints of the edges // and make an assessment that way, since a single edge can intersect the plane at more than one point. - final boolean assessEdgeAbove = assessAboveIntersections.length > 0; + final boolean assessEdgeAbove = assessAboveIntersections != null && assessAboveIntersections.length > 0; if (assessEdgeAbove != edgeCrossesAbove) { crossingCount++; } @@ -1326,14 +1327,15 @@ class GeoComplexPolygon extends GeoBasePolygon { computeInsideOutside(); // Does the crossing for this edge go up, or down? Or can't we tell? - final GeoPoint[] insideTestPointPlaneIntersections = testPointInsidePlane.findIntersections(planetModel, edge.plane, edge.startPlane, edge.endPlane, insideTestPointCutoffPlane); - final GeoPoint[] insideTravelPlaneIntersections = travelInsidePlane.findIntersections(planetModel, edge.plane, edge.startPlane, edge.endPlane, insideTravelCutoffPlane); - final GeoPoint[] outsideTestPointPlaneIntersections = testPointOutsidePlane.findIntersections(planetModel, edge.plane, edge.startPlane, edge.endPlane); - final GeoPoint[] outsideTravelPlaneIntersections = travelOutsidePlane.findIntersections(planetModel, edge.plane, edge.startPlane, edge.endPlane); + final GeoPoint[] insideTestPointPlaneIntersections = testPointInsidePlane.findCrossings(planetModel, edge.plane, edge.startPlane, edge.endPlane, insideTestPointCutoffPlane); + final GeoPoint[] insideTravelPlaneIntersections = travelInsidePlane.findCrossings(planetModel, edge.plane, edge.startPlane, edge.endPlane, insideTravelCutoffPlane); + final GeoPoint[] outsideTestPointPlaneIntersections = testPointOutsidePlane.findCrossings(planetModel, edge.plane, edge.startPlane, edge.endPlane); + final GeoPoint[] outsideTravelPlaneIntersections = travelOutsidePlane.findCrossings(planetModel, edge.plane, edge.startPlane, edge.endPlane); - assert !(insideTestPointPlaneIntersections.length + insideTravelPlaneIntersections.length > 0 && outsideTestPointPlaneIntersections.length + outsideTravelPlaneIntersections.length > 0) : "edge that ends in a crossing can't both up and down"; - - if (insideTestPointPlaneIntersections.length + insideTravelPlaneIntersections.length == 0 && outsideTestPointPlaneIntersections.length + outsideTravelPlaneIntersections.length == 0) { + if ((insideTestPointPlaneIntersections == null || insideTestPointPlaneIntersections.length == 0) && + (insideTravelPlaneIntersections == null || insideTravelPlaneIntersections.length == 0) && + (outsideTestPointPlaneIntersections == null || outsideTestPointPlaneIntersections.length == 0) && + (outsideTravelPlaneIntersections == null || outsideTravelPlaneIntersections.length == 0)) { //System.err.println(" No inside or outside crossings found"); return; } @@ -1353,10 +1355,12 @@ class GeoComplexPolygon extends GeoBasePolygon { assessOutsideTestPointIntersections = testPointOutsidePlane.findIntersections(planetModel, assessEdge.plane, assessEdge.startPlane, assessEdge.endPlane); assessOutsideTravelIntersections = travelOutsidePlane.findIntersections(planetModel, assessEdge.plane, assessEdge.startPlane, assessEdge.endPlane); - // An edge can cross both outside and inside, because of the corner. But it can be considered to cross the inside ONLY if it crosses either of the inside edges. - //assert !(assessInsideTestPointIntersections.length + assessInsideTravelIntersections.length > 0 && assessOutsideTestPointIntersections.length + assessOutsideTravelIntersections.length > 0) : "assess edge that ends in a crossing can't both up and down"; - - if (assessInsideTestPointIntersections.length + assessInsideTravelIntersections.length == 0 && assessOutsideTestPointIntersections.length + assessOutsideTravelIntersections.length == 0) { + // If the assess edge is numerically identical to the edge we're trying to find the intersections with, there's not really a crossing, so count it as zero. + + if ((assessInsideTestPointIntersections == null || assessInsideTestPointIntersections.length == 0) && + (assessInsideTravelIntersections == null || assessInsideTravelIntersections.length == 0) && + (assessOutsideTestPointIntersections == null || assessOutsideTestPointIntersections.length == 0) && + (assessOutsideTravelIntersections == null || assessOutsideTravelIntersections.length == 0)) { continue; } break; @@ -1376,7 +1380,12 @@ class GeoComplexPolygon extends GeoBasePolygon { } else { otherCrossingPoints = testPointPlane.findCrossings(planetModel, assessEdge.plane, testPointCutoffPlane, testPointOtherCutoffPlane, assessEdge.startPlane, assessEdge.endPlane); } - + + if (otherCrossingPoints == null) { + // The assessEdge plane is the same as the travel plane. We consider this the same as "no crossing". + return; + } + // Look for a matching endpoint. If the other endpoint doesn't show up, it is either out of bounds (in which case the // transition won't be counted for that edge), or it is not a crossing for that edge (so, same conclusion). for (final GeoPoint otherCrossingPoint : otherCrossingPoints) { @@ -1393,7 +1402,8 @@ class GeoComplexPolygon extends GeoBasePolygon { // point where they hit the plane. This may be complicated by the 3D geometry; it may not be safe just to look at the endpoints of the edges // and make an assessment that way, since a single edge can intersect the plane at more than one point. - final boolean assessEdgeInside = assessInsideTestPointIntersections.length + assessInsideTravelIntersections.length > 0; + final boolean assessEdgeInside = (assessInsideTestPointIntersections != null && assessInsideTestPointIntersections.length > 0) || + (assessInsideTravelIntersections != null && assessInsideTravelIntersections.length > 0); if (assessEdgeInside != edgeCrossesInside) { //System.err.println(" Incrementing crossing count"); crossingCount++; @@ -1405,6 +1415,8 @@ class GeoComplexPolygon extends GeoBasePolygon { //System.err.println(" Crossing point = edge.endPoint"); // Figure out if the crossing should be counted. computeInsideOutside(); + + // If the assess edge is numerically identical to the edge we're trying to find the intersections with, there's not really a crossing, so count it as zero. // Does the crossing for this edge go up, or down? Or can't we tell? final GeoPoint[] insideTestPointPlaneIntersections = testPointInsidePlane.findIntersections(planetModel, edge.plane, edge.startPlane, edge.endPlane, insideTestPointCutoffPlane); @@ -1413,14 +1425,17 @@ class GeoComplexPolygon extends GeoBasePolygon { final GeoPoint[] outsideTravelPlaneIntersections = travelOutsidePlane.findIntersections(planetModel, edge.plane, edge.startPlane, edge.endPlane); // An edge can cross both outside and inside, because of the corner. But it can be considered to cross the inside ONLY if it crosses either of the inside edges. - //assert !(insideTestPointPlaneIntersections.length + insideTravelPlaneIntersections.length > 0 && outsideTestPointPlaneIntersections.length + outsideTravelPlaneIntersections.length > 0) : "edge that ends in a crossing can't go both up and down: insideTestPointPlaneIntersections: "+insideTestPointPlaneIntersections.length+" insideTravelPlaneIntersections: "+insideTravelPlaneIntersections.length+" outsideTestPointPlaneIntersections: "+outsideTestPointPlaneIntersections.length+" outsideTravelPlaneIntersections: "+outsideTravelPlaneIntersections.length; - if (insideTestPointPlaneIntersections.length + insideTravelPlaneIntersections.length == 0 && outsideTestPointPlaneIntersections.length + outsideTravelPlaneIntersections.length == 0) { + if ((insideTestPointPlaneIntersections == null || insideTestPointPlaneIntersections.length == 0) && + (insideTravelPlaneIntersections == null || insideTravelPlaneIntersections.length == 0) && + (outsideTestPointPlaneIntersections == null || outsideTestPointPlaneIntersections.length == 0) && + (outsideTravelPlaneIntersections == null || outsideTravelPlaneIntersections.length == 0)) { //System.err.println(" No inside or outside crossings found"); return; } - final boolean edgeCrossesInside = insideTestPointPlaneIntersections.length + insideTravelPlaneIntersections.length > 0; + final boolean edgeCrossesInside = (insideTestPointPlaneIntersections !=null && insideTestPointPlaneIntersections.length > 0) || + (insideTravelPlaneIntersections != null && insideTravelPlaneIntersections.length > 0); // This depends on the previous edge that first departs from identicalness. Edge assessEdge = edge; @@ -1435,9 +1450,10 @@ class GeoComplexPolygon extends GeoBasePolygon { assessOutsideTestPointIntersections = testPointOutsidePlane.findIntersections(planetModel, assessEdge.plane, assessEdge.startPlane, assessEdge.endPlane); assessOutsideTravelIntersections = travelOutsidePlane.findIntersections(planetModel, assessEdge.plane, assessEdge.startPlane, assessEdge.endPlane); - assert !(assessInsideTestPointIntersections.length + assessInsideTravelIntersections.length > 0 && assessOutsideTestPointIntersections.length + assessOutsideTravelIntersections.length > 0) : "assess edge that ends in a crossing can't both up and down"; - - if (assessInsideTestPointIntersections.length + assessInsideTravelIntersections.length == 0 && assessOutsideTestPointIntersections.length + assessOutsideTravelIntersections.length == 0) { + if ((assessInsideTestPointIntersections == null || assessInsideTestPointIntersections.length == 0) && + (assessInsideTravelIntersections == null || assessInsideTravelIntersections.length == 0) && + (assessOutsideTestPointIntersections == null || assessOutsideTestPointIntersections.length == 0) && + (assessOutsideTravelIntersections == null || assessOutsideTravelIntersections.length == 0)) { continue; } break; @@ -1454,7 +1470,8 @@ class GeoComplexPolygon extends GeoBasePolygon { // point where they hit the plane. This may be complicated by the 3D geometry; it may not be safe just to look at the endpoints of the edges // and make an assessment that way, since a single edge can intersect the plane at more than one point. - final boolean assessEdgeInside = assessInsideTestPointIntersections.length + assessInsideTravelIntersections.length > 0; + final boolean assessEdgeInside = (assessInsideTestPointIntersections !=null && assessInsideTestPointIntersections.length > 0) || + (assessInsideTravelIntersections != null && assessInsideTravelIntersections.length > 0); if (assessEdgeInside != edgeCrossesInside) { //System.err.println(" Incrementing crossing count"); crossingCount++;