lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From iv...@apache.org
Subject [lucene-solr] 02/02: LUCENE-8775: Compute properly the bridge between a polygon and a hole when sharing a vertex.
Date Wed, 26 Jun 2019 05:16:24 GMT
This is an automated email from the ASF dual-hosted git repository.

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

commit d398838f6c909f0e9d52c815500ba6227fca7533
Author: Ignacio Vera <ivera@apache.org>
AuthorDate: Tue Jun 11 07:01:42 2019 +0200

    LUCENE-8775: Compute properly the bridge between a polygon and a hole when sharing a vertex.
---
 .../java/org/apache/lucene/geo/Tessellator.java    | 44 +++++++++++----
 .../org/apache/lucene/geo/TestTessellator.java     | 65 +++++++++++++++++++++-
 2 files changed, 97 insertions(+), 12 deletions(-)

diff --git a/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java b/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
index 195e4a6..0542d16 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
@@ -199,8 +199,24 @@ final public class Tessellator {
 
   /** Finds a bridge between vertices that connects a hole with an outer ring, and links
it */
   private static final void eliminateHole(final Node holeNode, Node outerNode, Polygon hole)
{
+    // Attempt to find a common point between the HoleNode and OuterNode.
+    Node next = outerNode;
+    do {
+      if (Rectangle.containsPoint(next.getLat(), next.getLon(), hole.minLat, hole.maxLat,
hole.minLon, hole.maxLon)) {
+        Node sharedVertex = getSharedVertex(holeNode, next);
+        if (sharedVertex != null) {
+          // Split the resulting polygon.
+          Node node = splitPolygon(next, sharedVertex);
+          // Filter the split nodes.
+          filterPoints(node, node.next);
+          return;
+        }
+      }
+      next = next.next;
+    } while (next != outerNode);
+
     // Attempt to find a logical bridge between the HoleNode and OuterNode.
-    outerNode = fetchHoleBridge(holeNode, outerNode, hole);
+    outerNode = fetchHoleBridge(holeNode, outerNode);
 
     // Determine whether a hole bridge could be fetched.
     if(outerNode != null) {
@@ -216,7 +232,7 @@ final public class Tessellator {
    *
    * see: http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf
    **/
-  private static final Node fetchHoleBridge(final Node holeNode, final Node outerNode, Polygon
hole) {
+  private static final Node fetchHoleBridge(final Node holeNode, final Node outerNode) {
     Node p = outerNode;
     double qx = Double.NEGATIVE_INFINITY;
     final double hx = holeNode.getX();
@@ -226,13 +242,6 @@ final public class Tessellator {
     // segment's endpoint with lesser x will be potential connection point
     {
       do {
-        //if vertex of the polygon is a vertex of the hole, just use that point.
-        if (Rectangle.containsPoint(p.getLat(), p.getLon(), hole.minLat, hole.maxLat, hole.minLon,
hole.maxLon)) {
-          Node sharedVertex = getSharedVertex(holeNode, p);
-          if (sharedVertex != null) {
-            return sharedVertex;
-          }
-        }
         if (hy <= p.getY() && hy >= p.next.getY() && p.next.getY()
!= p.getY()) {
           final double x = p.getX() + (hy - p.getY()) * (p.next.getX() - p.getX()) / (p.next.getY()
- p.getY());
           if (x <= hx && x > qx) {
@@ -528,9 +537,9 @@ final public class Tessellator {
 
   /** Determines whether a diagonal between two polygon nodes lies within a polygon interior.
(This determines the validity of the ray.) **/
   private static final boolean isValidDiagonal(final Node a, final Node b) {
-    //If points are equal then use it
     if (isVertexEquals(a, b)) {
-      return true;
+      //If points are equal then use it if they are valid polygons
+      return isCWPolygon(a, b);
     }
     return a.next.idx != b.idx && a.previous.idx != b.idx
         && isIntersectingPolygon(a, a.getX(), a.getY(), b.getX(), b.getY()) == false
@@ -538,6 +547,19 @@ final public class Tessellator {
         && middleInsert(a, a.getX(), a.getY(), b.getX(), b.getY());
   }
 
+  /** Determine whether the polygon defined between node start and node end is CW */
+  private static boolean isCWPolygon(Node start, Node end) {
+    Node next = start;
+    double windingSum = 0;
+    do {
+      // compute signed area
+      windingSum += area(next.getLon(), next.getLat(), next.next.getLon(), next.next.getLat(),
end.getLon(), end.getLat());
+      next = next.next;
+    } while (next.next != end);
+    //The polygon must be CW
+    return (windingSum < 0) ? true : false;
+  }
+
   private static final boolean isLocallyInside(final Node a, final Node b) {
     double area = area(a.previous.getX(), a.previous.getY(), a.getX(), a.getY(), a.next.getX(),
a.next.getY());
     if (area == 0) {
diff --git a/lucene/sandbox/src/test/org/apache/lucene/geo/TestTessellator.java b/lucene/sandbox/src/test/org/apache/lucene/geo/TestTessellator.java
index 247a7ed..fcfe1ab 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/geo/TestTessellator.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/geo/TestTessellator.java
@@ -508,9 +508,72 @@ public class TestTessellator extends LuceneTestCase {
     checkPolygon(wkt);
   }
 
+  public void testComplexPolygon38() throws Exception {
+    String wkt ="POLYGON((-80.1124643 40.8042035, -80.1124675 40.8044718, -80.1124274 40.8045944,
-80.1123667 40.8047618, -80.1123187 40.8048961, -80.1122144 40.8052404, -80.1121822 40.8054597,
" +
+        "-80.1126328 40.8055247, -80.11318 40.8057277, -80.1136735 40.8060119, -80.1139935
40.8061, -80.1144689 40.8062548, -80.1147571 40.8065235, -80.115177 40.8068213, -80.1152614
40.8070676, " +
+        "-80.1150468 40.8073031, -80.1149288 40.8075955, -80.1150039 40.8079934, -80.1151026
40.8081061, -80.1152399 40.8081396, -80.1156798 40.8082857, -80.1151843 40.8089253, -80.1156524
40.808904, " +
+        "-80.1162332 40.8091775, -80.1157808 40.8095377, -80.1156441 40.8096134, -80.1155087
40.8096884, -80.1151646 40.8098791, -80.1147561 40.8100954, -80.1147128 40.8101183, -80.1145352
40.8101879, " +
+        "-80.1142434 40.8103022, -80.1137421 40.8105106, -80.1136367 40.8101601, -80.1124244
40.8101033, -80.1121871 40.8099392, -80.1122527 40.8098272, -80.1125317 40.8098231, -80.1126926
40.8093887, " +
+        "-80.1129976 40.808775, -80.1128367 40.8084177, -80.1128685 40.8082688, -80.1129547
40.8078655, -80.1128903 40.8073945, -80.1128903 40.8069722, -80.1130083 40.8067529, -80.1128045
40.8065174, " +
+        "-80.1121608 40.8063794, -80.1115492 40.8062576, -80.111312 40.806182, -80.1111323
40.8063058, -80.1108733 40.8061601, -80.1099828 40.8057866, -80.1095966 40.8057297, -80.1091352
40.805478, " +
+        "-80.1085936 40.8053328, -80.1080731 40.8053967, -80.1077088 40.8055159, -80.1073654
40.8054672, -80.1063779 40.8050719, -80.1057878 40.8048932, -80.1051012 40.8047146, -80.1045237
40.804701, " +
+        "-80.1039834 40.803764, -80.1044145 40.803941, -80.1055089 40.8042334, -80.1063243
40.8044527, -80.1069251 40.8045014, -80.1073717 40.8045757, -80.1076775 40.8047463, -80.1081173
40.8047138, " +
+        "-80.1085143 40.8046813, -80.1088241 40.8049968, -80.1093399 40.8050004, -80.1096931
40.8050455, -80.1101759 40.8050618, -80.1103047 40.8050374, -80.1104549 40.8046232, -80.1106051
40.8041522, " +
+        "-80.1107553 40.8036937, -80.1088178 40.8030618, -80.1088714 40.8029156, -80.1094293
40.8030496, -80.1095751 40.8030051, -80.1091996 40.802599, -80.1089636 40.8023797, -80.1090816
40.8022741, " +
+        "-80.109382 40.8023797, -80.1099399 40.8025746, -80.1103905 40.8028751, -80.1108089
40.8030375, -80.1110557 40.8028914, -80.1114956 40.80307, -80.1119998 40.803338, -80.112429
40.8033299, -80.112665 40.8031512, " +
+        "-80.1121822 40.8029563, -80.1115063 40.8025665, -80.1108411 40.8023391, -80.1105407
40.8018924, -80.1103905 40.8014945, -80.1098648 40.8012996, -80.1092318 40.8009828, -80.1086417
40.8009585, " +
+        "-80.1087597 40.8006417, -80.1096065 40.8007592, -80.1117469 40.8018434, -80.1126175
40.8023287, -80.1138093 40.8032437, -80.1140089 40.8033365, -80.1142363 40.8033396, -80.1146277
40.8032744, " +
+        "-80.1159865 40.8029532, -80.1172922 40.802728, -80.1177849 40.8026481, -80.1179499
40.8014287, -80.1177068 40.8033675, -80.1176231 40.8040661, -80.1175682 40.8044886, -80.1173232
40.8045697, " +
+        "-80.114679 40.804454, -80.1146739 40.8043283, -80.1147726 40.8038162, -80.1139347
40.8040133, -80.1132184 40.8040944, -80.113193 40.8041732, -80.1130709 40.8042723, -80.1128737
40.80424, -80.1124643 40.8042035), " +
+        "(-80.112012 40.8039682, -80.1111747 40.8038305, -80.111237 40.8038512, -80.112012
40.8039682)," +
+        " (-80.1124643 40.8042035, -80.112484 40.804144, -80.1125136 40.8040207, -80.1124643
40.8042035))";
+    checkPolygon(wkt);
+  }
+
+  public void testComplexPolygon39() throws Exception {
+    String wkt ="POLYGON((71.8821959 52.3494653, 71.8824975 52.3494644, 71.8825076 52.3485511,
71.88209 52.3485465, 71.8820828 52.3487054, 71.8822007 52.3487626, 71.8822 52.3488601, 71.8821989
52.3490193, 71.8821959 52.3494653), " +
+        "(71.8823576 52.3489838, 71.882321 52.348962, 71.882357 52.3489395, 71.8823936 52.3489613,
71.8823576 52.3489838), " +
+        "(71.8823569 52.3494143, 71.8823916 52.349435, 71.8823568 52.3494567, 71.8823221
52.349436, 71.8823569 52.3494143), " +
+        "(71.8823569 52.3494143, 71.8823263 52.349396, 71.8823588 52.3493757, 71.8823894
52.3493939, 71.8823569 52.3494143), " +
+        "(71.8823588 52.3493757, 71.8823258 52.349356, 71.8823595 52.349335, 71.8823925 52.3493547,
71.8823588 52.3493757), " +
+        "(71.8823595 52.349335, 71.8823277 52.3493161, 71.8823602 52.3492958, 71.8823919
52.3493147, 71.8823595 52.349335), " +
+        "(71.8823602 52.3492958, 71.8823307 52.3492782, 71.8823595 52.3492602, 71.882389
52.3492778, 71.8823602 52.3492958), " +
+        "(71.8823595 52.3492602, 71.8823307 52.349243, 71.8823611 52.349224, 71.8823899 52.3492412,
71.8823595 52.3492602), " +
+        "(71.8823611 52.349224, 71.8823276 52.3492041, 71.882361 52.3491832, 71.8823944 52.3492031,
71.8823611 52.349224), " +
+        "(71.882361 52.3491832, 71.8823281 52.3491636, 71.8823613 52.3491428, 71.8823942
52.3491624, 71.882361 52.3491832), " +
+        "(71.8823613 52.3491428, 71.8823305 52.3491244, 71.8823618 52.3491048, 71.8823927
52.3491232, 71.8823613 52.3491428), " +
+        "(71.8823618 52.3491048, 71.8823294 52.3490854, 71.8823607 52.3490659, 71.8823931
52.3490852, 71.8823618 52.3491048), " +
+        "(71.8823607 52.3490659, 71.8823285 52.3490467, 71.8823581 52.3490282, 71.8823902
52.3490474, 71.8823607 52.3490659), " +
+        "(71.8823581 52.3490282, 71.8823215 52.3490064, 71.8823576 52.3489838, 71.8823942
52.3490057, 71.8823581 52.3490282))";
+    checkPolygon(wkt);
+  }
+
   private void checkPolygon(String wkt) throws Exception {
     Polygon polygon = (Polygon) SimpleWKTShapeParser.parse(wkt);
     List<Tessellator.Triangle> tessellation = Tessellator.tessellate(polygon);
-    assertTrue(tessellation.size() > 0);
+    assertEquals(area(polygon), area(tessellation), 0.0);
+  }
+
+  private double area(Polygon p) {
+    double val = 0;
+    for (int i = 0; i < p.numPoints() - 1; i++) {
+      val += p.getPolyLon(i) * p.getPolyLat(i + 1)
+          - p.getPolyLat(i) * p.getPolyLon(i + 1);
+    }
+    double area = Math.abs(val / 2.);
+    for (Polygon hole : p.getHoles()) {
+      area -= area(hole);
+    }
+    return area;
+  }
+
+  private double area(List<Tessellator.Triangle> triangles) {
+    double area = 0;
+    for (Tessellator.Triangle t : triangles) {
+      double[] lats = new double[] {t.getLat(0), t.getLat(1), t.getLat(2), t.getLat(0)};
+      double[] lons = new double[] {t.getLon(0), t.getLon(1), t.getLon(2), t.getLon(0)};
+      area += area(new Polygon(lats, lons));
+    }
+    return area;
   }
 }
\ No newline at end of file


Mime
View raw message