lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kwri...@apache.org
Subject lucene-solr:branch_6x: LUCENE-8220: Handle polygon tiling issues in a more robust way.
Date Sat, 24 Mar 2018 15:05:14 GMT
Repository: lucene-solr
Updated Branches:
  refs/heads/branch_6x 1f3a8bc17 -> d5eb1088c


LUCENE-8220: Handle polygon tiling issues in a more robust way.


Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/d5eb1088
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/d5eb1088
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/d5eb1088

Branch: refs/heads/branch_6x
Commit: d5eb1088cd79fd915016c7ad9a7a6b3e53fc354c
Parents: 1f3a8bc
Author: Karl Wright <DaddyWri@gmail.com>
Authored: Sat Mar 24 11:03:15 2018 -0400
Committer: Karl Wright <DaddyWri@gmail.com>
Committed: Sat Mar 24 11:05:06 2018 -0400

----------------------------------------------------------------------
 .../spatial3d/geom/GeoPolygonFactory.java       | 71 ++++++++++++++------
 .../lucene/spatial3d/geom/GeoPolygonTest.java   | 47 +++++++++++++
 2 files changed, 99 insertions(+), 19 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/d5eb1088/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 90ab75f..769ddda 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
@@ -867,11 +867,19 @@ public class GeoPolygonFactory {
     
     // If what is left has any plane/point pair that is on the wrong side, we have to split
using one of the plane endpoints and the 
     // point in question.  This is best structured as a recursion, if detected.
+    
+    // Note: Any edge that fails means (I think!!) that there's another edge that will also
fail.
+    // This is because each point is included in two edges.
+    // So, when we look for a non-conforming edge, and we can find one (but can't use it),
we
+    // also can find another edge that we might be able to use instead.
+    // If this is true, it means we should continue when we find a bad edge we can't use
--
+    // but we need to keep track of this, and fail hard if we don't find a place to split.
+    boolean foundBadEdge = false;
     final Iterator<Edge> checkIterator = edgeBuffer.iterator();
     while (checkIterator.hasNext()) {
       final Edge checkEdge = checkIterator.next();
       final SidedPlane flippedPlane = new SidedPlane(checkEdge.plane);
-      // Now walk around again looking for points that fail
+      // Now walk around again looking for points that fail.
       final Iterator<Edge> confirmIterator = edgeBuffer.iterator();
       while (confirmIterator.hasNext()) {
         final Edge confirmEdge = confirmIterator.next();
@@ -888,6 +896,8 @@ public class GeoPolygonFactory {
           thePoint = null;
         }
         if (thePoint != null) {
+          // Note that we found a problem.
+          foundBadEdge = true;
           // thePoint is on the wrong side of the complementary plane.  That means we cannot
build a concave polygon, because the complement would not
           // be a legal convex polygon.
           // But we can take advantage of the fact that the distance between the edge and
thePoint is less than 180 degrees, and so we can split the
@@ -897,6 +907,9 @@ public class GeoPolygonFactory {
           // This should be the only problematic part of the polygon.
           // We know that thePoint is on the "wrong" side of the edge -- that is, it's on
the side that the
           // edge is pointing at.
+          
+          // The proposed tiling generates two new edges -- one from thePoint to the start
point of the edge we found, and the other from thePoint
+          // to the end point of the edge.  We generate that as a triangle convex polygon,
and tile the two remaining pieces.
           final List<GeoPoint> thirdPartPoints = new ArrayList<>(3);
           final BitSet thirdPartInternal = new BitSet();
           thirdPartPoints.add(checkEdge.startPoint);
@@ -905,9 +918,16 @@ public class GeoPolygonFactory {
           thirdPartInternal.set(1, true);
           thirdPartPoints.add(thePoint);
           assert checkEdge.plane.isWithin(thePoint) : "Point was on wrong side of complementary
plane, so must be on the right side of the non-complementary plane!";
-          final GeoPolygon convexPart = new GeoConvexPolygon(planetModel, thirdPartPoints,
holes, thirdPartInternal, true);
-          //System.out.println("convex part = "+convexPart);
-          rval.addShape(convexPart);
+          // Check for illegal argument using try/catch rather than pre-emptive check, since
it cuts down on building objects for a rare case
+          try {
+            final GeoPolygon convexPart = new GeoConvexPolygon(planetModel, thirdPartPoints,
holes, thirdPartInternal, true);
+            //System.out.println("convex part = "+convexPart);
+            rval.addShape(convexPart);
+          } catch (IllegalArgumentException e) {
+            // Eat this exception, assuming that it means the triangle is coplanar, and look
for
+            // other edges that will work instead.
+            break;
+          }
 
           // The part preceding the bad edge, back to thePoint, needs to be recursively
           // processed.  So, assemble what we need, which is basically a list of edges.
@@ -979,7 +999,10 @@ public class GeoPolygonFactory {
     if (makeConcavePolygon(planetModel, rval, seenConcave, edgeBuffer, holes, testPoint)
== false) {
       return false;
     }
-    
+    if (foundBadEdge) {
+      // Unaddressed bad edge
+      throw new IllegalArgumentException("Could not tile polygon; found a pathological coplanarity
that couldn't be addressed");
+    }
     return true;
   }
   
@@ -1036,23 +1059,33 @@ public class GeoPolygonFactory {
       edge = edgeBuffer.getNext(edge);
     }
     
-    if (testPoint != null && holes != null && holes.size() > 0) {
-      // No holes, for test
-      final GeoPolygon testPolygon = new GeoConcavePolygon(planetModel, points, null, internalEdges,
isInternal);
-      if (testPolygon.isWithin(testPoint)) {
-        return false;
+    // It is possible that the polygon is degenerate and all points are colinear.  If that's
the case, a concave polygon cannot be produced,
+    // in which case trying to construct it will generate IllegalArgumentExceptions here.

+    try {
+      if (testPoint != null && holes != null && holes.size() > 0) {
+        // No holes, for test
+        final GeoPolygon testPolygon = new GeoConcavePolygon(planetModel, points, null, internalEdges,
isInternal);
+        if (testPolygon.isWithin(testPoint)) {
+          return false;
+        }
       }
-    }
-    
-    final GeoPolygon realPolygon = new GeoConcavePolygon(planetModel, points, holes, internalEdges,
isInternal);
-    if (testPoint != null && (holes == null || holes.size() == 0)) {
-      if (realPolygon.isWithin(testPoint)) {
-        return false;
+      
+      final GeoPolygon realPolygon = new GeoConcavePolygon(planetModel, points, holes, internalEdges,
isInternal);
+      if (testPoint != null && (holes == null || holes.size() == 0)) {
+        if (realPolygon.isWithin(testPoint)) {
+          return false;
+        }
       }
+      
+      rval.addShape(realPolygon);
+      return true;
+    } catch (IllegalArgumentException e) {
+      final StringBuilder sb = new StringBuilder("Could not construct GeoConcavePolygon due
to colinearity of points: ");
+      for (final GeoPoint point : points) {
+        sb.append(" ").append(point.toString());
+      }
+      throw new IllegalArgumentException(sb.toString(), e);
     }
-    
-    rval.addShape(realPolygon);
-    return true;
   }
   
   /** Look for a convex polygon at the specified edge.  If we find it, create one and adjust
the edge buffer.

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/d5eb1088/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 2a5c073..c0806b3 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
@@ -22,6 +22,7 @@ import java.util.BitSet;
 import java.util.Collections;
 
 import org.junit.Test;
+import org.junit.Ignore;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertTrue;
@@ -1099,4 +1100,50 @@ shape:
     assertFalse(polygon.isWithin(PlanetModel.SPHERE.createSurfacePoint(-testPoint.x, testPoint.y,
-testPoint.z)));
     assertFalse(polygon.isWithin(PlanetModel.SPHERE.createSurfacePoint(-testPoint.x, -testPoint.y,
testPoint.z)));
   }
+
+  @Test
+  @Ignore
+  public void testCoplanarityTileConvex() throws Exception {
+    // This test has been disabled because it is possible that the polygon specified actually
intersects itself.
+    //POLYGON((24.39398 65.77519,24.3941 65.77498,24.394024 65.77497,24.393976 65.77495,24.393963
65.77493,24.394068 65.774925,24.394156 65.77495,24.394201 65.77495,24.394234 65.77496,24.394266
65.77498,24.394318 65.77498,24.39434 65.774956,24.394377 65.77495,24.394451 65.77494,24.394476
65.77495,24.394457 65.77498,24.39398 65.77519))"
+    List<GeoPoint> points = new ArrayList<>();
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(65.77519), Geo3DUtil.fromDegrees(24.39398)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(65.77498), Geo3DUtil.fromDegrees(24.3941)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(65.77497), Geo3DUtil.fromDegrees(24.394024)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(65.77495), Geo3DUtil.fromDegrees(24.393976)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(65.77493), Geo3DUtil.fromDegrees(24.393963)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(65.774925), Geo3DUtil.fromDegrees(24.394068)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(65.77495), Geo3DUtil.fromDegrees(24.394156)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(65.77495), Geo3DUtil.fromDegrees(24.394201)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(65.77496), Geo3DUtil.fromDegrees(24.394234)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(65.77498), Geo3DUtil.fromDegrees(24.394266)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(65.77498), Geo3DUtil.fromDegrees(24.394318)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(65.774956), Geo3DUtil.fromDegrees(24.39434)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(65.77495), Geo3DUtil.fromDegrees(24.394377)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(65.77494), Geo3DUtil.fromDegrees(24.394451)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(65.77495), Geo3DUtil.fromDegrees(24.394476)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(65.77498), Geo3DUtil.fromDegrees(24.394457)));
+    GeoCompositePolygon polygon = (GeoCompositePolygon)GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE,
points);
+    assertTrue(polygon != null);
+  }
+
+  public void testCoplanarityConcave() throws Exception {
+    //POLYGON((-52.18851 64.53777,-52.18853 64.53828,-52.18675 64.53829,-52.18676 64.53855,-52.18736
64.53855,-52.18737 64.53881,-52.18677 64.53881,-52.18683 64.54009,-52.18919 64.53981,-52.18916
64.53905,-52.19093 64.53878,-52.19148 64.53775,-52.18851 64.53777))
+    List<GeoPoint> points = new ArrayList<>();
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(64.53777), Geo3DUtil.fromDegrees(-52.18851)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(64.53828), Geo3DUtil.fromDegrees(-52.18853)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(64.53829), Geo3DUtil.fromDegrees(-52.18675)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(64.53855), Geo3DUtil.fromDegrees(-52.18676)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(64.53855), Geo3DUtil.fromDegrees(-52.18736)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(64.53881), Geo3DUtil.fromDegrees(-52.18737)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(64.53881), Geo3DUtil.fromDegrees(-52.18677)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(64.54009), Geo3DUtil.fromDegrees(-52.18683)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(64.53981), Geo3DUtil.fromDegrees(-52.18919)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(64.53905), Geo3DUtil.fromDegrees(-52.18916)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(64.53878), Geo3DUtil.fromDegrees(-52.19093)));
+    points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(64.53775), Geo3DUtil.fromDegrees(-52.19148)));
+    GeoPolygon polygon = GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE, points);
+    Collections.reverse(points);
+    polygon  = GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE, points);
+  }
 }


Mime
View raw message