You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by iv...@apache.org on 2021/11/29 10:06:11 UTC
[lucene] branch main updated: LUCENE-9538: Detect polygon self-intersections in the Tessellator (#428)
This is an automated email from the ASF dual-hosted git repository.
ivera pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/main by this push:
new 78c8d7b LUCENE-9538: Detect polygon self-intersections in the Tessellator (#428)
78c8d7b is described below
commit 78c8d7b7ea6aca2202c5eeffcc19e837279721c6
Author: Ignacio Vera <iv...@apache.org>
AuthorDate: Mon Nov 29 11:05:03 2021 +0100
LUCENE-9538: Detect polygon self-intersections in the Tessellator (#428)
Detect self-intersections so it can provide a more meaningful error to the users.
---
lucene/CHANGES.txt | 2 +
.../org/apache/lucene/document/LatLonShape.java | 25 ++--
.../java/org/apache/lucene/document/XYShape.java | 25 ++--
.../src/java/org/apache/lucene/geo/GeoUtils.java | 23 +++-
.../java/org/apache/lucene/geo/Tessellator.java | 135 +++++++++++++++++++--
.../lucene/document/BaseLatLonSpatialTestCase.java | 2 +-
.../lucene/document/BaseXYShapeTestCase.java | 2 +-
.../apache/lucene/document/TestLatLonShape.java | 26 ++--
.../org/apache/lucene/document/TestXYShape.java | 2 +-
.../org/apache/lucene/geo/TestTessellator.java | 84 +++++++++----
.../java/org/apache/lucene/geo/GeoTestUtil.java | 4 +-
.../lucene/geo/lucene-9538-invalid.geojson.gz | Bin 0 -> 23077 bytes
12 files changed, 257 insertions(+), 73 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 72dfba0..624d721 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -62,6 +62,8 @@ Improvements
* LUCENE-10262: Lift up restrictions for navigating PointValues#PointTree
added in LUCENE-9820 (Ignacio Vera)
+* LUCENE-9538: Detect polygon self-intersections in the Tessellator. (Ignacio Vera)
+
Optimizations
---------------------
diff --git a/lucene/core/src/java/org/apache/lucene/document/LatLonShape.java b/lucene/core/src/java/org/apache/lucene/document/LatLonShape.java
index a35af35..8b18461 100644
--- a/lucene/core/src/java/org/apache/lucene/document/LatLonShape.java
+++ b/lucene/core/src/java/org/apache/lucene/document/LatLonShape.java
@@ -19,7 +19,6 @@ package org.apache.lucene.document;
import static org.apache.lucene.geo.GeoEncodingUtils.encodeLatitude;
import static org.apache.lucene.geo.GeoEncodingUtils.encodeLongitude;
-import java.util.ArrayList;
import java.util.List;
import org.apache.lucene.document.ShapeField.QueryRelation; // javadoc
import org.apache.lucene.document.ShapeField.Triangle;
@@ -45,6 +44,8 @@ import org.apache.lucene.search.Query;
*
* <ul>
* <li>{@link #createIndexableFields(String, Polygon)} for indexing a geo polygon.
+ * <li>{@link #createIndexableFields(String, Polygon, boolean)} for indexing a geo polygon with
+ * the possibility of checking for self-intersections.
* <li>{@link #createIndexableFields(String, Line)} for indexing a geo linestring.
* <li>{@link #createIndexableFields(String, double, double)} for indexing a lat, lon geo point.
* <li>{@link #newBoxQuery newBoxQuery()} for matching geo shapes that have some {@link
@@ -69,15 +70,25 @@ public class LatLonShape {
// no instance:
private LatLonShape() {}
- /** create indexable fields for polygon geometry */
+ /** create indexable fields for polygon geometry. */
public static Field[] createIndexableFields(String fieldName, Polygon polygon) {
+ return createIndexableFields(fieldName, polygon, false);
+ }
+
+ /**
+ * create indexable fields for polygon geometry. If {@code checkSelfIntersections} is set to true,
+ * the validity of the provided polygon is checked with a small performance penalty.
+ */
+ public static Field[] createIndexableFields(
+ String fieldName, Polygon polygon, boolean checkSelfIntersections) {
// the lionshare of the indexing is done by the tessellator
- List<Tessellator.Triangle> tessellation = Tessellator.tessellate(polygon);
- List<Triangle> fields = new ArrayList<>();
- for (Tessellator.Triangle t : tessellation) {
- fields.add(new Triangle(fieldName, t));
+ List<Tessellator.Triangle> tessellation =
+ Tessellator.tessellate(polygon, checkSelfIntersections);
+ Triangle[] fields = new Triangle[tessellation.size()];
+ for (int i = 0; i < tessellation.size(); i++) {
+ fields[i] = new Triangle(fieldName, tessellation.get(i));
}
- return fields.toArray(new Field[fields.size()]);
+ return fields;
}
/** create indexable fields for line geometry */
diff --git a/lucene/core/src/java/org/apache/lucene/document/XYShape.java b/lucene/core/src/java/org/apache/lucene/document/XYShape.java
index 0392425..d52ff49 100644
--- a/lucene/core/src/java/org/apache/lucene/document/XYShape.java
+++ b/lucene/core/src/java/org/apache/lucene/document/XYShape.java
@@ -18,9 +18,8 @@ package org.apache.lucene.document;
import static org.apache.lucene.geo.XYEncodingUtils.encode;
-import java.util.ArrayList;
import java.util.List;
-import org.apache.lucene.document.ShapeField.QueryRelation; // javadoc
+import org.apache.lucene.document.ShapeField.QueryRelation;
import org.apache.lucene.document.ShapeField.Triangle;
import org.apache.lucene.geo.Tessellator;
import org.apache.lucene.geo.XYCircle;
@@ -43,6 +42,8 @@ import org.apache.lucene.search.Query;
*
* <ul>
* <li>{@link #createIndexableFields(String, XYPolygon)} for indexing a cartesian polygon.
+ * <li>{@link #createIndexableFields(String, XYPolygon, boolean)} for indexing a cartesian polygon
+ * with the possibility of checking for self-intersections.
* <li>{@link #createIndexableFields(String, XYLine)} for indexing a cartesian linestring.
* <li>{@link #createIndexableFields(String, float, float)} for indexing a x, y cartesian point.
* <li>{@link #newBoxQuery newBoxQuery()} for matching cartesian shapes that have some {@link
@@ -68,13 +69,23 @@ public class XYShape {
/** create indexable fields for cartesian polygon geometry */
public static Field[] createIndexableFields(String fieldName, XYPolygon polygon) {
+ return createIndexableFields(fieldName, polygon, false);
+ }
- List<Tessellator.Triangle> tessellation = Tessellator.tessellate(polygon);
- List<Triangle> fields = new ArrayList<>(tessellation.size());
- for (Tessellator.Triangle t : tessellation) {
- fields.add(new Triangle(fieldName, t));
+ /**
+ * create indexable fields for cartesian polygon geometry. If {@code checkSelfIntersections} is
+ * set to true, the validity of the provided polygon is checked with a small performance penalty.
+ */
+ public static Field[] createIndexableFields(
+ String fieldName, XYPolygon polygon, boolean checkSelfIntersections) {
+
+ List<Tessellator.Triangle> tessellation =
+ Tessellator.tessellate(polygon, checkSelfIntersections);
+ Triangle[] fields = new Triangle[tessellation.size()];
+ for (int i = 0; i < tessellation.size(); i++) {
+ fields[i] = new Triangle(fieldName, tessellation.get(i));
}
- return fields.toArray(new Field[fields.size()]);
+ return fields;
}
/** create indexable fields for cartesian line geometry */
diff --git a/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java b/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
index 52dd287..5542b3d 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
@@ -224,11 +224,24 @@ public final class GeoUtils {
double a2y,
double b2x,
double b2y) {
- if (orient(a2x, a2y, b2x, b2y, a1x, a1y) * orient(a2x, a2y, b2x, b2y, b1x, b1y) < 0
- && orient(a1x, a1y, b1x, b1y, a2x, a2y) * orient(a1x, a1y, b1x, b1y, b2x, b2y) < 0) {
- return true;
- }
- return false;
+ return orient(a2x, a2y, b2x, b2y, a1x, a1y) * orient(a2x, a2y, b2x, b2y, b1x, b1y) < 0
+ && orient(a1x, a1y, b1x, b1y, a2x, a2y) * orient(a1x, a1y, b1x, b1y, b2x, b2y) < 0;
+ }
+
+ /** uses orient method to compute whether two line overlap each other */
+ public static boolean lineOverlapLine(
+ double a1x,
+ double a1y,
+ double b1x,
+ double b1y,
+ double a2x,
+ double a2y,
+ double b2x,
+ double b2y) {
+ return orient(a2x, a2y, b2x, b2y, a1x, a1y) == 0
+ && orient(a2x, a2y, b2x, b2y, b1x, b1y) == 0
+ && orient(a1x, a1y, b1x, b1y, a2x, a2y) == 0
+ && orient(a1x, a1y, b1x, b1y, b2x, b2y) == 0;
}
/**
diff --git a/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java b/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
index da08467..0990dc6 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
@@ -18,6 +18,8 @@ package org.apache.lucene.geo;
import static org.apache.lucene.geo.GeoEncodingUtils.encodeLatitude;
import static org.apache.lucene.geo.GeoEncodingUtils.encodeLongitude;
+import static org.apache.lucene.geo.GeoUtils.lineCrossesLine;
+import static org.apache.lucene.geo.GeoUtils.lineOverlapLine;
import static org.apache.lucene.geo.GeoUtils.orient;
import java.util.ArrayList;
@@ -83,7 +85,7 @@ public final class Tessellator {
// No Instance:
private Tessellator() {}
- public static final List<Triangle> tessellate(final Polygon polygon) {
+ public static List<Triangle> tessellate(final Polygon polygon, boolean checkSelfIntersections) {
// Attempt to establish a doubly-linked list of the provided shell points (should be CCW, but
// this will correct);
// then filter instances of intersections.
@@ -121,18 +123,21 @@ public final class Tessellator {
sortByMorton(outerNode);
}
}
+ if (checkSelfIntersections) {
+ checkIntersection(outerNode, mortonOptimized);
+ }
// Calculate the tessellation using the doubly LinkedList.
List<Triangle> result =
earcutLinkedList(polygon, outerNode, new ArrayList<>(), State.INIT, mortonOptimized);
if (result.size() == 0) {
throw new IllegalArgumentException(
- "Unable to Tessellate shape [" + polygon + "]. Possible malformed shape detected.");
+ "Unable to Tessellate shape. Possible malformed shape detected.");
}
return result;
}
- public static final List<Triangle> tessellate(final XYPolygon polygon) {
+ public static List<Triangle> tessellate(final XYPolygon polygon, boolean checkSelfIntersections) {
// Attempt to establish a doubly-linked list of the provided shell points (should be CCW, but
// this will correct);
// then filter instances of intersections.0
@@ -170,12 +175,15 @@ public final class Tessellator {
sortByMorton(outerNode);
}
}
+ if (checkSelfIntersections) {
+ checkIntersection(outerNode, mortonOptimized);
+ }
// Calculate the tessellation using the doubly LinkedList.
List<Triangle> result =
earcutLinkedList(polygon, outerNode, new ArrayList<>(), State.INIT, mortonOptimized);
if (result.size() == 0) {
throw new IllegalArgumentException(
- "Unable to Tessellate shape [" + polygon + "]. Possible malformed shape detected.");
+ "Unable to Tessellate shape. Possible malformed shape detected.");
}
return result;
@@ -559,9 +567,7 @@ public final class Tessellator {
if (splitEarcut(polygon, currEar, tessellation, mortonOptimized) == false) {
// we could not process all points. Tessellation failed
throw new IllegalArgumentException(
- "Unable to Tessellate shape ["
- + polygon
- + "]. Possible malformed shape detected.");
+ "Unable to Tessellate shape. Possible malformed shape detected.");
}
break;
}
@@ -819,6 +825,121 @@ public final class Tessellator {
}
/** Computes if edge defined by a and b overlaps with a polygon edge * */
+ private static void checkIntersection(Node a, boolean isMorton) {
+ Node next = a.next;
+ do {
+ Node innerNext = next.next;
+ if (isMorton) {
+ mortonCheckIntersection(next, innerNext);
+ } else {
+ do {
+ checkIntersectionPoint(next, innerNext);
+ innerNext = innerNext.next;
+ } while (innerNext != next.previous);
+ }
+ next = next.next;
+ } while (next != a.previous);
+ }
+
+ /**
+ * Uses morton code for speed to determine whether or not and edge defined by a and b overlaps
+ * with a polygon edge
+ */
+ private static final void mortonCheckIntersection(final Node a, final Node b) {
+ // edge bbox (flip the bits so negative encoded values are < positive encoded values)
+ int minTX = StrictMath.min(a.x, a.next.x) ^ 0x80000000;
+ int minTY = StrictMath.min(a.y, a.next.y) ^ 0x80000000;
+ int maxTX = StrictMath.max(a.x, a.next.x) ^ 0x80000000;
+ int maxTY = StrictMath.max(a.y, a.next.y) ^ 0x80000000;
+
+ // z-order range for the current edge;
+ long minZ = BitUtil.interleave(minTX, minTY);
+ long maxZ = BitUtil.interleave(maxTX, maxTY);
+
+ // now make sure we don't have other points inside the potential ear;
+
+ // look for points inside edge in both directions
+ Node p = b.previousZ;
+ Node n = b.nextZ;
+ while (p != null
+ && Long.compareUnsigned(p.morton, minZ) >= 0
+ && n != null
+ && Long.compareUnsigned(n.morton, maxZ) <= 0) {
+ checkIntersectionPoint(p, a);
+ p = p.previousZ;
+ checkIntersectionPoint(n, a);
+ n = n.nextZ;
+ }
+
+ // first look for points inside the edge in decreasing z-order
+ while (p != null && Long.compareUnsigned(p.morton, minZ) >= 0) {
+ checkIntersectionPoint(p, a);
+ p = p.previousZ;
+ }
+ // then look for points in increasing z-order
+ while (n != null && Long.compareUnsigned(n.morton, maxZ) <= 0) {
+ checkIntersectionPoint(n, a);
+ n = n.nextZ;
+ }
+ }
+
+ private static void checkIntersectionPoint(final Node a, final Node b) {
+ if (a == b) {
+ return;
+ }
+
+ if (Math.max(a.getY(), a.next.getY()) <= Math.min(b.getY(), b.next.getY())
+ || Math.min(a.getY(), a.next.getY()) >= Math.max(b.getY(), b.next.getY())
+ || Math.max(a.getX(), a.next.getX()) <= Math.min(b.getX(), b.next.getX())
+ || Math.min(a.getX(), a.next.getX()) >= Math.max(b.getX(), b.next.getX())) {
+ return;
+ }
+
+ if (lineCrossesLine(
+ a.getX(),
+ a.getY(),
+ a.next.getX(),
+ a.next.getY(),
+ b.getX(),
+ b.getY(),
+ b.next.getX(),
+ b.next.getY())) {
+ // Line AB represented as a1x + b1y = c1
+ double a1 = a.next.getY() - a.getY();
+ double b1 = a.getX() - a.next.getX();
+ double c1 = a1 * (a.getX()) + b1 * (a.getY());
+
+ // Line CD represented as a2x + b2y = c2
+ double a2 = b.next.getY() - b.getY();
+ double b2 = b.getX() - b.next.getX();
+ double c2 = a2 * (b.getX()) + b2 * (b.getY());
+
+ double determinant = a1 * b2 - a2 * b1;
+
+ assert determinant != 0;
+
+ double x = (b2 * c1 - b1 * c2) / determinant;
+ double y = (a1 * c2 - a2 * c1) / determinant;
+
+ throw new IllegalArgumentException("Polygon self-intersection at lat=" + y + " lon=" + x);
+ }
+ if (a.isNextEdgeFromPolygon
+ && b.isNextEdgeFromPolygon
+ && lineOverlapLine(
+ a.getX(),
+ a.getY(),
+ a.next.getX(),
+ a.next.getY(),
+ b.getX(),
+ b.getY(),
+ b.next.getX(),
+ b.next.getY())) {
+ throw new IllegalArgumentException(
+ "Polygon ring self-intersection at lat=" + a.getY() + " lon=" + a.getX());
+ }
+ }
+
+ /** Computes if edge defined by a and b overlaps with a polygon edge * */
private static boolean isEdgeFromPolygon(final Node a, final Node b, final boolean isMorton) {
if (isMorton) {
return isMortonEdgeFromPolygon(a, b);
diff --git a/lucene/core/src/test/org/apache/lucene/document/BaseLatLonSpatialTestCase.java b/lucene/core/src/test/org/apache/lucene/document/BaseLatLonSpatialTestCase.java
index 7329732..483e9e3 100644
--- a/lucene/core/src/test/org/apache/lucene/document/BaseLatLonSpatialTestCase.java
+++ b/lucene/core/src/test/org/apache/lucene/document/BaseLatLonSpatialTestCase.java
@@ -200,7 +200,7 @@ public abstract class BaseLatLonSpatialTestCase extends BaseSpatialTestCase {
while (true) {
Polygon p = GeoTestUtil.nextPolygon();
try {
- Tessellator.tessellate(p);
+ Tessellator.tessellate(p, random().nextBoolean());
return p;
} catch (
@SuppressWarnings("unused")
diff --git a/lucene/core/src/test/org/apache/lucene/document/BaseXYShapeTestCase.java b/lucene/core/src/test/org/apache/lucene/document/BaseXYShapeTestCase.java
index b0aa484..b6dc4b8 100644
--- a/lucene/core/src/test/org/apache/lucene/document/BaseXYShapeTestCase.java
+++ b/lucene/core/src/test/org/apache/lucene/document/BaseXYShapeTestCase.java
@@ -226,7 +226,7 @@ public abstract class BaseXYShapeTestCase extends BaseSpatialTestCase {
while (true) {
XYPolygon p = ShapeTestUtil.nextPolygon();
try {
- Tessellator.tessellate(p);
+ Tessellator.tessellate(p, random().nextBoolean());
return p;
} catch (
@SuppressWarnings("unused")
diff --git a/lucene/core/src/test/org/apache/lucene/document/TestLatLonShape.java b/lucene/core/src/test/org/apache/lucene/document/TestLatLonShape.java
index 51cfef9..431d4a2 100644
--- a/lucene/core/src/test/org/apache/lucene/document/TestLatLonShape.java
+++ b/lucene/core/src/test/org/apache/lucene/document/TestLatLonShape.java
@@ -64,7 +64,7 @@ public class TestLatLonShape extends LuceneTestCase {
}
protected void addPolygonsToDoc(String field, Document doc, Polygon polygon) {
- Field[] fields = LatLonShape.createIndexableFields(field, polygon);
+ Field[] fields = LatLonShape.createIndexableFields(field, polygon, random().nextBoolean());
for (Field f : fields) {
doc.add(f);
}
@@ -304,14 +304,9 @@ public class TestLatLonShape extends LuceneTestCase {
new double[] {15d, -7.5d, -15d, -10d, 15d, 15d},
new double[] {180d, 180d, 176d, 174d, 176d, 180d});
- Field[] fields = LatLonShape.createIndexableFields("test", indexPoly1);
- for (Field f : fields) {
- doc.add(f);
- }
- fields = LatLonShape.createIndexableFields("test", indexPoly2);
- for (Field f : fields) {
- doc.add(f);
- }
+ addPolygonsToDoc("test", doc, indexPoly1);
+ addPolygonsToDoc("test", doc, indexPoly2);
+
w.addDocument(doc);
w.forceMerge(1);
@@ -369,14 +364,9 @@ public class TestLatLonShape extends LuceneTestCase {
new Polygon(
new double[] {-2d, -2d, 2d, 2d, -2d}, new double[] {-180d, -178d, -178d, -180d, -180d});
- Field[] fields = LatLonShape.createIndexableFields("test", indexPoly1);
- for (Field f : fields) {
- doc.add(f);
- }
- fields = LatLonShape.createIndexableFields("test", indexPoly2);
- for (Field f : fields) {
- doc.add(f);
- }
+ addPolygonsToDoc("test", doc, indexPoly1);
+ addPolygonsToDoc("test", doc, indexPoly2);
+
w.addDocument(doc);
w.forceMerge(1);
@@ -795,7 +785,7 @@ public class TestLatLonShape extends LuceneTestCase {
GeoEncodingUtils.encodeLongitude(polygon.getPolyLon(i)));
}
polygon = new Polygon(lats, lons);
- Tessellator.tessellate(polygon);
+ Tessellator.tessellate(polygon, random().nextBoolean());
break;
} catch (
@SuppressWarnings("unused")
diff --git a/lucene/core/src/test/org/apache/lucene/document/TestXYShape.java b/lucene/core/src/test/org/apache/lucene/document/TestXYShape.java
index 4ffbe61..6952109 100644
--- a/lucene/core/src/test/org/apache/lucene/document/TestXYShape.java
+++ b/lucene/core/src/test/org/apache/lucene/document/TestXYShape.java
@@ -133,7 +133,7 @@ public class TestXYShape extends LuceneTestCase {
if (areBoxDisjoint(r1, r2)) {
p = toPolygon(r2);
try {
- Tessellator.tessellate(p);
+ Tessellator.tessellate(p, random.nextBoolean());
break;
} catch (
@SuppressWarnings("unused")
diff --git a/lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java b/lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java
index 742d92a..2c7686a 100644
--- a/lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java
+++ b/lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java
@@ -64,7 +64,7 @@ public class TestTessellator extends LuceneTestCase {
new double[] {-1.0, -1.0, 0.5, 1.0, 1.0, 0.5, -1.0},
new double[] {-2.0, -4.0, -3.5, -4.0, -2.0, -2.5, -2.0});
poly = new Polygon(poly.getPolyLats(), poly.getPolyLons(), inner, inner2);
- assertTrue(Tessellator.tessellate(poly).size() > 0);
+ assertTrue(Tessellator.tessellate(poly, random().nextBoolean()).size() > 0);
}
@Nightly
@@ -79,7 +79,7 @@ public class TestTessellator extends LuceneTestCase {
new double[] {-1.0, -1.0, 0.5, 1.0, 1.0, 0.5, -1.0},
new double[] {-2.0, -4.0, -3.5, -4.0, -2.0, -2.5, -2.0});
poly = new Polygon(poly.getPolyLats(), poly.getPolyLons(), inner, inner2);
- assertTrue(Tessellator.tessellate(poly).size() > 0);
+ assertTrue(Tessellator.tessellate(poly, random().nextBoolean()).size() > 0);
}
public void testLUCENE8454() throws ParseException {
@@ -99,7 +99,7 @@ public class TestTessellator extends LuceneTestCase {
+ "[[168.1652103335658, -29.3030088541673], [168.16605788758287, -29.446580625201833], [168.16556735186845, -29.303245228857072], [168.165381, -29.303246], [168.16537977124085, -29.303008170411644], [168.1652103335658, -29.3030088541673]], "
+ "[[168.02088551865063, -29.647294313012004], [168.02133932508806, -29.811843292379823], [168.02135614030843, -29.811843274349446], [168.021356, -29.811809], [168.02162340579383, -29.811807949652078], [168.02088551865063, -29.647294313012004]]]}";
Polygon[] polygons = Polygon.fromGeoJSON(geoJson);
- List<Tessellator.Triangle> result = Tessellator.tessellate(polygons[0]);
+ List<Tessellator.Triangle> result = Tessellator.tessellate(polygons[0], random().nextBoolean());
assertEquals(result.size(), 84);
}
@@ -120,25 +120,31 @@ public class TestTessellator extends LuceneTestCase {
+ "[[168.71121460687698,-31.795031659971823],[168.71136127361123,-31.79503081865431],[168.71038567290682,-31.657182838382653],[168.71121460687698,-31.795031659971823]],"
+ "[[167.81624041598312,-31.53023516975434],[167.81634270442586,-31.530235525706665],[167.81676369867318,-31.434841665952604],[167.81624041598312,-31.53023516975434]]]}";
Polygon[] polygons = Polygon.fromGeoJSON(geoJson);
- List<Tessellator.Triangle> result = Tessellator.tessellate(polygons[0]);
+ List<Tessellator.Triangle> result = Tessellator.tessellate(polygons[0], random().nextBoolean());
assertEquals(113, result.size());
}
- public void testInvalidPolygon() throws Exception {
+ public void testInvalidPolygonIntersects() throws Exception {
String wkt = "POLYGON((0 0, 1 1, 0 1, 1 0, 0 0))";
Polygon polygon = (Polygon) SimpleWKTShapeParser.parse(wkt);
- expectThrows(
- IllegalArgumentException.class,
- () -> {
- Tessellator.tessellate(polygon);
- });
+ IllegalArgumentException ex =
+ expectThrows(IllegalArgumentException.class, () -> Tessellator.tessellate(polygon, true));
+ assertEquals("Polygon self-intersection at lat=0.5 lon=0.5", ex.getMessage());
}
- public void testLUCENE8550() throws Exception {
+ public void testInvalidPolygonOverlap() throws Exception {
+ // holes are equal
String wkt =
- "POLYGON((24.04725 59.942,24.04825 59.94125,24.04875 59.94125,24.04875 59.94175,24.048 59.9425,24.0475 59.94275,24.0465 59.94225,24.046 59.94225,24.04575 59.9425,24.04525 59.94225,24.04725 59.942))";
+ "POLYGON((6.0373903 52.0927095, 6.0363363 52.0924929, 6.0364421 52.0925414, 6.0366551 52.0927136, 6.0367463 52.092781, 6.0370682 52.0929958, 6.0372052 52.093085, 6.0373191 52.0931397, 6.037441 52.0931853, 6.0387158 52.0935294, 6.0388509 52.093564, 6.0388904 52.093572, 6.03894 52.0935172, 6.0389929 52.093481, 6.0390607 52.0934904, 6.0395233 52.0936092, 6.0397184 52.0936688, 6.0398596 52.0937371, 6.0399905 52.0938164, 6.0401399 52.0939142, 6.0402279 52.0939553, 6.0403145 52.0939837 [...]
+ + " 6.0438704 52.0947948, 6.0438877 52.0948026, 6.0439294 52.0948214, 6.0440239 52.0948431, 6.0440735 52.0948507, 6.0441791 52.0948543, 6.045512 52.0947949, 6.0455192 52.0948216, 6.0456981 52.0947986, 6.0459013 52.0947863, 6.0460089 52.0947857, 6.0461408 52.0948108, 6.0462669 52.0948578, 6.0463578 52.0949239, 6.0463764 52.0949825, 6.0463582 52.0950124, 6.0463968 52.0950234, 6.0463915 52.0950928, 6.0473354 52.0963349, 6.0485817 52.0963608, 6.0490603 52.0962177, 6.0489671 52.09 [...]
+ + " 6.0415155 52.0936271, 6.0413498 52.093569, 6.040999 52.0934704, 6.0406499 52.0933945, 6.040265 52.0933135, 6.0401695 52.0926941, 6.0401431 52.092505, 6.0393746 52.0924531, 6.0392555 52.0924338, 6.039146 52.0923841, 6.0390625 52.0923275, 6.0389748 52.0922443, 6.0378985 52.0913116, 6.0376887 52.0914018, 6.0375636 52.0914061, 6.037535 52.0914026, 6.037483 52.0913363, 6.0374139 52.0912876, 6.037277 52.0912639, 6.0370897 52.091257, 6.0370336 52.0913821, 6.0368773 52.0915326, 6 [...]
+ + " 6.0360358 52.0920367, 6.0359538 52.0920908, 6.035886 52.0921313, 6.0358394 52.0921889, 6.0358354 52.0922414, 6.035836 52.0922822, 6.0358481 52.0923161, 6.0358538 52.0923315, 6.0358873 52.0923605, 6.0376211 52.0927082, 6.0379741 52.0927953, 6.0379461 52.0928399, 6.0376294 52.0927647, 6.0373903 52.0927095), "
+ + " (6.0391557 52.0929189, 6.0388667 52.0928373, 6.0387045 52.0928107, 6.038578 52.0927855, 6.0384897 52.0927195, 6.0384626 52.0927036, 6.0384412 52.0926911, 6.0382642 52.0926086, 6.0380309 52.092529, 6.0377877 52.0924683, 6.0377571 52.0924499, 6.0377263 52.0924189, 6.037857 52.0923747, 6.0383203 52.0923097, 6.0385012 52.0922528, 6.0385416 52.0922588, 6.0385632 52.0923458, 6.0386452 52.0924386, 6.0387875 52.0925001, 6.0391495 52.0926998, 6.0393437 52.0928496, 6.0393774 52.092 [...]
+ + " (6.0377263 52.0924189, 6.0377571 52.0924499, 6.0377877 52.0924683, 6.0380309 52.092529, 6.0382642 52.0926086, 6.0384412 52.0926911, 6.0384626 52.0927036, 6.0384897 52.0927195, 6.038578 52.0927855, 6.0387045 52.0928107, 6.0388667 52.0928373, 6.0391557 52.0929189, 6.039246 52.0929349, 6.0393239 52.0929308, 6.0393715 52.092914, 6.0393774 52.0928918, 6.0393437 52.0928496, 6.0391495 52.0926998, 6.0387875 52.0925001, 6.0386452 52.0924386, 6.0385632 52.0923458, 6.0385416 52.0922 [...]
Polygon polygon = (Polygon) SimpleWKTShapeParser.parse(wkt);
- assertTrue(Tessellator.tessellate(polygon).size() == 8);
+ IllegalArgumentException ex =
+ expectThrows(IllegalArgumentException.class, () -> Tessellator.tessellate(polygon, true));
+ assertEquals("Polygon ring self-intersection at lat=52.0924189 lon=6.0377263", ex.getMessage());
}
public void testLUCENE8559() throws Exception {
@@ -302,7 +308,11 @@ public class TestTessellator extends LuceneTestCase {
"POLYGON((14.1989238 40.8274753, 14.1990593 40.8275004, 14.1991793 40.8275226, 14.1993451 40.8275478, 14.1993761 40.8275525, 14.1994599 40.8275746, 14.1996909 40.8276174, 14.1996769 40.8276728, 14.1993975 40.8277665, "
+ "14.1993717 40.8277752, 14.1992074 40.8278304, 14.1990929 40.8278688, 14.1989635 40.8279122, 14.1988594 40.8276864, 14.1989238 40.8274753), (14.1993717 40.8277752, 14.1993975 40.8277665, 14.1995864 40.8276576, 14.1994599 40.8275746,"
+ " 14.1993761 40.8275525, 14.1993451 40.8275478, 14.1993073 40.8276704, 14.1993717 40.8277752), (14.1990593 40.8275004, 14.1989907 40.8276889, 14.1990929 40.8278688, 14.1992074 40.8278304, 14.1991335 40.8276763, 14.1991793 40.8275226, 14.1990593 40.8275004))";
- checkPolygon(wkt);
+ Polygon polygon = (Polygon) SimpleWKTShapeParser.parse(wkt);
+ IllegalArgumentException ex =
+ expectThrows(IllegalArgumentException.class, () -> Tessellator.tessellate(polygon, true));
+ assertEquals(
+ "Polygon ring self-intersection at lat=40.8278688 lon=14.1990929", ex.getMessage());
}
public void testComplexPolygon18() throws Exception {
@@ -362,9 +372,7 @@ public class TestTessellator extends LuceneTestCase {
Polygon polygon = (Polygon) SimpleWKTShapeParser.parse(wkt);
expectThrows(
IllegalArgumentException.class,
- () -> {
- Tessellator.tessellate(polygon);
- });
+ () -> Tessellator.tessellate(polygon, random().nextBoolean()));
}
public void testComplexPolygon25() throws Exception {
@@ -375,9 +383,7 @@ public class TestTessellator extends LuceneTestCase {
Polygon polygon = (Polygon) SimpleWKTShapeParser.parse(wkt);
expectThrows(
IllegalArgumentException.class,
- () -> {
- Tessellator.tessellate(polygon);
- });
+ () -> Tessellator.tessellate(polygon, random().nextBoolean()));
}
public void testComplexPolygon26() throws Exception {
@@ -394,7 +400,8 @@ public class TestTessellator extends LuceneTestCase {
+ "((6.9731576 51.6249947,6.9731361 51.6250664,6.9731161 51.6251037,6.9731022 51.6250803,6.9731277 51.62502,6.9731576 51.6249947)))";
Polygon[] polygons = (Polygon[]) SimpleWKTShapeParser.parse(wkt);
for (Polygon polygon : polygons) {
- List<Tessellator.Triangle> tessellation = Tessellator.tessellate(polygon);
+ List<Tessellator.Triangle> tessellation =
+ Tessellator.tessellate(polygon, random().nextBoolean());
assertTrue(tessellation.size() > 0);
}
}
@@ -646,7 +653,8 @@ public class TestTessellator extends LuceneTestCase {
public void testComplexPolygon40() throws Exception {
String wkt = GeoTestUtil.readShape("lucene-9251.wkt.gz");
Polygon polygon = (Polygon) SimpleWKTShapeParser.parse(wkt);
- List<Tessellator.Triangle> tessellation = Tessellator.tessellate(polygon);
+ List<Tessellator.Triangle> tessellation =
+ Tessellator.tessellate(polygon, random().nextBoolean());
// calculate the area of big polygons have numerical error
assertEquals(area(polygon), area(tessellation), 1e-12);
for (Tessellator.Triangle t : tessellation) {
@@ -668,7 +676,8 @@ public class TestTessellator extends LuceneTestCase {
String geoJson = GeoTestUtil.readShape("lucene-9417.geojson.gz");
Polygon[] polygons = Polygon.fromGeoJSON(geoJson);
for (int i = 0; i < polygons.length; i++) {
- List<Tessellator.Triangle> tessellation = Tessellator.tessellate(polygons[i]);
+ List<Tessellator.Triangle> tessellation =
+ Tessellator.tessellate(polygons[i], random().nextBoolean());
// calculate the area of big polygons have numerical error
assertEquals(area(polygons[i]), area(tessellation), 1e-11);
for (Tessellator.Triangle t : tessellation) {
@@ -687,16 +696,41 @@ public class TestTessellator extends LuceneTestCase {
+ "(-88.3245325358123 41.9306419084828,-88.3245478066552 41.9305086556331,-88.3245658060855 41.930351580587,-88.3242368660096 41.9303327977821,-88.3242200926128 41.9304905242189,-88.324206161464 41.9306215207536,-88.3245325358123 41.9306419084828),"
+ "(-88.3236767661893 41.9307089429871,-88.3237008716322 41.930748885445,-88.323876104365 41.9306891087739,-88.324063438129 41.9306252050871,-88.3239244290607 41.930399373909,-88.3237349076233 41.9304653056436,-88.3235653339759 41.9305242981369,-88.3236767661893 41.9307089429871))";
Polygon polygon = (Polygon) SimpleWKTShapeParser.parse(wkt);
- List<Tessellator.Triangle> tessellation = Tessellator.tessellate(polygon);
+ List<Tessellator.Triangle> tessellation =
+ Tessellator.tessellate(polygon, random().nextBoolean());
assertEquals(area(polygon), area(tessellation), 1e-11);
for (Tessellator.Triangle t : tessellation) {
checkTriangleEdgesFromPolygon(polygon, t);
}
}
+ public void testComplexPolygon44() throws Exception {
+ String geoJson = GeoTestUtil.readShape("lucene-9538-invalid.geojson.gz");
+ Polygon[] polygons = Polygon.fromGeoJSON(geoJson);
+ for (int i = 0; i < polygons.length; i++) {
+ if (i == 21) {
+ final Polygon illegalPolygon = polygons[i];
+ IllegalArgumentException ex =
+ expectThrows(
+ IllegalArgumentException.class, () -> Tessellator.tessellate(illegalPolygon, true));
+ assertEquals(
+ "Polygon self-intersection at lat=34.21165542666664 lon=-83.88787058666672",
+ ex.getMessage());
+ } else {
+ List<Tessellator.Triangle> tessellation =
+ Tessellator.tessellate(polygons[i], random().nextBoolean());
+ assertEquals(area(polygons[i]), area(tessellation), 0.0);
+ for (Tessellator.Triangle t : tessellation) {
+ checkTriangleEdgesFromPolygon(polygons[i], t);
+ }
+ }
+ }
+ }
+
private void checkPolygon(String wkt) throws Exception {
Polygon polygon = (Polygon) SimpleWKTShapeParser.parse(wkt);
- List<Tessellator.Triangle> tessellation = Tessellator.tessellate(polygon);
+ List<Tessellator.Triangle> tessellation =
+ Tessellator.tessellate(polygon, random().nextBoolean());
assertEquals(area(polygon), area(tessellation), 0.0);
for (Tessellator.Triangle t : tessellation) {
checkTriangleEdgesFromPolygon(polygon, t);
diff --git a/lucene/test-framework/src/java/org/apache/lucene/geo/GeoTestUtil.java b/lucene/test-framework/src/java/org/apache/lucene/geo/GeoTestUtil.java
index 7a3f8ab..42540fe 100644
--- a/lucene/test-framework/src/java/org/apache/lucene/geo/GeoTestUtil.java
+++ b/lucene/test-framework/src/java/org/apache/lucene/geo/GeoTestUtil.java
@@ -797,7 +797,9 @@ public class GeoTestUtil {
is = new GZIPInputStream(is);
}
BufferedReader reader = new BufferedReader(new InputStreamReader(is, StandardCharsets.UTF_8));
- return reader.readLine();
+ StringBuilder builder = new StringBuilder();
+ reader.lines().forEach(s -> builder.append(s));
+ return builder.toString();
}
}
}
diff --git a/lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-9538-invalid.geojson.gz b/lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-9538-invalid.geojson.gz
new file mode 100644
index 0000000..a96e143
Binary files /dev/null and b/lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-9538-invalid.geojson.gz differ