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 08:33:34 UTC
[lucene-solr] branch LUCENE-10470 created (now 4f67eabb3c0)
This is an automated email from the ASF dual-hosted git repository.
ivera pushed a change to branch LUCENE-10470
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git
at 4f67eabb3c0 LUCENE-10470: [Tessellator] Fix some failing polygons due to collinear edges (#756)
This branch includes the following new commits:
new 4f67eabb3c0 LUCENE-10470: [Tessellator] Fix some failing polygons due to collinear edges (#756)
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-10470: [Tessellator] Fix some failing polygons due to collinear edges (#756)
Posted by iv...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
ivera pushed a commit to branch LUCENE-10470
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git
commit 4f67eabb3c08501d4691beee731f8f7dba1262f0
Author: Ignacio Vera <iv...@apache.org>
AuthorDate: Wed Apr 27 10:24:22 2022 +0200
LUCENE-10470: [Tessellator] Fix some failing polygons due to collinear edges (#756)
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
# 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-10470-2.geojson.gz
# lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10470-3.geojson.gz
# lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10470.geojson.gz
# lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10470.wkt.gz
---
lucene/CHANGES.txt | 5 +-
.../java/org/apache/lucene/geo/Tessellator.java | 60 +++++++++++++--------
.../org/apache/lucene/geo/TestTessellator.java | 58 +++++++++++++++++++-
.../java/org/apache/lucene/geo/GeoTestUtil.java | 4 +-
.../apache/lucene/geo/lucene-10470-2.geojson.gz | Bin 0 -> 4007 bytes
.../apache/lucene/geo/lucene-10470-3.geojson.gz | Bin 0 -> 9513 bytes
.../org/apache/lucene/geo/lucene-10470.geojson.gz | Bin 0 -> 769 bytes
.../org/apache/lucene/geo/lucene-10470.wkt.gz | Bin 0 -> 1201 bytes
8 files changed, 102 insertions(+), 25 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index c3bdfe45f5e..7dc3d29f14e 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -7,8 +7,11 @@ http://s.apache.org/luceneversions
Bug Fixes
---------------------
-* LUCENE-9580: (Backport from 9.0.0) Fix bug in the polygon tessellator when introducing collinear edges during polygon
+* LUCENE-9580: Fix bug in the polygon tessellator when introducing collinear edges during polygon
splitting. (Ignacio Vera)
+
+* 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 8.11.2 =======================
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 a2cdcf522fa..0fe89df2413 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
@@ -387,7 +387,7 @@ final public class Tessellator {
if (isVertexEquals(next, vertex)) {
// make sure we are not crossing the polygon. This might happen when several holes share the same polygon vertex.
boolean crosses = GeoUtils.lineCrossesLine(next.previous.getX(), next.previous.getY(), vertex.next.getX(), vertex.next.getY(),
- next.next.getX(), next.next.getY(), vertex.previous.getX(), vertex.previous.getY());
+ next.next.getX(), next.next.getY(), vertex.previous.getX(), vertex.previous.getY());
if (crosses == false) {
return next;
}
@@ -531,20 +531,20 @@ final public class Tessellator {
// 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.getX(), p.getY(), ear.previous.getX(), ear.previous.getY(), ear.getX(), ear.getY(), ear.next.getX(), ear.next.getY())
- && area(p.previous.getX(), p.previous.getY(), p.getX(), p.getY(), p.next.getX(), p.next.getY()) >= 0) {
- return false;
- }
+ && pointInEar(p.getX(), p.getY(), ear.previous.getX(), ear.previous.getY(), ear.getX(), ear.getY(), ear.next.getX(), ear.next.getY())
+ && area(p.previous.getX(), p.previous.getY(), p.getX(), p.getY(), p.next.getX(), p.next.getY()) >= 0) {
+ return false;
+ }
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.getX(), n.getY(), ear.previous.getX(), ear.previous.getY(), ear.getX(), ear.getY(), ear.next.getX(), ear.next.getY())
- && area(n.previous.getX(), n.previous.getY(), n.getX(), n.getY(), n.next.getX(), n.next.getY()) >= 0) {
- return false;
- }
+ if (n.idx != ear.previous.idx && n.idx != ear.next.idx
+ && pointInEar(n.getX(), n.getY(), ear.previous.getX(), ear.previous.getY(), ear.getX(), ear.getY(), ear.next.getX(), ear.next.getY())
+ && area(n.previous.getX(), n.previous.getY(), n.getX(), n.getY(), n.next.getX(), n.next.getY()) >= 0) {
+ return false;
+ }
n = n.nextZ;
}
return true;
@@ -612,7 +612,8 @@ final public class Tessellator {
}
searchNode = searchNode.next;
} while (searchNode != start);
- return false;
+ // if there is some area left, we failed
+ return signedArea(start, start) == 0;
}
/** Computes if edge defined by a and b overlaps with a polygon edge **/
@@ -766,6 +767,12 @@ final public class Tessellator {
/** Determine whether the polygon defined between node start and node end is CW */
private static boolean isCWPolygon(final Node start, final Node end) {
+ // The polygon must be CW
+ return (signedArea(start, end) < 0) ? true : false;
+ }
+
+ /** Determine the signed area between node start and node end */
+ private static double signedArea(final Node start, final Node end) {
Node next = start;
double windingSum = 0;
do {
@@ -773,8 +780,7 @@ final public class Tessellator {
windingSum += area(next.getX(), next.getY(), next.next.getX(), next.next.getY(), end.getX(), end.getY());
next = next.next;
} while (next.next != end);
- //The polygon must be CW
- return (windingSum < 0) ? true : false;
+ return windingSum;
}
private static final boolean isLocallyInside(final Node a, final Node b) {
@@ -934,10 +940,22 @@ final public class Tessellator {
nextNode = node.next;
prevNode = node.previous;
// we can filter points when:
- if (isVertexEquals(node, nextNode) || // 1. they are the same,
- isVertexEquals(prevNode, nextNode) || // 2.- each one starts and ends in each other
- (prevNode.isNextEdgeFromPolygon == node.isNextEdgeFromPolygon && // 3.- they are co-linear and both edges have the same value in .isNextEdgeFromPolygon
- area(prevNode.getX(), prevNode.getY(), node.getX(), node.getY(), nextNode.getX(), nextNode.getY()) == 0)) {
+ // 1. they are the same
+ // 2.- each one starts and ends in each other
+ // 3.- they are collinear and both edges have the same value in .isNextEdgeFromPolygon
+ // 4.- they are collinear and second edge returns over the first edge
+ if (isVertexEquals(node, nextNode)
+ || isVertexEquals(prevNode, nextNode)
+ || ((prevNode.isNextEdgeFromPolygon == node.isNextEdgeFromPolygon
+ || isPointInLine(prevNode, node, nextNode.getX(), nextNode.getY()))
+ && area(
+ prevNode.getX(),
+ prevNode.getY(),
+ node.getX(),
+ node.getY(),
+ nextNode.getX(),
+ nextNode.getY())
+ == 0)) {
// Remove the node
removeNode(node, prevNode.isNextEdgeFromPolygon);
node = end = prevNode;
@@ -1008,8 +1026,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 */
@@ -1177,8 +1195,8 @@ final public class Tessellator {
/** pretty print the triangle vertices */
public String toString() {
String result = vertex[0].x + ", " + vertex[0].y + " [" + edgeFromPolygon[0] + "] " +
- vertex[1].x + ", " + vertex[1].y + " [" + edgeFromPolygon[1] + "] " +
- vertex[2].x + ", " + vertex[2].y + " [" + edgeFromPolygon[2] + "]";
+ vertex[1].x + ", " + vertex[1].y + " [" + edgeFromPolygon[1] + "] " +
+ vertex[2].x + ", " + vertex[2].y + " [" + edgeFromPolygon[2] + "]";
return result;
}
}
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 0f613242772..8156558015c 100644
--- a/lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java
+++ b/lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java
@@ -45,7 +45,7 @@ public class TestTessellator extends LuceneTestCase {
poly = new Polygon(poly.getPolyLats(), poly.getPolyLons(), inner, inner2);
assertTrue(Tessellator.tessellate(poly).size() > 0);
}
-
+
@Nightly
public void testSimpleTessellationAtNight() throws Exception {
Polygon poly = GeoTestUtil.createRegularPolygon(0.0, 0.0, 1000000, 1000000);
@@ -590,7 +590,7 @@ public class TestTessellator extends LuceneTestCase {
// 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);
+ checkTriangleEdgesFromPolygon(polygons[i], t);
}
}
}
@@ -612,6 +612,60 @@ public class TestTessellator extends LuceneTestCase {
}
}
+ public void testComplexPolygon45() throws Exception {
+ String geoJson = GeoTestUtil.readShape("lucene-10470.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);
+ }
+ }
+ }
+
+ public void testComplexPolygon46() throws Exception {
+ String wkt = GeoTestUtil.readShape("lucene-10470.wkt.gz");
+ Polygon polygon = (Polygon) SimpleWKTShapeParser.parse(wkt);
+ 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);
+ }
+ }
+
+ public void testComplexPolygon47() throws Exception {
+ String geoJson = GeoTestUtil.readShape("lucene-10470-2.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);
+ }
+ }
+ }
+
+ @Nightly
+ public void testComplexPolygon48() throws Exception {
+ String geoJson = GeoTestUtil.readShape("lucene-10470-3.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/java/org/apache/lucene/geo/GeoTestUtil.java b/lucene/test-framework/src/java/org/apache/lucene/geo/GeoTestUtil.java
index 9dc5b8d3f26..6f3af2b2160 100644
--- a/lucene/test-framework/src/java/org/apache/lucene/geo/GeoTestUtil.java
+++ b/lucene/test-framework/src/java/org/apache/lucene/geo/GeoTestUtil.java
@@ -761,7 +761,9 @@ public class GeoTestUtil {
is = new GZIPInputStream(is);
}
BufferedReader reader = new BufferedReader(new InputStreamReader(is, StandardCharsets.UTF_8));
- return reader.readLine();
+ StringBuilder builder = new StringBuilder();
+ reader.lines().forEach(s -> builder.append(s));
+ return builder.toString();
}
}
}
diff --git a/lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10470-2.geojson.gz b/lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10470-2.geojson.gz
new file mode 100644
index 00000000000..5e8b14f6f4e
Binary files /dev/null and b/lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10470-2.geojson.gz differ
diff --git a/lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10470-3.geojson.gz b/lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10470-3.geojson.gz
new file mode 100644
index 00000000000..c839cd53318
Binary files /dev/null and b/lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10470-3.geojson.gz differ
diff --git a/lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10470.geojson.gz b/lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10470.geojson.gz
new file mode 100644
index 00000000000..cf3ef4d82f3
Binary files /dev/null and b/lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10470.geojson.gz differ
diff --git a/lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10470.wkt.gz b/lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10470.wkt.gz
new file mode 100644
index 00000000000..9b62c1c681d
Binary files /dev/null and b/lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10470.wkt.gz differ