From commits-return-100176-archive-asf-public=cust-asf.ponee.io@lucene.apache.org Tue Apr 10 02:14:23 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 85D5C180645 for ; Tue, 10 Apr 2018 02:14:22 +0200 (CEST) Received: (qmail 24974 invoked by uid 500); 10 Apr 2018 00:14:21 -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 24965 invoked by uid 99); 10 Apr 2018 00:14:21 -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, 10 Apr 2018 00:14:21 +0000 Received: by git1-us-west.apache.org (ASF Mail Server at git1-us-west.apache.org, from userid 33) id 2435FDFB0D; Tue, 10 Apr 2018 00:14:21 +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 Date: Tue, 10 Apr 2018 00:14:21 -0000 Message-Id: <849af73d8c3a46ccb0a74ac976e24575@git.apache.org> X-Mailer: ASF-Git Admin Mailer Subject: [1/2] lucene-solr:master: LUCENE-8245: Don't rely only on 'intersects' code to determine whether we should bother looking for crossings; also see if endpoints lie on travel planes. Repository: lucene-solr Updated Branches: refs/heads/master a12d39887 -> 1cd859713 LUCENE-8245: Don't rely only on 'intersects' code to determine whether we should bother looking for crossings; also see if endpoints lie on travel 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/9bd6d130 Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/9bd6d130 Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/9bd6d130 Branch: refs/heads/master Commit: 9bd6d1305c8bbccf2f3a22079a523b483325e9eb Parents: bd8fe72 Author: Karl Wright Authored: Mon Apr 9 20:13:12 2018 -0400 Committer: Karl Wright Committed: Mon Apr 9 20:13:12 2018 -0400 ---------------------------------------------------------------------- .../spatial3d/geom/GeoComplexPolygon.java | 46 +++++++++++++++----- .../org/apache/lucene/spatial3d/geom/Plane.java | 5 ++- .../lucene/spatial3d/geom/GeoPolygonTest.java | 17 ++++++++ 3 files changed, 55 insertions(+), 13 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/9bd6d130/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 f64755c..5c3521c 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 @@ -935,8 +935,10 @@ class GeoComplexPolygon extends GeoBasePolygon { // 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[] planeCrossings = plane.findIntersections(planetModel, edge.plane, bound, edge.startPlane, edge.endPlane); if (planeCrossings != null && planeCrossings.length == 0) { - // No actual crossing - return true; + // Sometimes on the hairy edge an intersection will be missed. This check finds those. + if (!plane.evaluateIsZero(edge.startPoint) && !plane.evaluateIsZero(edge.endPoint)) { + return true; + } } // Determine crossings of this edge against all inside/outside planes. There's no further need to look at the actual travel plane itself. @@ -1021,8 +1023,10 @@ class GeoComplexPolygon extends GeoBasePolygon { // 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[] planeCrossings = plane.findIntersections(planetModel, edge.plane, bound1, bound2, edge.startPlane, edge.endPlane); if (planeCrossings != null && planeCrossings.length == 0) { - // No actual crossing - return true; + // Sometimes on the hairy edge an intersection will be missed. This check finds those. + if (!plane.evaluateIsZero(edge.startPoint) && !plane.evaluateIsZero(edge.endPoint)) { + return true; + } } // Determine crossings of this edge against all inside/outside planes. There's no further need to look at the actual travel plane itself. @@ -1248,8 +1252,6 @@ class GeoComplexPolygon extends GeoBasePolygon { } seenEdges.add(edge); - //System.out.println("Considering edge "+(edge.startPoint)+" -> "+(edge.endPoint)); - // We've never seen this edge before. Evaluate it in the context of inner and outer planes. computeInsideOutside(); @@ -1273,14 +1275,36 @@ class GeoComplexPolygon extends GeoBasePolygon { 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) { final GeoPoint[] testPointCrossings = testPointPlane.findIntersections(planetModel, edge.plane, testPointCutoffPlane, testPointOtherCutoffPlane, edge.startPlane, edge.endPlane); if (testPointCrossings != null && testPointCrossings.length == 0) { - return true; + // 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. + if (!travelPlane.evaluateIsZero(edge.startPoint) && !travelPlane.evaluateIsZero(edge.endPoint) && + !testPointPlane.evaluateIsZero(edge.startPoint) && !testPointPlane.evaluateIsZero(edge.endPoint)) { + return true; + } } } + + /* + System.out.println( + " start point travel dist="+travelPlane.evaluate(edge.startPoint)+"; end point travel dist="+travelPlane.evaluate(edge.endPoint)); + System.out.println( + " start point travel above dist="+travelAbovePlane.evaluate(edge.startPoint)+"; end point travel above dist="+travelAbovePlane.evaluate(edge.endPoint)); + System.out.println( + " start point travel below dist="+travelBelowPlane.evaluate(edge.startPoint)+"; end point travel below dist="+travelBelowPlane.evaluate(edge.endPoint)); + System.out.println( + " start point testpoint dist="+testPointPlane.evaluate(edge.startPoint)+"; end point testpoint dist="+testPointPlane.evaluate(edge.endPoint)); + System.out.println( + " start point testpoint above dist="+testPointAbovePlane.evaluate(edge.startPoint)+"; end point testpoint above dist="+testPointAbovePlane.evaluate(edge.endPoint)); + System.out.println( + " start point testpoint below dist="+testPointBelowPlane.evaluate(edge.startPoint)+"; end point testpoint below dist="+testPointBelowPlane.evaluate(edge.endPoint)); + */ // 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); @@ -1294,13 +1318,13 @@ class GeoComplexPolygon extends GeoBasePolygon { if (travelInnerCrossings != null) { for (final GeoPoint crossing : travelInnerCrossings) { - //System.out.println(" Travel inner point "+crossing); + //System.out.println(" Travel inner point "+crossing+"; edgeplane="+edge.plane.evaluate(crossing)+"; travelInsidePlane="+travelInsidePlane.evaluate(crossing)+"; edgestartplane="+edge.startPlane.evaluate(crossing)+"; edgeendplane="+edge.endPlane.evaluate(crossing)); countingHash.add(crossing); } } if (testPointInnerCrossings != null) { for (final GeoPoint crossing : testPointInnerCrossings) { - //System.out.println(" Test point inner point "+crossing); + //System.out.println(" Test point inner point "+crossing+"; edgeplane="+edge.plane.evaluate(crossing)+"; testPointInsidePlane="+testPointInsidePlane.evaluate(crossing)+"; edgestartplane="+edge.startPlane.evaluate(crossing)+"; edgeendplane="+edge.endPlane.evaluate(crossing)); countingHash.add(crossing); } } @@ -1310,13 +1334,13 @@ class GeoComplexPolygon extends GeoBasePolygon { countingHash.clear(); if (travelOuterCrossings != null) { for (final GeoPoint crossing : travelOuterCrossings) { - //System.out.println(" Travel outer point "+crossing); + //System.out.println(" Travel outer point "+crossing+"; edgeplane="+edge.plane.evaluate(crossing)+"; travelOutsidePlane="+travelOutsidePlane.evaluate(crossing)+"; edgestartplane="+edge.startPlane.evaluate(crossing)+"; edgeendplane="+edge.endPlane.evaluate(crossing)); countingHash.add(crossing); } } if (testPointOuterCrossings != null) { for (final GeoPoint crossing : testPointOuterCrossings) { - //System.out.println(" Test point outer point "+crossing); + //System.out.println(" Test point outer point "+crossing+"; edgeplane="+edge.plane.evaluate(crossing)+"; testPointOutsidePlane="+testPointOutsidePlane.evaluate(crossing)+"; edgestartplane="+edge.startPlane.evaluate(crossing)+"; edgeendplane="+edge.endPlane.evaluate(crossing)); countingHash.add(crossing); } } http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/9bd6d130/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Plane.java ---------------------------------------------------------------------- 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 34a2fce..b47cffd 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 @@ -23,8 +23,9 @@ package org.apache.lucene.spatial3d.geom; * @lucene.experimental */ public class Plane extends Vector { - /** For plane envelopes, we need a small distance that can't lead to numerical confusion. */ - public final static double MINIMUM_PLANE_OFFSET = MINIMUM_RESOLUTION * 1.1; + /** For plane envelopes, we need a small distance that can't lead to numerical confusion. This spacing is large enough to + * avoid numerical confusion, but still permit all points within the envelope to belong to one or another plane. */ + public final static double MINIMUM_PLANE_OFFSET = MINIMUM_RESOLUTION * 2.0; /** An array with no points in it */ public final static GeoPoint[] NO_POINTS = new GeoPoint[0]; /** An array with no bounds in it */ http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/9bd6d130/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 d1e6688..ee2217d 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 @@ -1501,5 +1501,22 @@ shape: final GeoPoint point = new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-6.782152464351765E-11), Geo3DUtil.fromDegrees(91.60559215160585)); assertTrue(polygon.isWithin(point) == largePolygon.isWithin(point)); } + + @Test + public void testLUCENE8245() { + //POLYGON((-70.19447784626787 -83.117346007187,0.0 2.8E-322,-139.99870438810106 7.994601469571884,-143.14292702670522 -18.500141088122664,-158.7373186858464 -35.42942085357812,-70.19447784626787 -83.117346007187)) + final List points = new ArrayList<>(); + points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-83.117346007187), Geo3DUtil.fromDegrees(-70.19447784626787))); + points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(2.8E-322), Geo3DUtil.fromDegrees(0.0))); + points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(7.994601469571884), Geo3DUtil.fromDegrees(-139.99870438810106))); + points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-18.500141088122664), Geo3DUtil.fromDegrees(-143.14292702670522))); + points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-35.42942085357812), Geo3DUtil.fromDegrees(-158.7373186858464))); + final GeoPolygonFactory.PolygonDescription description = new GeoPolygonFactory.PolygonDescription(points); + final GeoPolygon polygon = GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE, description); + final GeoPolygon largePolygon = GeoPolygonFactory.makeLargeGeoPolygon(PlanetModel.SPHERE, Collections.singletonList(description)); + //POINT(-1.91633079336513E-11 12.282452091883385) + final GeoPoint point = new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(12.282452091883385), Geo3DUtil.fromDegrees(-1.91633079336513E-11)); + assertTrue(polygon.isWithin(point) == largePolygon.isWithin(point)); + } }