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 2022/04/27 08:25:50 UTC
[lucene] branch branch_9x updated: LUCENE-10470: [Tessellator] Fix some failing polygons due to collinear edges (#756)
This is an automated email from the ASF dual-hosted git repository.
ivera pushed a commit to branch branch_9x
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/branch_9x by this push:
new 78ad4f7fa6b LUCENE-10470: [Tessellator] Fix some failing polygons due to collinear edges (#756)
78ad4f7fa6b is described below
commit 78ad4f7fa6b9da0d0ad1d96c4824f330a30a75b6
Author: Ignacio Vera <iv...@apache.org>
AuthorDate: Wed Apr 27 10:24:22 2022 +0200
LUCENE-10470: [Tessellator] Fix some failing polygons due to collinear edges (#756)
Check if polygon has been successfully tessellated before we fail (we are failing some valid
tessellations) and allow filtering edges that fold on top of the previous one
---
lucene/CHANGES.txt | 3 +
.../java/org/apache/lucene/geo/Tessellator.java | 18 +++--
.../org/apache/lucene/geo/TestTessellator.java | 85 +++++++++++++++++++--
.../lucene/tests/geo/lucene-10470-2.geojson.gz | Bin 0 -> 4007 bytes
.../lucene/tests/geo/lucene-10470-3.geojson.gz | Bin 0 -> 9513 bytes
.../lucene/tests/geo/lucene-10470.geojson.gz | Bin 0 -> 769 bytes
.../apache/lucene/tests/geo/lucene-10470.wkt.gz | Bin 0 -> 1201 bytes
7 files changed, 95 insertions(+), 11 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 0231f5fd815..7f276687532 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -93,6 +93,9 @@ Bug Fixes
* LUCENE-10529: Properly handle when TestTaxonomyFacetAssociations test case randomly indexes
no documents instead of throwing an NPE. (Greg Miller)
+* LUCENE-10470: Check if polygon has been successfully tessellated before we fail (we are failing some valid
+ tessellations) and allow filtering edges that fold on top of the previous one. (Ignacio Vera)
+
Build
---------------------
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 2ee19eaba96..4a6a8fc26a8 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
@@ -827,7 +827,8 @@ public final class Tessellator {
}
searchNode = searchNode.next;
} while (searchNode != start);
- return false;
+ // if there is some area left, we failed
+ return signedArea(start, start) == 0;
}
/** Computes if edge defined by a and b overlaps with a polygon edge * */
@@ -1102,6 +1103,12 @@ public final class Tessellator {
/** 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;
+ }
+
+ /** Determine the signed area between node start and node end */
+ private static double signedArea(final Node start, final Node end) {
Node next = start;
double windingSum = 0;
do {
@@ -1111,8 +1118,7 @@ public final class Tessellator {
next.getX(), next.getY(), next.next.getX(), next.next.getY(), end.getX(), end.getY());
next = next.next;
} while (next.next != end);
- // The polygon must be CW
- return (windingSum < 0) ? true : false;
+ return windingSum;
}
private static final boolean isLocallyInside(final Node a, final Node b) {
@@ -1291,10 +1297,12 @@ public final class Tessellator {
// we can filter points when:
// 1. they are the same
// 2.- each one starts and ends in each other
- // 3.- they are co-linear and both edges have the same value in .isNextEdgeFromPolygon
+ // 3.- they are collinear and both edges have the same value in .isNextEdgeFromPolygon
+ // 4.- they are collinear and second edge returns over the first edge
if (isVertexEquals(node, nextNode)
|| isVertexEquals(prevNode, nextNode)
- || (prevNode.isNextEdgeFromPolygon == node.isNextEdgeFromPolygon
+ || ((prevNode.isNextEdgeFromPolygon == node.isNextEdgeFromPolygon
+ || isPointInLine(prevNode, node, nextNode.getX(), nextNode.getY()))
&& area(
prevNode.getX(),
prevNode.getY(),
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 c4d52d9eba7..1f2220c3754 100644
--- a/lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java
+++ b/lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java
@@ -128,9 +128,18 @@ public class TestTessellator extends LuceneTestCase {
public void testInvalidPolygonIntersects() throws Exception {
String wkt = "POLYGON((0 0, 1 1, 0 1, 1 0, 0 0))";
Polygon polygon = (Polygon) SimpleWKTShapeParser.parse(wkt);
- IllegalArgumentException ex =
- expectThrows(IllegalArgumentException.class, () -> Tessellator.tessellate(polygon, true));
- assertEquals("Polygon self-intersection at lat=0.5 lon=0.5", ex.getMessage());
+ {
+ IllegalArgumentException ex =
+ expectThrows(IllegalArgumentException.class, () -> Tessellator.tessellate(polygon, true));
+ assertEquals("Polygon self-intersection at lat=0.5 lon=0.5", ex.getMessage());
+ }
+ {
+ IllegalArgumentException ex =
+ expectThrows(
+ IllegalArgumentException.class, () -> Tessellator.tessellate(polygon, false));
+ assertEquals(
+ "Unable to Tessellate shape. Possible malformed shape detected.", ex.getMessage());
+ }
}
public void testInvalidPolygonOverlap() throws Exception {
@@ -143,9 +152,19 @@ public class TestTessellator extends LuceneTestCase {
+ " (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);
- IllegalArgumentException ex =
- expectThrows(IllegalArgumentException.class, () -> Tessellator.tessellate(polygon, true));
- assertEquals("Polygon ring self-intersection at lat=52.0924189 lon=6.0377263", ex.getMessage());
+ {
+ IllegalArgumentException ex =
+ expectThrows(IllegalArgumentException.class, () -> Tessellator.tessellate(polygon, true));
+ assertEquals(
+ "Polygon ring self-intersection at lat=52.0924189 lon=6.0377263", ex.getMessage());
+ }
+ {
+ IllegalArgumentException ex =
+ expectThrows(
+ IllegalArgumentException.class, () -> Tessellator.tessellate(polygon, false));
+ assertEquals(
+ "Unable to Tessellate shape. Possible malformed shape detected.", ex.getMessage());
+ }
}
public void testLUCENE8559() throws Exception {
@@ -737,6 +756,60 @@ public class TestTessellator extends LuceneTestCase {
}
}
+ public void testComplexPolygon45() throws Exception {
+ String geoJson = GeoTestUtil.readShape("lucene-10470.geojson.gz");
+ Polygon[] polygons = Polygon.fromGeoJSON(geoJson);
+ for (int i = 0; i < polygons.length; 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) {
+ checkTriangleEdgesFromPolygon(polygons[i], t);
+ }
+ }
+ }
+
+ public void testComplexPolygon46() throws Exception {
+ String wkt = GeoTestUtil.readShape("lucene-10470.wkt.gz");
+ Polygon polygon = (Polygon) SimpleWKTShapeParser.parse(wkt);
+ List<Tessellator.Triangle> tessellation =
+ Tessellator.tessellate(polygon, random().nextBoolean());
+ // calculate the area of big polygons have numerical error
+ assertEquals(area(polygon), area(tessellation), 1e-11);
+ for (Tessellator.Triangle t : tessellation) {
+ checkTriangleEdgesFromPolygon(polygon, t);
+ }
+ }
+
+ public void testComplexPolygon47() throws Exception {
+ String geoJson = GeoTestUtil.readShape("lucene-10470-2.geojson.gz");
+ Polygon[] polygons = Polygon.fromGeoJSON(geoJson);
+ for (int i = 0; i < polygons.length; 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) {
+ checkTriangleEdgesFromPolygon(polygons[i], t);
+ }
+ }
+ }
+
+ @Nightly
+ public void testComplexPolygon48() throws Exception {
+ String geoJson = GeoTestUtil.readShape("lucene-10470-3.geojson.gz");
+ Polygon[] polygons = Polygon.fromGeoJSON(geoJson);
+ for (int i = 0; i < polygons.length; i++) {
+ List<Tessellator.Triangle> tessellation = Tessellator.tessellate(polygons[i], true);
+ // calculate the area of big polygons have numerical error
+ assertEquals(area(polygons[i]), area(tessellation), 1e-11);
+ 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 =
diff --git a/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/lucene-10470-2.geojson.gz b/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/lucene-10470-2.geojson.gz
new file mode 100644
index 00000000000..5e8b14f6f4e
Binary files /dev/null and b/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/lucene-10470-2.geojson.gz differ
diff --git a/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/lucene-10470-3.geojson.gz b/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/lucene-10470-3.geojson.gz
new file mode 100644
index 00000000000..c839cd53318
Binary files /dev/null and b/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/lucene-10470-3.geojson.gz differ
diff --git a/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/lucene-10470.geojson.gz b/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/lucene-10470.geojson.gz
new file mode 100644
index 00000000000..cf3ef4d82f3
Binary files /dev/null and b/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/lucene-10470.geojson.gz differ
diff --git a/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/lucene-10470.wkt.gz b/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/lucene-10470.wkt.gz
new file mode 100644
index 00000000000..9b62c1c681d
Binary files /dev/null and b/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/lucene-10470.wkt.gz differ