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 2022/08/12 15:54:29 UTC
[lucene] branch main updated: LUCENE-10654: Fix ShapeDocValue Bounding Box failure (#1066)
This is an automated email from the ASF dual-hosted git repository.
nknize 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 543910d9008 LUCENE-10654: Fix ShapeDocValue Bounding Box failure (#1066)
543910d9008 is described below
commit 543910d9008e714016db8a799058860b8ece5565
Author: Nick Knize <nk...@apache.org>
AuthorDate: Fri Aug 12 10:54:22 2022 -0500
LUCENE-10654: Fix ShapeDocValue Bounding Box failure (#1066)
The base spatial test case may create invalid self crossing polygons. These
polygons are cleaned by the tessellator which may result in an inconsistent
bounding box between the tessellated shape and the original, invalid, geometry.
This commit fixes the shape doc value test case to compute the bounding box from
the cleaned geometry instead of relying on the, potentially invalid, original
geometry.
Signed-off-by: Nicholas Walter Knize <nk...@apache.org>
---
.../java/org/apache/lucene/geo/Tessellator.java | 3 +-
.../apache/lucene/document/TestShapeDocValues.java | 49 +++++++++++++++++++++-
2 files changed, 49 insertions(+), 3 deletions(-)
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 be6a3efce0a..e93958a96d3 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
@@ -194,7 +194,7 @@ public final class Tessellator {
sortByMorton(outerNode);
}
}
- if (checkSelfIntersections) {
+ if (checkSelfIntersections == true) {
checkIntersection(outerNode, mortonOptimized);
}
// Calculate the tessellation using the doubly LinkedList.
@@ -1060,6 +1060,7 @@ public final class Tessellator {
return isPointInLine(a, b, point.getX(), point.getY());
}
+ /** returns true if the lon, lat point is colinear w/ the provided a and b point */
private static boolean isPointInLine(
final Node a, final Node b, final double lon, final double lat) {
final double dxc = lon - a.getX();
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 e00cd82156f..f89f614471e 100644
--- a/lucene/core/src/test/org/apache/lucene/document/TestShapeDocValues.java
+++ b/lucene/core/src/test/org/apache/lucene/document/TestShapeDocValues.java
@@ -56,7 +56,7 @@ public class TestShapeDocValues extends LuceneTestCase {
public void testLatLonPolygonBBox() {
Polygon p = GeoTestUtil.nextPolygon();
- Rectangle expected = new Rectangle(p.minLat, p.maxLat, p.minLon, p.maxLon);
+ Rectangle expected = (Rectangle) computeBoundingBox(p);
LatLonShapeDocValuesField dv = LatLonShape.createDocValueField(FIELD_NAME, p);
assertEquals(expected.minLat, dv.getBoundingBox().minLat, TOLERANCE);
assertEquals(expected.maxLat, dv.getBoundingBox().maxLat, TOLERANCE);
@@ -66,7 +66,7 @@ public class TestShapeDocValues extends LuceneTestCase {
public void testXYPolygonBBox() {
XYPolygon p = (XYPolygon) BaseXYShapeTestCase.ShapeType.POLYGON.nextShape();
- XYRectangle expected = new XYRectangle(p.minX, p.maxX, p.minY, p.maxY);
+ XYRectangle expected = (XYRectangle) computeBoundingBox(p);
XYShapeDocValuesField dv = XYShape.createDocValueField(FIELD_NAME, p);
assertEquals(expected.minX, dv.getBoundingBox().minX, TOLERANCE);
assertEquals(expected.maxX, dv.getBoundingBox().maxX, TOLERANCE);
@@ -132,6 +132,51 @@ public class TestShapeDocValues extends LuceneTestCase {
return createPoint.apply(numXPly / totalSignedArea, numYPly / totalSignedArea);
}
+ /**
+ * compute the bounding box from the tessellation; test utils may create self crossing polygons
+ * cleaned by the tessellator
+ */
+ private Geometry computeBoundingBox(Geometry p) {
+ List<ShapeField.DecodedTriangle> tess = getTessellation(p);
+ IntFunction<Double> decodeX =
+ p instanceof Polygon
+ ? (x) -> GeoEncodingUtils.decodeLongitude(x)
+ : (x) -> (double) XYEncodingUtils.decode(x);
+ IntFunction<Double> decodeY =
+ p instanceof Polygon
+ ? (y) -> GeoEncodingUtils.decodeLatitude(y)
+ : (y) -> (double) XYEncodingUtils.decode(y);
+ BiFunction<Double[], Double[], Geometry> createRectangle =
+ p instanceof Polygon
+ ? (min, max) -> new Rectangle(min[1], max[1], min[0], max[0])
+ : (min, max) ->
+ new XYRectangle(
+ min[0].floatValue(),
+ max[0].floatValue(),
+ min[1].floatValue(),
+ max[1].floatValue());
+
+ double ax, bx, cx;
+ double ay, by, cy;
+ double minX = Double.MAX_VALUE;
+ double minY = Double.MAX_VALUE;
+ double maxX = -Double.MAX_VALUE;
+ double maxY = -Double.MAX_VALUE;
+ for (ShapeField.DecodedTriangle t : tess) {
+ ax = decodeX.apply(t.aX);
+ ay = decodeY.apply(t.aY);
+ bx = decodeX.apply(t.bX);
+ by = decodeY.apply(t.bY);
+ cx = decodeX.apply(t.cX);
+ cy = decodeY.apply(t.cY);
+ minX = Math.min(minX, Math.min(ax, Math.min(bx, cx)));
+ maxX = Math.max(maxX, Math.max(ax, Math.max(bx, cx)));
+ minY = Math.min(minY, Math.min(ay, Math.min(by, cy)));
+ maxY = Math.max(maxY, Math.max(ay, Math.max(by, cy)));
+ }
+ return createRectangle.apply(new Double[] {minX, minY}, new Double[] {maxX, maxY});
+ }
+
public void testExplicitLatLonPolygonCentroid() throws Exception {
String mp = "POLYGON((-80 -10, -40 -10, -40 10, -80 10, -80 -10))";
Polygon p = (Polygon) SimpleWKTShapeParser.parse(mp);