[lucene-solr] branch branch_8x updated: LUCENE-9417: Tessellator might fail when several holes share are connected to the same vertex (#1614)

[iv...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

ivera pushed a commit to branch branch_8x
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git


The following commit(s) were added to refs/heads/branch_8x by this push:
     new 3bcd866  LUCENE-9417: Tessellator might fail when several holes share are connected to the same vertex (#1614)
3bcd866 is described below

commit 3bcd86646ffd1ba3f6681440e55da37dcee3ea2e
Author: Ignacio Vera <iv...@apache.org>
AuthorDate: Mon Jun 29 17:46:21 2020 +0200

    LUCENE-9417: Tessellator might fail when several holes share are connected to the same vertex (#1614)
---
 lucene/CHANGES.txt                                      |   3 +++
 .../src/java/org/apache/lucene/geo/Tessellator.java     |  11 ++++++++++-
 .../src/test/org/apache/lucene/geo/TestTessellator.java |  14 ++++++++++++++
 .../org/apache/lucene/geo/lucene-9417.geojson.gz        | Bin 0 -> 79049 bytes
 4 files changed, 27 insertions(+), 1 deletion(-)

diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 02ea4ba..2208794 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -146,6 +146,9 @@ Bug Fixes
 
 * LUCENE-9400: Tessellator might build illegal polygons when several holes share the shame vertex. (Ignacio Vera)
 
+* LUCENE-9417: Tessellator might build illegal polygons when several holes share are connected to the same
+  vertex. (Ignacio Vera)
+
 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 1600955..6ef68e8 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
@@ -360,7 +360,16 @@ final public class Tessellator {
         if (hx >= p.getX() && p.getX() >= mx && hx != p.getX()
             && pointInEar(p.getX(), p.getY(), hy < my ? hx : qx, hy, mx, my, hy < my ? qx : hx, hy)) {
           tan = Math.abs(hy - p.getY()) / (hx - p.getX()); // tangential
-          if ((tan < tanMin || (tan == tanMin && p.getX() > connection.getX())) && isLocallyInside(p, holeNode)) {
+          if (isVertexEquals(p, connection) && isLocallyInside(p, holeNode)) {
+            // make sure we are not crossing the polygon. This might happen when several holes have a bridge to the same polygon vertex
+            // and this vertex has different vertex.
+            boolean crosses = GeoUtils.lineCrossesLine(p.getX(), p.getY(), holeNode.getX(), holeNode.getY(),
+                connection.next.getX(), connection.next.getY(), connection.previous.getX(), connection.previous.getY());
+            if (crosses == false) {
+              connection = p;
+              tanMin = tan;
+            }
+          } else if ((tan < tanMin || (tan == tanMin && p.getX() > connection.getX())) && isLocallyInside(p, holeNode)) {
             connection = p;
             tanMin = tan;
           }
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 2410ba1..61aab6d 100644
--- a/lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java
+++ b/lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java
@@ -581,6 +581,20 @@ public class TestTessellator extends LuceneTestCase {
     checkPolygon(wkt);
   }
 
+  @Nightly
+  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++) {
+      List<Tessellator.Triangle> tessellation = Tessellator.tessellate(polygons[i]);
+      // 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 = Tessellator.tessellate(polygon);
diff --git a/lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-9417.geojson.gz b/lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-9417.geojson.gz
new file mode 100644
index 0000000..0cdb18d
Binary files /dev/null and b/lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-9417.geojson.gz differ