[Tessellator] Improve the checks that validate the diagonal between two polygon nodes (#12353)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 50229e1..150f298 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -182,6 +182,9 @@
* GITHUB#12291: Skip blank lines from stopwords list. (Jerry Chin)
+* GITHUB#12352: [Tessellator] Improve the checks that validate the diagonal between two polygon nodes so
+ the resulting polygons are valid counter clockwise polygons. (Ignacio Vera)
+
Other
---------------------
(No changes)
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 5d58357..937a26a 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
@@ -1090,17 +1090,22 @@
* Determines whether a diagonal between two polygon nodes lies within a polygon interior. (This
* determines the validity of the ray.) *
*/
- private static final boolean isValidDiagonal(final Node a, final Node b) {
- if (isVertexEquals(a, b)) {
- // If points are equal then use it if they are valid polygons
- return isCWPolygon(a, b);
+ private static boolean isValidDiagonal(final Node a, final Node b) {
+ if (a.next.idx == b.idx
+ || a.previous.idx == b.idx
+ // check next edges are locally visible
+ || isLocallyInside(a.previous, b) == false
+ || isLocallyInside(b.next, a) == false
+ // check polygons are CCW in both sides
+ || isCWPolygon(a, b) == false
+ || isCWPolygon(b, a) == false) {
+ return false;
}
- return a.next.idx != b.idx
- && a.previous.idx != b.idx
- && isLocallyInside(a, b)
+ if (isVertexEquals(a, b)) {
+ return true;
+ }
+ return isLocallyInside(a, b)
&& isLocallyInside(b, a)
- && isLocallyInside(a.previous, b)
- && isLocallyInside(b.next, a)
&& middleInsert(a, a.getX(), a.getY(), b.getX(), b.getY())
// make sure we don't introduce collinear lines
&& area(a.previous.getX(), a.previous.getY(), a.getX(), a.getY(), b.getX(), b.getY()) != 0
@@ -1114,7 +1119,7 @@
/** Determine whether the polygon defined between node start and node end is CW */
private static boolean isCWPolygon(final Node start, final Node end) {
// The polygon must be CW
- return (signedArea(start, end) < 0) ? true : false;
+ return signedArea(start, end) < 0;
}
/** Determine the signed area between node start and node end */
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 950772f..44c17b4 100644
--- a/lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java
+++ b/lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java
@@ -915,6 +915,28 @@
}
}
+ public void testComplexPolygon55() throws Exception {
+ String geoJson = GeoTestUtil.readShape("github-12352-1.geojson.gz");
+ Polygon[] polygons = Polygon.fromGeoJSON(geoJson);
+ for (Polygon polygon : polygons) {
+ List<Tessellator.Triangle> tessellation =
+ Tessellator.tessellate(polygon, random().nextBoolean());
+ assertEquals(area(polygon), area(tessellation), 0.0);
+ // don't check edges as it takes several minutes
+ }
+ }
+
+ public void testComplexPolygon56() throws Exception {
+ String geoJson = GeoTestUtil.readShape("github-12352-2.geojson.gz");
+ Polygon[] polygons = Polygon.fromGeoJSON(geoJson);
+ for (Polygon polygon : polygons) {
+ List<Tessellator.Triangle> tessellation =
+ Tessellator.tessellate(polygon, random().nextBoolean());
+ assertEquals(area(polygon), area(tessellation), 0.0);
+ // don't check edges as it takes several minutes
+ }
+ }
+
private static class TestCountingMonitor implements Tessellator.Monitor {
private int count = 0;
private int splitsStarted = 0;
diff --git a/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/github-12352-1.geojson.gz b/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/github-12352-1.geojson.gz
new file mode 100644
index 0000000..17a9a17
--- /dev/null
+++ b/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/github-12352-1.geojson.gz
Binary files differ
diff --git a/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/github-12352-2.geojson.gz b/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/github-12352-2.geojson.gz
new file mode 100644
index 0000000..eec620e
--- /dev/null
+++ b/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/github-12352-2.geojson.gz
Binary files differ
