You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by kw...@apache.org on 2018/03/24 15:04:42 UTC
lucene-solr:branch_7x: LUCENE-8220: Handle polygon tiling issues in a
more robust way.
Repository: lucene-solr
Updated Branches:
refs/heads/branch_7x bf33c0a4c -> e88066ab7
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/e88066ab
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/e88066ab
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/e88066ab
Branch: refs/heads/branch_7x
Commit: e88066ab7848d74d1da9d67f53fd5e3aff1a3412
Parents: bf33c0a
Author: Karl Wright <Da...@gmail.com>
Authored: Sat Mar 24 11:03:15 2018 -0400
Committer: Karl Wright <Da...@gmail.com>
Committed: Sat Mar 24 11:04:31 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/e88066ab/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/e88066ab/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);
+ }
}