From commits-return-100192-archive-asf-public=cust-asf.ponee.io@lucene.apache.org Tue Apr 10 12:59:06 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 86ADF18072F for ; Tue, 10 Apr 2018 12:59:05 +0200 (CEST) Received: (qmail 15164 invoked by uid 500); 10 Apr 2018 10:59:04 -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 15132 invoked by uid 99); 10 Apr 2018 10:59:04 -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 10:59:04 +0000 Received: by git1-us-west.apache.org (ASF Mail Server at git1-us-west.apache.org, from userid 33) id 05436E0910; Tue, 10 Apr 2018 10:59:04 +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: <77029d3ef9dc42c0a15b12a9b81c0fa3@git.apache.org> X-Mailer: ASF-Git Admin Mailer Subject: lucene-solr:branch_6x: LUCENE-8245: Add more tests that demonstrate problems with GeoComplexPolygon. Date: Tue, 10 Apr 2018 10:59:04 +0000 (UTC) Repository: lucene-solr Updated Branches: refs/heads/branch_6x 95435d4e7 -> 3a0aef1fe LUCENE-8245: Add more tests that demonstrate problems with 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/3a0aef1f Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/3a0aef1f Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/3a0aef1f Branch: refs/heads/branch_6x Commit: 3a0aef1fe91039b397e4b023238fd0e0296459a3 Parents: 95435d4 Author: Karl Wright Authored: Tue Apr 10 06:57:13 2018 -0400 Committer: Karl Wright Committed: Tue Apr 10 06:58:56 2018 -0400 ---------------------------------------------------------------------- .../lucene/spatial3d/geom/GeoPolygonTest.java | 57 +++++++- .../geom/RandomGeo3dShapeGenerator.java | 2 +- .../spatial3d/geom/RandomGeoPolygonTest.java | 141 +++++++++++++++++++ 3 files changed, 198 insertions(+), 2 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/3a0aef1f/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 ee2217d..46750d4 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 @@ -21,12 +21,14 @@ import java.util.List; import java.util.BitSet; import java.util.Collections; +import org.apache.lucene.util.LuceneTestCase; + import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertFalse; import static org.junit.Assert.assertTrue; -public class GeoPolygonTest { +public class GeoPolygonTest extends LuceneTestCase { @Test public void testPolygonPointFiltering() { @@ -1518,5 +1520,58 @@ shape: final GeoPoint point = new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(12.282452091883385), Geo3DUtil.fromDegrees(-1.91633079336513E-11)); assertTrue(polygon.isWithin(point) == largePolygon.isWithin(point)); } + + @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 points = new ArrayList<>(); + points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-26.833721534785912), Geo3DUtil.fromDegrees(5.512285089810178))); + points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-16.085163683089583), Geo3DUtil.fromDegrees(12.13983320542565))); + points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-9.167423203860656), Geo3DUtil.fromDegrees(4.868755337835201))); + points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-5.261747514529465), Geo3DUtil.fromDegrees(0.0))); + points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-21.362181191487718), Geo3DUtil.fromDegrees(-15.696549288211289))); + 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(-6.994273817216168E-11 -1.6915596606526662E-292) + final GeoPoint point = new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-1.6915596606526662E-292), Geo3DUtil.fromDegrees(-6.994273817216168E-11)); + assertTrue(polygon.isWithin(point) == largePolygon.isWithin(point)); + } + + @Test + @AwaitsFix(bugUrl="https://issues.apache.org/jira/browse/LUCENE-8245") + public void testLUCENE8245_case3() { + //POLYGON((144.76249846857021 8.828705232593283,166.00162989841027 -8.5E-322,157.03429484830787 64.92565566857392,108.64696979831984 39.10241638996957,102.54234512410089 20.471658760034586,144.76249846857021 8.828705232593283)) + final List points = new ArrayList<>(); + points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(8.828705232593283), Geo3DUtil.fromDegrees(144.76249846857021))); + points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-8.5E-322), Geo3DUtil.fromDegrees(166.00162989841027))); + points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(64.92565566857392), Geo3DUtil.fromDegrees(157.03429484830787))); + points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(39.10241638996957), Geo3DUtil.fromDegrees(108.64696979831984))); + points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(20.471658760034586), Geo3DUtil.fromDegrees(102.54234512410089))); + 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.9999999999998 7.627654408067997E-11) + final GeoPoint point = new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(7.627654408067997E-11), Geo3DUtil.fromDegrees(179.9999999999998)); + assertTrue(polygon.isWithin(point) == largePolygon.isWithin(point)); + } + + @Test + public void testLUCENE8245_case4() { + //POLYGON((-3.728795716978514 -10.354090605548162,-137.97868338527985 0.05602723926521642,-113.87317441507611 -76.2471400450585,-162.64032677742279 -89.9999999991684,179.9999999999998 -89.99999999999997,-3.728795716978514 -10.354090605548162)) + final List points = new ArrayList<>(); + points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-10.354090605548162), Geo3DUtil.fromDegrees(-3.728795716978514))); + points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(0.05602723926521642), Geo3DUtil.fromDegrees(-137.97868338527985))); + points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-76.2471400450585), Geo3DUtil.fromDegrees(-113.87317441507611))); + points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-89.9999999991684), Geo3DUtil.fromDegrees(-162.64032677742279))); + points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-89.99999999999997), Geo3DUtil.fromDegrees(179.9999999999998))); + 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.2862855990004445E-10 -39.178517830976105) + final GeoPoint point = new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-39.178517830976105), Geo3DUtil.fromDegrees(-1.2862855990004445E-10)); + assertTrue(polygon.isWithin(point) == largePolygon.isWithin(point)); + } } http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/3a0aef1f/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/RandomGeo3dShapeGenerator.java ---------------------------------------------------------------------- diff --git a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/RandomGeo3dShapeGenerator.java b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/RandomGeo3dShapeGenerator.java index cf3713c..ca0c829 100644 --- a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/RandomGeo3dShapeGenerator.java +++ b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/RandomGeo3dShapeGenerator.java @@ -897,7 +897,7 @@ public class RandomGeo3dShapeGenerator extends LuceneTestCase { * @param points The points to order. * @return The list of ordered points anti-clockwise. */ - private List orderPoints(List points) { + protected List orderPoints(List points) { double x = 0; double y = 0; double z = 0; http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/3a0aef1f/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/RandomGeoPolygonTest.java ---------------------------------------------------------------------- diff --git a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/RandomGeoPolygonTest.java b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/RandomGeoPolygonTest.java index beac8c7..fc7e2ad 100644 --- a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/RandomGeoPolygonTest.java +++ b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/RandomGeoPolygonTest.java @@ -17,11 +17,15 @@ package org.apache.lucene.spatial3d.geom; import java.util.ArrayList; +import java.util.Collections; import java.util.List; import com.carrotsearch.randomizedtesting.annotations.Repeat; +import com.carrotsearch.randomizedtesting.generators.BiasedNumbers; import org.junit.Test; +import static com.carrotsearch.randomizedtesting.RandomizedTest.randomDouble; + /** * Random test for polygons. */ @@ -84,4 +88,141 @@ public class RandomGeoPolygonTest extends RandomGeo3dShapeGenerator { GeoCompositePolygon polygon = (GeoCompositePolygon)GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE, points); assertTrue(polygon.size() == 3); } + + /** + * Test comparing different polygon technologies using random + * biased doubles. + */ + @Test + @AwaitsFix(bugUrl="https://issues.apache.org/jira/browse/LUCENE-8245") + @Repeat(iterations = 10) + public void testComparePolygons() { + final PlanetModel planetModel = randomPlanetModel(); + //Create polygon points using a reference point and a maximum distance to the point + final GeoPoint referencePoint = getBiasedPoint(planetModel); + final int n = random().nextInt(4) + 4; + final List points = new ArrayList<>(n); + final double maxDistance = random().nextDouble() * Math.PI; + for (int i = 0; i < n; i++) { + while(true) { + final double distance = BiasedNumbers.randomDoubleBetween(random(), 0, maxDistance);// random().nextDouble() * maxDistance; + final double bearing = random().nextDouble() * 2 * Math.PI; + GeoPoint p = planetModel.surfacePointOnBearing(referencePoint, distance, bearing); + if (!contains(p, points)) { + if (points.size() > 1 && Plane.arePointsCoplanar(points.get(points.size() -1), points.get(points.size() - 2), p)) { + continue; + } + points.add(p); + break; + } + } + } + //order points so we don't get crossing edges + final List orderedPoints = orderPoints(points); + //Comment out below to get clock-wise polygons + if (random().nextBoolean() && random().nextBoolean()) { + Collections.reverse(orderedPoints); + } + GeoPolygonFactory.PolygonDescription polygonDescription = new GeoPolygonFactory.PolygonDescription(orderedPoints); + GeoPolygon polygon = null; + try { + polygon = GeoPolygonFactory.makeGeoPolygon(planetModel, polygonDescription); + } catch(Exception e) { + StringBuilder buffer = new StringBuilder("Polygon failed to build with an exception:\n"); + buffer.append(points.toString()+ "\n"); + buffer.append("WKT:" + getWKT(orderedPoints)); + buffer.append(e.toString()); + fail(buffer.toString()); + } + if (polygon == null) { + StringBuilder buffer = new StringBuilder("Polygon failed to build:\n"); + buffer.append(points.toString()+ "\n"); + buffer.append("WKT:" + getWKT(orderedPoints)); + fail(buffer.toString()); + } + GeoPolygon largePolygon = null; + try { + largePolygon = GeoPolygonFactory.makeLargeGeoPolygon(planetModel, Collections.singletonList(polygonDescription)); + } catch(Exception e) { + StringBuilder buffer = new StringBuilder("Large polygon failed to build with an exception:\n"); + buffer.append(points.toString()+ "\n"); + buffer.append("WKT:" + getWKT(orderedPoints)); + buffer.append(e.toString()); + fail(buffer.toString()); + } + if (largePolygon == null) { + StringBuilder buffer = new StringBuilder("Large polygon failed to build:\n"); + buffer.append(points.toString()+ "\n"); + buffer.append("WKT:" + getWKT(orderedPoints)); + fail(buffer.toString()); + } + + for(int i=0;i<100000;i++) { + GeoPoint point = getBiasedPoint(planetModel); + boolean withIn1 = polygon.isWithin(point); + boolean withIn2 = largePolygon.isWithin(point); + StringBuilder buffer = new StringBuilder(); + if (withIn1 != withIn2) { + //NOTE: Sometimes we get errors when check point is near a polygon point. + // For the time being, we filter this errors. + double d1 = polygon.computeOutsideDistance(DistanceStyle.ARC, point); + double d2 = largePolygon.computeOutsideDistance(DistanceStyle.ARC, point); + if (d1 == 0 && d2 == 0) { + continue; + } + buffer = buffer.append("\nStandard polygon: " + polygon.toString() +"\n"); + buffer = buffer.append("\nLarge polygon: " + largePolygon.toString() +"\n"); + buffer = buffer.append("\nPoint: " + point.toString() +"\n"); + buffer.append("\nWKT: " + getWKT(orderedPoints)); + buffer.append("\nWKT: POINT(" + Math.toDegrees(point.getLongitude()) + " " + Math.toDegrees(point.getLatitude()) + ")\n"); + buffer.append("normal polygon: " +withIn1 + "\n"); + buffer.append("large polygon: " + withIn2 + "\n"); + } + assertTrue(buffer.toString(), withIn1 == withIn2); + } + //Not yet tested +// for(int i=0;i<100;i++) { +// GeoShape shape = randomGeoShape(randomShapeType(), planetModel); +// int rel1 = polygon.getRelationship(shape); +// int rel2 = largePolygon.getRelationship(shape); +// StringBuilder buffer = new StringBuilder(); +// if (rel1 != rel2) { +// buffer = buffer.append(polygon.toString() +"\n" + shape.toString() + "\n"); +// buffer.append("WKT: " + getWKT(orderedPoints) + "\n"); +// buffer.append("normal polygon: " + rel1 + "\n"); +// buffer.append("large polygon: " + rel2 + "\n"); +// } +// assertTrue(buffer.toString(), rel1 == rel2); +// } + } + + private GeoPoint getBiasedPoint(PlanetModel planetModel) { + double lat = BiasedNumbers.randomDoubleBetween(random(), 0, Math.PI / 2); + if (random().nextBoolean()) { + lat = (-1) * lat; + } + double lon = BiasedNumbers.randomDoubleBetween(random(), 0, Math.PI); + if (random().nextBoolean()) { + lon = (-1) * lon; + } + return new GeoPoint(planetModel, lat, lon); + } + + private String getWKT(List points) { + StringBuffer buffer = new StringBuffer("POLYGON(("); + for (GeoPoint point : points) { + buffer.append(Math.toDegrees(point.getLongitude()) + " " + Math.toDegrees(point.getLatitude()) + ","); + } + buffer.append(Math.toDegrees(points.get(0).getLongitude()) + " " + Math.toDegrees(points.get(0).getLatitude()) + "))\n"); + return buffer.toString(); + } + + private boolean contains(GeoPoint p, List points) { + for (GeoPoint point : points) { + if (point.isNumericallyIdentical(p)) { + return true; + } + } + return false; + } }