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/06/08 08:58:46 UTC
[lucene] branch main updated: LUCENE-10563: Fix failure to tessellate complex polygon (#933)
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 1dceff12c8b LUCENE-10563: Fix failure to tessellate complex polygon (#933)
1dceff12c8b is described below
commit 1dceff12c8bb764255927be55e46f4d435f47aed
Author: Craig Taverner <cr...@amanzi.com>
AuthorDate: Wed Jun 8 10:58:40 2022 +0200
LUCENE-10563: Fix failure to tessellate complex polygon (#933)
---
lucene/CHANGES.txt | 2 +
.../java/org/apache/lucene/geo/Tessellator.java | 5 +-
.../org/apache/lucene/geo/TestTessellator.java | 99 +++++++++++++++++----
.../lucene/tests/geo/lucene-10563-1.geojson.gz | Bin 0 -> 541 bytes
.../lucene/tests/geo/lucene-10563-2.geojson.gz | Bin 0 -> 362 bytes
.../lucene/tests/geo/lucene-10563-3.geojson.gz | Bin 0 -> 358 bytes
6 files changed, 88 insertions(+), 18 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index f3de66e7409..a9e0c3822f8 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -95,6 +95,8 @@ Bug Fixes
* LUCENE-10598: SortedSetDocValues#docValueCount() should be always greater than zero. (Lu Xugang)
+* LUCENE-10563: Fix failure to tessellate complex polygon (Craig Taverner)
+
Other
---------------------
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 4a6a8fc26a8..cfdd3efcb21 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
@@ -800,9 +800,8 @@ public final class Tessellator {
final boolean mortonOptimized) {
// Search for a valid diagonal that divides the polygon into two.
Node searchNode = start;
- Node nextNode;
do {
- nextNode = searchNode.next;
+ Node nextNode = searchNode.next;
Node diagonal = nextNode.next;
while (diagonal != searchNode.previous) {
if (searchNode.idx != diagonal.idx && isValidDiagonal(searchNode, diagonal)) {
@@ -1093,6 +1092,8 @@ public final class Tessellator {
&& isIntersectingPolygon(a, a.getX(), a.getY(), b.getX(), b.getY()) == false
&& 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
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 1f2220c3754..1c491bf8ae2 100644
--- a/lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java
+++ b/lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java
@@ -17,6 +17,7 @@
package org.apache.lucene.geo;
import static org.apache.lucene.tests.geo.GeoTestUtil.nextBoxNotCrossingDateline;
+import static org.hamcrest.Matchers.equalTo;
import java.text.ParseException;
import java.util.List;
@@ -704,13 +705,13 @@ public class TestTessellator extends LuceneTestCase {
public void testComplexPolygon42() throws Exception {
String geoJson = GeoTestUtil.readShape("lucene-9417.geojson.gz");
Polygon[] polygons = Polygon.fromGeoJSON(geoJson);
- for (int i = 0; i < polygons.length; i++) {
+ for (Polygon polygon : polygons) {
List<Tessellator.Triangle> tessellation =
- Tessellator.tessellate(polygons[i], random().nextBoolean());
+ Tessellator.tessellate(polygon, random().nextBoolean());
// calculate the area of big polygons have numerical error
- assertEquals(area(polygons[i]), area(tessellation), 1e-11);
+ assertEquals(area(polygon), area(tessellation), 1e-11);
for (Tessellator.Triangle t : tessellation) {
- checkTriangleEdgesFromPolygon(polygons[i], t);
+ checkTriangleEdgesFromPolygon(polygon, t);
}
}
}
@@ -759,13 +760,13 @@ 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++) {
+ for (Polygon polygon : polygons) {
List<Tessellator.Triangle> tessellation =
- Tessellator.tessellate(polygons[i], random().nextBoolean());
+ Tessellator.tessellate(polygon, random().nextBoolean());
// calculate the area of big polygons have numerical error
- assertEquals(area(polygons[i]), area(tessellation), 1e-11);
+ assertEquals(area(polygon), area(tessellation), 1e-11);
for (Tessellator.Triangle t : tessellation) {
- checkTriangleEdgesFromPolygon(polygons[i], t);
+ checkTriangleEdgesFromPolygon(polygon, t);
}
}
}
@@ -785,13 +786,13 @@ public class TestTessellator extends LuceneTestCase {
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++) {
+ for (Polygon polygon : polygons) {
List<Tessellator.Triangle> tessellation =
- Tessellator.tessellate(polygons[i], random().nextBoolean());
+ Tessellator.tessellate(polygon, random().nextBoolean());
// calculate the area of big polygons have numerical error
- assertEquals(area(polygons[i]), area(tessellation), 1e-11);
+ assertEquals(area(polygon), area(tessellation), 1e-11);
for (Tessellator.Triangle t : tessellation) {
- checkTriangleEdgesFromPolygon(polygons[i], t);
+ checkTriangleEdgesFromPolygon(polygon, t);
}
}
}
@@ -800,16 +801,82 @@ public class TestTessellator extends LuceneTestCase {
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);
+ for (Polygon polygon : polygons) {
+ List<Tessellator.Triangle> tessellation = Tessellator.tessellate(polygon, true);
// calculate the area of big polygons have numerical error
- assertEquals(area(polygons[i]), area(tessellation), 1e-11);
+ assertEquals(area(polygon), area(tessellation), 1e-11);
for (Tessellator.Triangle t : tessellation) {
- checkTriangleEdgesFromPolygon(polygons[i], t);
+ checkTriangleEdgesFromPolygon(polygon, t);
}
}
}
+ public void testComplexPolygon49() throws Exception {
+ String wkt =
+ "POLYGON((77.500 13.500, 77.550 13.500, 77.530 13.470, 77.570 13.470,"
+ + "77.550 13.500, 77.600 13.500, 77.600 13.400, 77.500 13.400, 77.500 13.500))";
+ Polygon polygon = (Polygon) SimpleWKTShapeParser.parse(wkt);
+ 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 testComplexPolygon50() throws Exception {
+ String geoJson = GeoTestUtil.readShape("lucene-10563-1.geojson.gz");
+ Polygon[] polygons = Polygon.fromGeoJSON(geoJson);
+ assertThat("Only one polygon", polygons.length, equalTo(1));
+ Polygon polygon = polygons[0];
+ List<Tessellator.Triangle> tessellation = Tessellator.tessellate(polygon, true);
+ // 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 testComplexPolygon51() throws Exception {
+ String geoJson = GeoTestUtil.readShape("lucene-10563-2.geojson.gz");
+ Polygon[] polygons = Polygon.fromGeoJSON(geoJson);
+ assertThat("Only one polygon", polygons.length, equalTo(1));
+ Polygon polygon = polygons[0];
+ boolean checkSelfIntersections = random().nextBoolean();
+ IllegalArgumentException ex =
+ expectThrows(
+ IllegalArgumentException.class,
+ () -> Tessellator.tessellate(polygon, checkSelfIntersections));
+ String error =
+ checkSelfIntersections
+ ? "Polygon self-intersection at lat=2.8440144262027296 lon=177.96701124393607"
+ : "Unable to Tessellate shape. Possible malformed shape detected.";
+ assertEquals(
+ "Expected specific error depending on checkSelfIntersections=" + checkSelfIntersections,
+ error,
+ ex.getMessage());
+ }
+
+ public void testComplexPolygon52() throws Exception {
+ String geoJson = GeoTestUtil.readShape("lucene-10563-3.geojson.gz");
+ Polygon[] polygons = Polygon.fromGeoJSON(geoJson);
+ assertThat("Only one polygon", polygons.length, equalTo(1));
+ Polygon polygon = polygons[0];
+ boolean checkSelfIntersections = random().nextBoolean();
+ IllegalArgumentException ex =
+ expectThrows(
+ IllegalArgumentException.class,
+ () -> Tessellator.tessellate(polygon, checkSelfIntersections));
+ String error =
+ checkSelfIntersections
+ ? "Polygon self-intersection at lat=-11.22876335157631 lon=126.94854431224186"
+ : "Unable to Tessellate shape. Possible malformed shape detected.";
+ assertEquals(
+ "Expected specific error depending on checkSelfIntersections=" + checkSelfIntersections,
+ error,
+ ex.getMessage());
+ }
+
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-10563-1.geojson.gz b/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/lucene-10563-1.geojson.gz
new file mode 100644
index 00000000000..5f283a38e18
Binary files /dev/null and b/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/lucene-10563-1.geojson.gz differ
diff --git a/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/lucene-10563-2.geojson.gz b/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/lucene-10563-2.geojson.gz
new file mode 100644
index 00000000000..c803e43d49a
Binary files /dev/null and b/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/lucene-10563-2.geojson.gz differ
diff --git a/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/lucene-10563-3.geojson.gz b/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/lucene-10563-3.geojson.gz
new file mode 100644
index 00000000000..81ba08f36f6
Binary files /dev/null and b/lucene/test-framework/src/resources/org/apache/lucene/tests/geo/lucene-10563-3.geojson.gz differ