From commits-return-100539-archive-asf-public=cust-asf.ponee.io@lucene.apache.org Mon Apr 23 11:57:58 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 D1D29180634 for ; Mon, 23 Apr 2018 11:57:57 +0200 (CEST) Received: (qmail 50832 invoked by uid 500); 23 Apr 2018 09:57:56 -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 50823 invoked by uid 99); 23 Apr 2018 09:57:56 -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; Mon, 23 Apr 2018 09:57:56 +0000 Received: by git1-us-west.apache.org (ASF Mail Server at git1-us-west.apache.org, from userid 33) id BE8C6E38BB; Mon, 23 Apr 2018 09:57:56 +0000 (UTC) Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: ivera@apache.org To: commits@lucene.apache.org Message-Id: <0a2509cf646d4127b1d2e6c6e47e9d72@git.apache.org> X-Mailer: ASF-Git Admin Mailer Subject: lucene-solr:branch_6x: LUCENE-8266: Detect bogus tiles when creating a standard polygon and throw a TileException Date: Mon, 23 Apr 2018 09:57:56 +0000 (UTC) Repository: lucene-solr Updated Branches: refs/heads/branch_6x 422ef65f0 -> 7026095f6 LUCENE-8266: Detect bogus tiles when creating a standard polygon and throw a TileException Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/7026095f Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/7026095f Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/7026095f Branch: refs/heads/branch_6x Commit: 7026095f61a4b36daf83b5d468baf99d226ac858 Parents: 422ef65 Author: Ignacio Vera Authored: Mon Apr 23 11:55:36 2018 +0200 Committer: Ignacio Vera Committed: Mon Apr 23 11:55:36 2018 +0200 ---------------------------------------------------------------------- lucene/CHANGES.txt | 3 + .../spatial3d/geom/GeoPolygonFactory.java | 20 +++++-- .../lucene/spatial3d/geom/GeoPolygonTest.java | 61 +++++++++++++++++++- 3 files changed, 79 insertions(+), 5 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/7026095f/lucene/CHANGES.txt ---------------------------------------------------------------------- diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt index 534f3df..2a7c353 100644 --- a/lucene/CHANGES.txt +++ b/lucene/CHANGES.txt @@ -43,6 +43,9 @@ New Features Bug Fixes +* LUCENE-8266: Detect bogus tiles when creating a standard polygon + and throw a TileException. (Ignacio Vera) + * LUCENE-8236: Filter duplicated points when creating GeoPath shapes to avoid creation of bogus planes. (Ignacio Vera) http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/7026095f/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPolygonFactory.java ---------------------------------------------------------------------- diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPolygonFactory.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPolygonFactory.java index 0bbae80..af5d8ef 100755 --- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPolygonFactory.java +++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPolygonFactory.java @@ -1237,14 +1237,14 @@ public class GeoPolygonFactory { break; } final Edge newLastEdge = edgeBuffer.getNext(lastEdge); + if (Plane.arePointsCoplanar(lastEdge.startPoint, lastEdge.endPoint, newLastEdge.endPoint)) { + break; + } // Planes that are almost identical cannot be properly handled by the standard polygon logic. Detect this case and, if found, // give up on the tiling -- we'll need to create a large poly instead. if (lastEdge.plane.isFunctionallyIdentical(newLastEdge.plane)) { throw new TileException("Two adjacent edge planes are effectively parallel despite filtering; give up on tiling"); } - if (Plane.arePointsCoplanar(lastEdge.startPoint, lastEdge.endPoint, newLastEdge.endPoint)) { - break; - } if (isWithin(newLastEdge.endPoint, includedEdges)) { //System.out.println(" maybe can extend to next edge"); // Found a candidate for extension. But do some other checks first. Basically, we need to know if we construct a polygon @@ -1308,6 +1308,11 @@ public class GeoPolygonFactory { if (Plane.arePointsCoplanar(newFirstEdge.startPoint, newFirstEdge.endPoint, firstEdge.endPoint)) { break; } + // Planes that are almost identical cannot be properly handled by the standard polygon logic. Detect this case and, if found, + // give up on the tiling -- we'll need to create a large poly instead. + if (firstEdge.plane.isFunctionallyIdentical(newFirstEdge.plane)) { + throw new TileException("Two adjacent edge planes are effectively parallel despite filtering; give up on tiling"); + } if (isWithin(newFirstEdge.startPoint, includedEdges)) { //System.out.println(" maybe can extend to previous edge"); // Found a candidate for extension. But do some other checks first. Basically, we need to know if we construct a polygon @@ -1387,6 +1392,10 @@ public class GeoPolygonFactory { // has no contents, so we generate no polygon. return false; } + + if (firstEdge.plane.isFunctionallyIdentical(lastEdge.plane)) { + throw new TileException("Two adjacent edge planes are effectively parallel despite filtering; give up on tiling"); + } // Now look for completely planar points. This too is a degeneracy condition that we should // return "false" for. @@ -1407,7 +1416,10 @@ public class GeoPolygonFactory { // Build the return edge (internal, of course) final SidedPlane returnSidedPlane = new SidedPlane(firstEdge.endPoint, false, firstEdge.startPoint, lastEdge.endPoint); final Edge returnEdge = new Edge(firstEdge.startPoint, lastEdge.endPoint, returnSidedPlane, true); - + if (returnEdge.plane.isFunctionallyIdentical(lastEdge.plane) || + returnEdge.plane.isFunctionallyIdentical(firstEdge.plane)) { + throw new TileException("Two adjacent edge planes are effectively parallel despite filtering; give up on tiling"); + } // Build point list and edge list final List edges = new ArrayList(includedEdges.size()); returnIsInternal = true; http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/7026095f/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 09ae776..3eafb5a 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 @@ -1626,5 +1626,64 @@ shape: final GeoPoint point = new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(2.104316138623836E-4), Geo3DUtil.fromDegrees(1.413E-321)); assertTrue(polygon.isWithin(point) == largePolygon.isWithin(point)); } - + + @Test + public void testLUCENE8266_case1() { + //POLYGON((-6.35093158794635E-11 -4.965517818537545E-11,0.0 3.113E-321,-60.23538585411111 18.46706692248612, 162.37100340450482 -25.988383239097754,-6.35093158794635E-11 -4.965517818537545E-11)) + final List points = new ArrayList<>(); + points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-4.965517818537545E-11), Geo3DUtil.fromDegrees(-6.35093158794635E-11))); + points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(3.113E-321), Geo3DUtil.fromDegrees(0.0))); + points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(18.46706692248612), Geo3DUtil.fromDegrees(-60.23538585411111))); + points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-25.988383239097754), Geo3DUtil.fromDegrees(162.37100340450482))); + 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(-179.99999999999974 2.4432260684194717E-11) + final GeoPoint point = new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(2.4432260684194717E-11), Geo3DUtil.fromDegrees(-179.99999999999974)); + assertFalse(polygon.isWithin(point)); + assertFalse(largePolygon.isWithin(point)); + } + + @Test + public void testLUCENE8266_case2() { + //POLYGON((7.885596306952593 -42.25131029665893,1.5412637897085604 -6.829581354691802,34.03338913004999 27.583811665797796,0.0 5.7E-322,-8.854664233194431E-12 7.132883127401669E-11,-40.20723013296905 15.679563923063258,7.885596306952593 -42.25131029665893)) + final List points = new ArrayList<>(); + points.add(new GeoPoint(PlanetModel.WGS84, Geo3DUtil.fromDegrees(-42.25131029665893), Geo3DUtil.fromDegrees(7.885596306952593))); + points.add(new GeoPoint(PlanetModel.WGS84, Geo3DUtil.fromDegrees(-6.829581354691802), Geo3DUtil.fromDegrees(1.5412637897085604))); + points.add(new GeoPoint(PlanetModel.WGS84, Geo3DUtil.fromDegrees(27.583811665797796), Geo3DUtil.fromDegrees(34.03338913004999))); + points.add(new GeoPoint(PlanetModel.WGS84, Geo3DUtil.fromDegrees(5.7E-322), Geo3DUtil.fromDegrees(0.0))); + points.add(new GeoPoint(PlanetModel.WGS84, Geo3DUtil.fromDegrees(7.132883127401669E-11), Geo3DUtil.fromDegrees( -8.854664233194431E-12))); + points.add(new GeoPoint(PlanetModel.WGS84, Geo3DUtil.fromDegrees(15.679563923063258), Geo3DUtil.fromDegrees(-40.20723013296905))); + final GeoPolygonFactory.PolygonDescription description = new GeoPolygonFactory.PolygonDescription(points); + final GeoPolygon polygon = GeoPolygonFactory.makeGeoPolygon(PlanetModel.WGS84, description); + final GeoPolygon largePolygon = GeoPolygonFactory.makeLargeGeoPolygon(PlanetModel.WGS84, Collections.singletonList(description)); + + //POINT(-179.99999999999983 -8.474427850967216E-12) + final GeoPoint point = new GeoPoint(PlanetModel.WGS84, Geo3DUtil.fromDegrees(-8.474427850967216E-12), Geo3DUtil.fromDegrees(-179.99999999999983)); + assertFalse(polygon.isWithin(point)); + assertFalse(largePolygon.isWithin(point)); + } + + @Test + public void testLUCENE8266_case3() { + //POLYGON((-98.38897266664411 7.286530349760722,-169.07259176302364 -7.410435277740526,8E-123,-179.9999999999438 -1.298973436027626E-10,66.2759716901292 -52.84327866278771,-98.38897266664411 7.286530349760722)) + final List points = new ArrayList<>(); + points.add(new GeoPoint(PlanetModel.WGS84, Geo3DUtil.fromDegrees(7.286530349760722), Geo3DUtil.fromDegrees(-98.38897266664411))); + points.add(new GeoPoint(PlanetModel.WGS84, Geo3DUtil.fromDegrees(-7.410435277740526), Geo3DUtil.fromDegrees(-169.07259176302364))); + points.add(new GeoPoint(PlanetModel.WGS84, Geo3DUtil.fromDegrees(-8.136646215781618E-123), Geo3DUtil.fromDegrees(-180.0))); + points.add(new GeoPoint(PlanetModel.WGS84, Geo3DUtil.fromDegrees(-1.298973436027626E-10), Geo3DUtil.fromDegrees(-179.9999999999438))); + points.add(new GeoPoint(PlanetModel.WGS84, Geo3DUtil.fromDegrees(-52.84327866278771), Geo3DUtil.fromDegrees(66.2759716901292))); + final GeoPolygonFactory.PolygonDescription description = new GeoPolygonFactory.PolygonDescription(points); + final GeoPolygon polygon = GeoPolygonFactory.makeGeoPolygon(PlanetModel.WGS84, description); + final GeoPolygon largePolygon = GeoPolygonFactory.makeLargeGeoPolygon(PlanetModel.WGS84, Collections.singletonList(description)); + + //POINT(3.4279315107728157E-122 2.694960611439045E-11) + final GeoPoint point = new GeoPoint(PlanetModel.WGS84, Geo3DUtil.fromDegrees(2.694960611439045E-11), Geo3DUtil.fromDegrees(3.4279315107728157E-122)); + assertFalse(polygon.isWithin(point)); + assertFalse(largePolygon.isWithin(point)); + } + + + }