You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by nk...@apache.org on 2018/09/19 21:59:08 UTC
lucene-solr:branch_7x: LUCENE-8454: Fix incorrect vertex indexing and
other computation errors in shape tessellation that would sometimes cause an
infinite loop.
Repository: lucene-solr
Updated Branches:
refs/heads/branch_7x 81f8093b7 -> f54639d4a
LUCENE-8454: Fix incorrect vertex indexing and other computation errors in shape tessellation that would sometimes cause an infinite loop.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/f54639d4
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/f54639d4
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/f54639d4
Branch: refs/heads/branch_7x
Commit: f54639d4a18bbca98c8853f7e5065a0a3752292c
Parents: 81f8093
Author: Nicholas Knize <nk...@gmail.com>
Authored: Wed Sep 19 15:04:48 2018 -0500
Committer: Nicholas Knize <nk...@gmail.com>
Committed: Wed Sep 19 16:58:43 2018 -0500
----------------------------------------------------------------------
lucene/CHANGES.txt | 7 ++
.../java/org/apache/lucene/geo/Tessellator.java | 105 ++++++++++---------
.../org/apache/lucene/geo/TestTessellator.java | 22 ++++
3 files changed, 82 insertions(+), 52 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/f54639d4/lucene/CHANGES.txt
----------------------------------------------------------------------
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 68eb769..05098f9 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -9,6 +9,13 @@ Build
* LUCENE-8504: Upgrade forbiddenapis to version 2.6. (Uwe Schindler)
+======================= Lucene 7.5.1 =======================
+
+Bug Fixes:
+
+* LUCENE-8454: Fix incorrect vertex indexing and other computation errors in
+ shape tessellation that would sometimes cause an infinite loop. (Nick Knize)
+
======================= Lucene 7.5.0 =======================
API Changes:
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/f54639d4/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 969facf..a03e57c 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
@@ -150,9 +150,8 @@ final public class Tessellator {
final List<Node> holeList = new ArrayList<>();
// Iterate through each array of hole vertices.
Polygon[] holes = polygon.getHoles();
- int nodeIndex = 0;
+ int nodeIndex = polygon.numPoints();
for(int i = 0; i < polygon.numHoles(); ++i) {
- nodeIndex += holes[i].numPoints();
// create the doubly-linked hole list
Node list = createDoublyLinkedList(holes[i], nodeIndex, WindingOrder.CCW);
if (list == list.next) {
@@ -163,6 +162,7 @@ final public class Tessellator {
// Add the leftmost vertex of the hole.
holeList.add(fetchLeftmost(list));
}
+ nodeIndex += holes[i].numPoints();
}
// Sort the hole vertices by x coordinate
@@ -209,11 +209,15 @@ final public class Tessellator {
// segment's endpoint with lesser x will be potential connection point
{
do {
- if (hy <= p.getY() && hy >= p.next.getY()) {
+ 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) {
qx = x;
- connection = (p.getX() < p.next.getX()) ? p : p.next;
+ if (x == hx) {
+ if (hy == p.getY()) return p;
+ if (hy == p.next.getY()) return p.next;
+ }
+ connection = p.getX() < p.next.getX() ? p : p.next;
}
}
p = p.next;
@@ -222,7 +226,7 @@ final public class Tessellator {
if (connection == null) {
return null;
- } else if (hx == connection.getX()) {
+ } else if (hx == qx) {
return connection.previous;
}
@@ -237,8 +241,9 @@ final public class Tessellator {
p = connection.next;
{
while (p != stop) {
- if (hx > p.getX() && p.getX() >= mx && pointInEar(hy < my ? hx : qx, hy, mx, my, hy < my ? qx : hx, hy, mx, my)) {
- tan = Math.abs(hy - my) / (hx - mx); // tangential
+ 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)) {
connection = p;
tanMin = tan;
@@ -355,10 +360,6 @@ final public class Tessellator {
double cx = ear.next.x;
double cy = ear.next.y;
- // now make sure we don't have other points inside the potential ear;
- Node node;
- int idx;
-
// triangle bbox (flip the bits so negative encoded values are < positive encoded values)
int minTX = StrictMath.min(StrictMath.min(ear.previous.x, ear.x), ear.next.x) ^ 0x80000000;
int minTY = StrictMath.min(StrictMath.min(ear.previous.y, ear.y), ear.next.y) ^ 0x80000000;
@@ -369,32 +370,42 @@ final public class Tessellator {
long minZ = BitUtil.interleave(minTX, minTY);
long maxZ = BitUtil.interleave(maxTX, maxTY);
- // first look for points inside the triangle in increasing z-order
- node = ear.nextZ;
- while (node != null && Long.compareUnsigned(node.morton, maxZ) <= 0) {
- if (Long.compareUnsigned(node.morton, maxZ) <= 0) {
- idx = node.idx;
- if (idx != ear.previous.idx && idx != ear.next.idx
- && pointInEar(node.x, node.y, ax, ay, bx, by, cx, cy)
- && area(node.previous.x, node.previous.y, node.x, node.y, node.next.x, node.next.y) >= 0) {
+ // now make sure we don't have other points inside the potential ear;
+
+ // look for points inside the triangle in both directions
+ Node p = ear.previousZ;
+ Node n = ear.nextZ;
+ while (p != null && Long.compareUnsigned(p.morton, minZ) >= 0
+ && n != null && Long.compareUnsigned(n.morton, maxZ) <= 0) {
+ if (p.idx != ear.previous.idx && p.idx != ear.next.idx &&
+ pointInEar(p.x, p.y, ax, ay, bx, by, cx, cy) &&
+ area(p.previous.x, p.previous.y, p.x, p.y, p.next.x, p.next.y) >= 0) return false;
+ p = p.previousZ;
+
+ if (n.idx != ear.previous.idx && n.idx != ear.next.idx &&
+ pointInEar(n.x, n.y, ax, ay, bx, by, cx, cy) &&
+ area(n.previous.x, n.previous.y, n.x, n.y, n.next.x, n.next.y) >= 0) return false;
+ n = n.nextZ;
+ }
+
+ // first look for points inside the triangle in decreasing z-order
+ while (p != null && Long.compareUnsigned(p.morton, minZ) >= 0) {
+ if (p.idx != ear.previous.idx && p.idx != ear.next.idx
+ && pointInEar(p.x, p.y, ax, ay, bx, by, cx, cy)
+ && area(p.previous.x, p.previous.y, p.x, p.y, p.next.x, p.next.y) >= 0) {
return false;
}
- }
- node = node.nextZ;
- }
- // then look for points in decreasing z-order
- node = ear.previousZ;
- while (node != null &&
- Long.compareUnsigned(node.morton, minZ) >= 0) {
- if (Long.compareUnsigned(node.morton, maxZ) <= 0) {
- idx = node.idx;
- if (idx != ear.previous.idx && idx != ear.next.idx
- && pointInEar(node.x, node.y, ax, ay, bx, by, cx, cy)
- && area(node.previous.x, node.previous.y, node.x, node.y, node.next.x, node.next.y) >= 0) {
+ p = p.previousZ;
+ }
+ // then look for points in increasing z-order
+ while (n != null &&
+ Long.compareUnsigned(n.morton, maxZ) <= 0) {
+ if (n.idx != ear.previous.idx && n.idx != ear.next.idx
+ && pointInEar(n.x, n.y, ax, ay, bx, by, cx, cy)
+ && area(n.previous.x, n.previous.y, n.x, n.y, n.next.x, n.next.y) >= 0) {
return false;
}
- }
- node = node.previousZ;
+ n = n.nextZ;
}
return true;
}
@@ -464,6 +475,8 @@ final public class Tessellator {
a.nextZ = b;
b.previous = a;
b.previousZ = a;
+ a2.next = an;
+ a2.nextZ = an;
an.previous = a2;
an.previousZ = a2;
b2.next = a2;
@@ -577,24 +590,11 @@ final public class Tessellator {
// now we have two lists; merge
while (pSize > 0 || (qSize > 0 && q != null)) {
- // decide whether next element of merge comes from p or q
- if (pSize == 0) {
- // p is empty; e must come from q
- e = q;
- q = q.nextZ;
- --qSize;
- } else if (qSize == 0 || q == null) {
- // q is empty; e must come from p
- e = p;
- p = p.nextZ;
- --pSize;
- } else if (Long.compareUnsigned(p.morton, q.morton) <= 0) {
- // first element of p is lower (or same); e must come from p
+ if (pSize != 0 && (qSize == 0 || q == null || Long.compareUnsigned(p.morton, q.morton) <= 0)) {
e = p;
p = p.nextZ;
--pSize;
} else {
- // first element of q is lower; e must come from q
e = q;
q = q.nextZ;
--qSize;
@@ -677,7 +677,7 @@ final public class Tessellator {
node.nextZ = node;
} else {
node.next = lastNode.next;
- node.nextZ = lastNode.nextZ;
+ node.nextZ = lastNode.next;
node.previous = lastNode;
node.previousZ = lastNode;
lastNode.next.previous = node;
@@ -716,8 +716,8 @@ final public class Tessellator {
private static boolean pointInEar(final double x, final double y, final double ax, final double ay,
final double bx, final double by, final double cx, final double cy) {
return (cx - x) * (ay - y) - (ax - x) * (cy - y) >= 0 &&
- (ax - x) * (by - y) - (bx - x) * (ay - y) >= 0 &&
- (bx - x) * (cy - y) - (cx - x) * (by - y) >= 0;
+ (ax - x) * (by - y) - (bx - x) * (ay - y) >= 0 &&
+ (bx - x) * (cy - y) - (cx - x) * (by - y) >= 0;
}
/** compute whether the given x, y point is in a triangle; uses the winding order method */
@@ -795,16 +795,17 @@ final public class Tessellator {
this.next = other.next;
this.previousZ = other.previousZ;
this.nextZ = other.nextZ;
+ this.isSteiner = other.isSteiner;
}
/** get the x value */
public final double getX() {
- return polygon.getPolyLon(vrtxIdx);
+ return x;
}
/** get the y value */
public final double getY() {
- return polygon.getPolyLat(vrtxIdx);
+ return y;
}
/** get the longitude value */
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/f54639d4/lucene/sandbox/src/test/org/apache/lucene/geo/TestTessellator.java
----------------------------------------------------------------------
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 878cf01..055e025 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/geo/TestTessellator.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/geo/TestTessellator.java
@@ -16,6 +16,9 @@
*/
package org.apache.lucene.geo;
+import java.text.ParseException;
+import java.util.List;
+
import org.apache.lucene.util.LuceneTestCase;
import static org.apache.lucene.geo.GeoTestUtil.nextBoxNotCrossingDateline;
@@ -42,4 +45,23 @@ public class TestTessellator extends LuceneTestCase {
poly = new Polygon(poly.getPolyLats(), poly.getPolyLons(), inner, inner2);
assertTrue(Tessellator.tessellate(poly).size() > 0);
}
+
+ public void testLUCENE8454() throws ParseException {
+ String geoJson = "{\"type\": \"Polygon\", \"coordinates\": [[[167.8752929333776, -30.078235509309092], [167.729078, -30.078368], [167.7288750679411, -29.918443128222044], [167.728949, -30.078598], [167.582239, -30.078557], [167.58234527408044, -29.9717026229659], " +
+ "[167.43547018634274, -30.030896196337487], [167.43528, -30.078575], [167.288467, -30.078185], [167.28846777961195, -30.078041819512045], [167.142089, -30.077483], [167.143635, -29.813199], [167.1450859974141, -29.567345798606294], [167.144888, -29.567345], " +
+ "[167.14633281276596, -29.302953194679134], [167.146281, -29.302953], [167.147725, -29.036352], [167.292924, -29.036892], [167.2918703799358, -29.301396273146477], [167.29192460356776, -29.301396365495897], [167.292964, -29.036798], [167.4380298884901, -29.037250444489867], " +
+ "[167.43803, -29.03719], [167.583317, -29.037381], [167.58331697583935, -29.03744011447325], [167.7285250024388, -29.037514998454153], [167.728525, -29.03749], [167.873835, -29.037419], [167.87383543708486, -29.037703808329873], [168.018612, -29.037121], " +
+ "[168.0186121103674, -29.03714161109612], [168.163842, -29.03656], [168.1650939339767, -29.247683610268638], [168.164004, -29.036724], [168.309341, -29.036127], [168.3110870459225, -29.30068025473746], [168.311176, -29.30068], [168.312472, -29.567161], " +
+ "[168.31243194795024, -29.56716111631554], [168.31443, -29.812612], [168.31388505737894, -29.812615143334597], [168.315886, -30.077081], [168.169234, -30.077883], [168.16913368505345, -30.06147402418803], [168.169224, -30.077737], [168.022447, -30.078317], " +
+ "[168.02181920125142, -29.924959173336568], [168.0221, -30.078254], [167.875293, -30.078413], [167.8752929333776, -30.078235509309092]]," + //holes
+ "[[167.43638852926597, -29.811913377451322], [167.43642819713568, -29.81191343893342], [167.43660948310222, -29.684470839430233], [167.43638852926597, -29.811913377451322]], " +
+ "[[167.2900169281376, -29.811700260790584], [167.29007609051774, -29.811700416752192], [167.29022481985885, -29.765019899914726], [167.2900169281376, -29.811700260790584]], " +
+ "[[167.72865676499967, -29.812149953736277], [167.7287401903084, -29.81214997654223], [167.72874, -29.812], [167.72893197342373, -29.81199982820994], [167.72851531939722, -29.568503012044204], [167.72851327553326, -29.568503011862287], [167.72865676499967, -29.812149953736277]], " +
+ "[[167.87424106545097, -29.302014822030415], [167.87432742269175, -29.30201461402921], [167.87418553426855, -29.265830214765142], [167.87424106545097, -29.302014822030415]], " +
+ "[[168.1652103335658, -29.3030088541673], [168.16605788758287, -29.446580625201833], [168.16556735186845, -29.303245228857072], [168.165381, -29.303246], [168.16537977124085, -29.303008170411644], [168.1652103335658, -29.3030088541673]], " +
+ "[[168.02088551865063, -29.647294313012004], [168.02133932508806, -29.811843292379823], [168.02135614030843, -29.811843274349446], [168.021356, -29.811809], [168.02162340579383, -29.811807949652078], [168.02088551865063, -29.647294313012004]]]}";
+ Polygon[] polygons =Polygon.fromGeoJSON(geoJson);
+ List<Tessellator.Triangle> result = Tessellator.tessellate(polygons[0]);
+ assertEquals(result.size(), 84);
+ }
}
\ No newline at end of file