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 2025/08/26 09:32:17 UTC
(lucene) branch main updated: Tessellator should fail if it cannot process a hole (#14974)
This is an automated email from the ASF dual-hosted git repository.
ivera pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/main by this push:
new 4b821699e36 Tessellator should fail if it cannot process a hole (#14974)
4b821699e36 is described below
commit 4b821699e3659a19479bacea2cf0c32ed8bd4078
Author: Ignacio Vera <iv...@apache.org>
AuthorDate: Tue Aug 26 10:32:11 2025 +0100
Tessellator should fail if it cannot process a hole (#14974)
Tessellator throws an IAE exception if it cannot process a hole.
---
lucene/CHANGES.txt | 3 ++
.../java/org/apache/lucene/geo/Tessellator.java | 29 +++++++++++++++----
.../src/java/org/apache/lucene/geo/XYPolygon.java | 13 +++++++++
.../apache/lucene/document/TestShapeDocValues.java | 7 ++---
.../org/apache/lucene/geo/TestTessellator.java | 33 +++++++++++++++++++++-
5 files changed, 75 insertions(+), 10 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index d27ecdfda8a..6fd5516742f 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -314,6 +314,9 @@ Bug Fixes
* GITHUB#15106: Fix infinite loop when RefCountedSharedArena's underlying
Arena#close fails due to concurrent usage of segments. (Uwe Schindler)
+* GITHUB#14974: Lucene tessellator now always fails if it cannot process a hole instead of just ignoring it.
+ (Ignacio Vera)
+
Build
---------------------
* Upgrade forbiddenapis to version 3.9. (Uwe Schindler)
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 bc53006175f..bd7025e979d 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
@@ -43,6 +43,7 @@ import org.apache.lucene.util.BitUtil;
* <li>Requires valid polygons:
* <ul>
* <li>No self intersections
+ * <li>Holes must be inside the polygon
* <li>Holes may only touch at one vertex
* <li>Polygon must have an area (e.g., no "line" boxes)
* <li>sensitive to overflow (e.g, subatomic values such as E-200 can cause unexpected
@@ -339,16 +340,31 @@ public final class Tessellator {
holeMinY = holePoly.minY;
holeMaxY = holePoly.maxY;
}
- eliminateHole(holeNode, outerNode, holeMinX, holeMaxX, holeMinY, holeMaxY);
- // Filter the new polygon.
- outerNode = filterPoints(outerNode, outerNode.next);
+ if (eliminateHole(holeNode, outerNode, holeMinX, holeMaxX, holeMinY, holeMaxY)) {
+ // Filter the new polygon.
+ outerNode = filterPoints(outerNode, outerNode.next);
+ } else {
+ // we couldn't find a point to the left of the hole's leftmost point, the point
+ // is not inside the polygon.
+ String polygon;
+ if (h instanceof Polygon holePoly) {
+ polygon = Polygon.verticesToGeoJSON(holePoly.getPolyLats(), holePoly.getPolyLons());
+ } else {
+ XYPolygon holePoly = (XYPolygon) h;
+ polygon = XYPolygon.verticesToGeoJSON(holePoly.getPolyX(), holePoly.getPolyY());
+ }
+ if (polygon.length() > 100) {
+ polygon = polygon.substring(0, 100) + "...";
+ }
+ throw new IllegalArgumentException("Illegal hole detected: " + polygon);
+ }
}
// Return a pointer to the list.
return outerNode;
}
/** Finds a bridge between vertices that connects a hole with an outer ring, and links it */
- private static void eliminateHole(
+ private static boolean eliminateHole(
final Node holeNode,
Node outerNode,
double holeMinX,
@@ -359,7 +375,7 @@ public final class Tessellator {
// Attempt to merge the hole using a common point between if it exists.
if (maybeMergeHoleWithSharedVertices(
holeNode, outerNode, holeMinX, holeMaxX, holeMinY, holeMaxY)) {
- return;
+ return true;
}
// Attempt to find a logical bridge between the HoleNode and OuterNode.
outerNode = fetchHoleBridge(holeNode, outerNode);
@@ -374,6 +390,9 @@ public final class Tessellator {
Node node = splitPolygon(outerNode, holeNode, fromPolygon);
// Filter the split nodes.
filterPoints(node, node.next);
+ return true;
+ } else {
+ return false;
}
}
diff --git a/lucene/core/src/java/org/apache/lucene/geo/XYPolygon.java b/lucene/core/src/java/org/apache/lucene/geo/XYPolygon.java
index ef55e52d339..e1511932d4f 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/XYPolygon.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/XYPolygon.java
@@ -184,6 +184,19 @@ public final class XYPolygon extends XYGeometry {
return true;
}
+ public static String verticesToGeoJSON(final float[] xs, final float[] ys) {
+ StringBuilder sb = new StringBuilder();
+ sb.append('[');
+ for (int i = 0; i < xs.length; i++) {
+ sb.append("[").append(xs[i]).append(", ").append(ys[i]).append("]");
+ if (i != xs.length - 1) {
+ sb.append(", ");
+ }
+ }
+ sb.append(']');
+ return sb.toString();
+ }
+
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
diff --git a/lucene/core/src/test/org/apache/lucene/document/TestShapeDocValues.java b/lucene/core/src/test/org/apache/lucene/document/TestShapeDocValues.java
index 58d223492c0..c389f6d5465 100644
--- a/lucene/core/src/test/org/apache/lucene/document/TestShapeDocValues.java
+++ b/lucene/core/src/test/org/apache/lucene/document/TestShapeDocValues.java
@@ -49,7 +49,7 @@ public class TestShapeDocValues extends LuceneTestCase {
assertEquals(
dv.relate(LatLonGeometry.create(new Rectangle(-0.25, -0.24, -3.8, -3.7))),
PointValues.Relation.CELL_OUTSIDE_QUERY);
- assertNotEquals(
+ assertEquals(
dv.relate(LatLonGeometry.create(new Rectangle(-1.2, 1.2, -1.5, 1.7))),
PointValues.Relation.CELL_CROSSES_QUERY);
}
@@ -214,15 +214,14 @@ public class TestShapeDocValues extends LuceneTestCase {
}
private Polygon getTestPolygonWithHole() {
- Polygon poly = GeoTestUtil.createRegularPolygon(0.0, 0.0, 100000, 7);
+ Polygon poly = GeoTestUtil.createRegularPolygon(0.0, 0.0, 500000, 7);
Polygon inner =
new Polygon(
new double[] {-1.0, -1.0, 0.5, 1.0, 1.0, 0.5, -1.0},
new double[] {1.0, -1.0, -0.5, -1.0, 1.0, 0.5, 1.0});
Polygon inner2 =
new Polygon(
- new double[] {-1.0, -1.0, 0.5, 1.0, 1.0, 0.5, -1.0},
- new double[] {-2.0, -4.0, -3.5, -4.0, -2.0, -2.5, -2.0});
+ new double[] {-1.0, -1.0, 1.0, 1.0, -1.0}, new double[] {-2.0, -4.0, -4.0, -2.0, -2.0});
return new Polygon(poly.getPolyLats(), poly.getPolyLons(), inner, inner2);
}
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 e2e964526e8..8b0e809d7b3 100644
--- a/lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java
+++ b/lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java
@@ -57,7 +57,7 @@ public class TestTessellator extends LuceneTestCase {
}
public void testSimpleTessellation() throws Exception {
- Polygon poly = GeoTestUtil.createRegularPolygon(0.0, 0.0, 100000, 100000);
+ Polygon poly = GeoTestUtil.createRegularPolygon(0.0, 0.0, 1000000, 100000);
Polygon inner =
new Polygon(
new double[] {-1.0, -1.0, 0.5, 1.0, 1.0, 0.5, -1.0},
@@ -199,6 +199,37 @@ public class TestTessellator extends LuceneTestCase {
assertEquals("at least three non-collinear points required", ex.getMessage());
}
+ public void testInvalidPolygonHoleDisjoint() throws Exception {
+ String wkt =
+ "POLYGON((172.42 51.3, 180.0 51.3, 180.0 71.4, 172.42 71.4, 172.42 51.3), "
+ + "(-180.0 51.3, -129.99 51.3, -129.99 71.4, -180.0 71.4, -180.0 51.3))";
+ Polygon polygon = (Polygon) SimpleWKTShapeParser.parse(wkt);
+ IllegalArgumentException ex =
+ expectThrows(IllegalArgumentException.class, () -> Tessellator.tessellate(polygon, true));
+ assertEquals(
+ "Illegal hole detected: [[-180.0, 51.3], [-129.99, 51.3], [-129.99, 71.4], [-180.0, 71.4], [-180.0, 51.3]]",
+ ex.getMessage());
+
+ float[] xs = new float[polygon.numPoints()];
+ float[] ys = new float[polygon.numPoints()];
+ for (int i = 0; i < polygon.numPoints(); i++) {
+ xs[i] = (float) polygon.getPolyLon(i);
+ ys[i] = (float) polygon.getPolyLat(i);
+ }
+ float[] xsHole = new float[polygon.getHole(0).numPoints()];
+ float[] ysHole = new float[polygon.getHole(0).numPoints()];
+ for (int i = 0; i < polygon.getHole(0).numPoints(); i++) {
+ xsHole[i] = (float) polygon.getHole(0).getPolyLon(i);
+ ysHole[i] = (float) polygon.getHole(0).getPolyLat(i);
+ }
+ XYPolygon xyPolygon = new XYPolygon(xs, ys, new XYPolygon(xsHole, ysHole));
+ ex =
+ expectThrows(IllegalArgumentException.class, () -> Tessellator.tessellate(xyPolygon, true));
+ assertEquals(
+ "Illegal hole detected: [[-180.0, 51.3], [-129.99, 51.3], [-129.99, 71.4], [-180.0, 71.4], [-180.0, 51.3]]",
+ ex.getMessage());
+ }
+
public void testComplexPolygon01() throws Exception {
String wkt =
"POLYGON((58.8792517 54.9160937, 58.8762477 54.9154524, 58.8735011 54.9140217, 58.8726428 54.9127389, 58.8731146 54.9122507, 58.8741877 54.9120482, 58.8771918 54.9117028, 58.88011 54.913331, 58.8801175 54.9137036, 58.8805885 54.9143186, 58.8807109 54.9148604, 58.88011 54.915551, 58.8792517 54.9160937), "