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:42 UTC
[lucene-solr] branch LUCENE-10563 created (now 41203f41276)
This is an automated email from the ASF dual-hosted git repository.
ivera pushed a change to branch LUCENE-10563
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git
at 41203f41276 LUCENE-10563: Fix failure to tessellate complex polygon (#933)
This branch includes the following new commits:
new 41203f41276 LUCENE-10563: Fix failure to tessellate complex polygon (#933)
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
[lucene-solr] 01/01: LUCENE-10563: Fix failure to tessellate complex polygon (#933)
Posted by iv...@apache.org.
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