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/07/01 09:03:43 UTC
[lucene-solr] 01/01: 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 LUCENE-10563
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git
commit 41203f412762e858f62223524ae9b4af6cfe32f8
Author: Craig Taverner <cr...@amanzi.com>
AuthorDate: Wed Jun 8 10:58:40 2022 +0200
LUCENE-10563: Fix failure to tessellate complex polygon (#933)
# Conflicts:
# lucene/CHANGES.txt
# lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
# lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java
# lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10563-1.geojson.gz
# lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10563-2.geojson.gz
# lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10563-3.geojson.gz
---
lucene/CHANGES.txt | 2 ++
.../java/org/apache/lucene/geo/Tessellator.java | 2 ++
.../org/apache/lucene/geo/TestTessellator.java | 26 +++++++++++++++++++++
.../apache/lucene/geo/lucene-10563-1.geojson.gz | Bin 0 -> 541 bytes
.../apache/lucene/geo/lucene-10563-2.geojson.gz | Bin 0 -> 362 bytes
.../apache/lucene/geo/lucene-10563-3.geojson.gz | Bin 0 -> 358 bytes
6 files changed, 30 insertions(+)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 7dc3d29f14e..91683c82c61 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -13,6 +13,8 @@ Bug Fixes
* 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)
+* LUCENE-10563: Fix failure to tessellate complex polygon (Craig Taverner)
+
======================= Lucene 8.11.2 =======================
Bug Fixes
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 0fe89df2413..69d5c9a6f37 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
@@ -757,6 +757,8 @@ final public class Tessellator {
return a.next.idx != b.idx && a.previous.idx != b.idx
&& 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 8156558015c..56313782ee6 100644
--- a/lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java
+++ b/lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java
@@ -665,6 +665,32 @@ public class TestTessellator extends LuceneTestCase {
}
}
}
+
+ 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);
+ 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);
+ assertEquals(1, polygons.length);
+ Polygon polygon = polygons[0];
+ List<Tessellator.Triangle> tessellation = Tessellator.tessellate(polygon);
+ // calculate the area of big polygons have numerical error
+ assertEquals(area(polygon), area(tessellation), 1e-11);
+ for (Tessellator.Triangle t : tessellation) {
+ checkTriangleEdgesFromPolygon(polygon, t);
+ }
+ }
private void checkPolygon(String wkt) throws Exception {
Polygon polygon = (Polygon) SimpleWKTShapeParser.parse(wkt);
diff --git a/lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10563-1.geojson.gz b/lucene/test-framework/src/resources/org/apache/lucene/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/geo/lucene-10563-1.geojson.gz differ
diff --git a/lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10563-2.geojson.gz b/lucene/test-framework/src/resources/org/apache/lucene/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/geo/lucene-10563-2.geojson.gz differ
diff --git a/lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10563-3.geojson.gz b/lucene/test-framework/src/resources/org/apache/lucene/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/geo/lucene-10563-3.geojson.gz differ