lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From nkn...@apache.org
Subject lucene-solr:branch_7x: LUCENE-8418: Fix tessellation failure on polygon with holes due to vertex index clashing.
Date Fri, 27 Jul 2018 17:06:31 GMT
Repository: lucene-solr
Updated Branches:
  refs/heads/branch_7x 9c3e42c98 -> 50615fda9


LUCENE-8418: Fix tessellation failure on polygon with holes due to
vertex index clashing.


Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/50615fda
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/50615fda
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/50615fda

Branch: refs/heads/branch_7x
Commit: 50615fda9dfa13d37151baddca6bb74b5cd1eca8
Parents: 9c3e42c
Author: Nicholas Knize <nknize@gmail.com>
Authored: Fri Jul 27 11:00:46 2018 -0500
Committer: Nicholas Knize <nknize@gmail.com>
Committed: Fri Jul 27 12:06:23 2018 -0500

----------------------------------------------------------------------
 .../src/java/org/apache/lucene/geo/Polygon.java |  2 +-
 .../java/org/apache/lucene/geo/Tessellator.java | 36 ++++++++++++--------
 .../apache/lucene/document/TestLatLonShape.java |  1 -
 3 files changed, 22 insertions(+), 17 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/50615fda/lucene/core/src/java/org/apache/lucene/geo/Polygon.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/geo/Polygon.java b/lucene/core/src/java/org/apache/lucene/geo/Polygon.java
index e96fe8d..39ba9b7 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Polygon.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Polygon.java
@@ -116,7 +116,7 @@ public final class Polygon {
     this.maxLat = maxLat;
     this.minLon = minLon;
     this.maxLon = maxLon;
-    this.windingOrder = (windingSum < 0) ? GeoUtils.WindingOrder.CW : GeoUtils.WindingOrder.CCW;
+    this.windingOrder = (windingSum < 0) ? GeoUtils.WindingOrder.CCW : GeoUtils.WindingOrder.CW;
   }
 
   /** returns the number of vertex points */

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/50615fda/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
----------------------------------------------------------------------
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 c4e52a1..969facf 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
@@ -82,7 +82,7 @@ final public class Tessellator {
   public static final List<Triangle> tessellate(final Polygon polygon) {
     // Attempt to establish a doubly-linked list of the provided shell points (should be
CCW, but this will correct);
     // then filter instances of intersections.
-    Node outerNode = createDoublyLinkedList(polygon, WindingOrder.CCW);
+    Node outerNode = createDoublyLinkedList(polygon, 0, WindingOrder.CW);
     // If an outer node hasn't been detected, the shape is malformed. (must comply with OGC
SFA specification)
     if(outerNode == null) {
       throw new IllegalArgumentException("Malformed shape detected in Tessellator!");
@@ -118,19 +118,19 @@ final public class Tessellator {
   }
 
   /** Creates a circular doubly linked list using polygon points. The order is governed by
the specified winding order */
-  private static final Node createDoublyLinkedList(final Polygon polygon, final WindingOrder
windingOrder) {
+  private static final Node createDoublyLinkedList(final Polygon polygon, int startIndex,
final WindingOrder windingOrder) {
     Node lastNode = null;
     // Link points into the circular doubly-linked list in the specified winding order
     if (windingOrder == polygon.getWindingOrder()) {
       for (int i = 0; i < polygon.numPoints(); ++i) {
         if (lastNode == null || filter(polygon, i, lastNode) == false) {
-          lastNode = insertNode(polygon, i, lastNode);
+          lastNode = insertNode(polygon, startIndex++, i, lastNode);
         }
       }
     } else {
       for (int i = polygon.numPoints() - 1; i >= 0; --i) {
         if (lastNode == null || filter(polygon, i, lastNode) == false) {
-          lastNode = insertNode(polygon, i, lastNode);
+          lastNode = insertNode(polygon, startIndex++, i, lastNode);
         }
       }
     }
@@ -150,9 +150,11 @@ final public class Tessellator {
     final List<Node> holeList = new ArrayList<>();
     // Iterate through each array of hole vertices.
     Polygon[] holes = polygon.getHoles();
+    int nodeIndex = 0;
     for(int i = 0; i < polygon.numHoles(); ++i) {
+      nodeIndex += holes[i].numPoints();
       // create the doubly-linked hole list
-      Node list = createDoublyLinkedList(holes[i], WindingOrder.CW);
+      Node list = createDoublyLinkedList(holes[i], nodeIndex, WindingOrder.CCW);
       if (list == list.next) {
         list.isSteiner = true;
       }
@@ -666,8 +668,8 @@ final public class Tessellator {
   }
 
   /** Creates a node and optionally links it with a previous node in a circular doubly-linked
list */
-  private static final Node insertNode(final Polygon polygon, int index, final Node lastNode)
{
-    final Node node = new Node(polygon, index);
+  private static final Node insertNode(final Polygon polygon, int index, int vertexIndex,
final Node lastNode) {
+    final Node node = new Node(polygon, index, vertexIndex);
     if(lastNode == null) {
       node.previous = node;
       node.previousZ = node;
@@ -744,8 +746,10 @@ final public class Tessellator {
 
   /** Circular Doubly-linked list used for polygon coordinates */
   protected static class Node {
-    // vertex index in the polygon
+    // node index in the linked list
     private final int idx;
+    // vertex index in the polygon
+    private final int vrtxIdx;
     // reference to the polygon for lat/lon values
     private final Polygon polygon;
     // encoded x value
@@ -766,11 +770,12 @@ final public class Tessellator {
     // triangle center
     private boolean isSteiner = false;
 
-    protected Node(final Polygon polygon, final int index) {
+    protected Node(final Polygon polygon, final int index, final int vertexIndex) {
       this.idx = index;
+      this.vrtxIdx = vertexIndex;
       this.polygon = polygon;
-      this.y = encodeLatitude(polygon.getPolyLat(idx));
-      this.x = encodeLongitude(polygon.getPolyLon(idx));
+      this.y = encodeLatitude(polygon.getPolyLat(vrtxIdx));
+      this.x = encodeLongitude(polygon.getPolyLon(vrtxIdx));
       this.morton = BitUtil.interleave(x ^ 0x80000000, y ^ 0x80000000);
       this.previous = null;
       this.next = null;
@@ -781,6 +786,7 @@ final public class Tessellator {
     /** simple deep copy constructor */
     protected Node(Node other) {
       this.idx = other.idx;
+      this.vrtxIdx = other.vrtxIdx;
       this.polygon = other.polygon;
       this.morton = other.morton;
       this.x = other.x;
@@ -793,22 +799,22 @@ final public class Tessellator {
 
     /** get the x value */
     public final double getX() {
-      return polygon.getPolyLon(idx);
+      return polygon.getPolyLon(vrtxIdx);
     }
 
     /** get the y value */
     public final double getY() {
-      return polygon.getPolyLat(idx);
+      return polygon.getPolyLat(vrtxIdx);
     }
 
     /** get the longitude value */
     public final double getLon() {
-      return polygon.getPolyLon(idx);
+      return polygon.getPolyLon(vrtxIdx);
     }
 
     /** get the latitude value */
     public final double getLat() {
-      return polygon.getPolyLat(idx);
+      return polygon.getPolyLat(vrtxIdx);
     }
 
     /** compare nodes by y then x */

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/50615fda/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShape.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShape.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShape.java
index ac11e1b..f673d0a 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShape.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShape.java
@@ -102,7 +102,6 @@ public class TestLatLonShape extends LuceneTestCase {
     IOUtils.close(reader, dir);
   }
 
-  @AwaitsFix(bugUrl = "https://issues.apache.org/jira/browse/LUCENE-8418")
   /** test random polygons with a single hole */
   public void testPolygonWithHole() throws Exception {
     int numVertices = TestUtil.nextInt(random(), 50, 100);


Mime
View raw message