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 2019/12/17 08:43:46 UTC
[lucene-solr] branch branch_8x updated: LUCENE-9055: Fix the
detection of lines crossing triangles through edge points (#1020)
This is an automated email from the ASF dual-hosted git repository.
ivera pushed a commit to branch branch_8x
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git
The following commit(s) were added to refs/heads/branch_8x by this push:
new f08a830 LUCENE-9055: Fix the detection of lines crossing triangles through edge points (#1020)
f08a830 is described below
commit f08a830a6a4880cb397cf7d071460e37ea6f8e10
Author: Ignacio Vera <iv...@apache.org>
AuthorDate: Tue Dec 17 09:38:58 2019 +0100
LUCENE-9055: Fix the detection of lines crossing triangles through edge points (#1020)
---
lucene/CHANGES.txt | 4 +-
.../src/java/org/apache/lucene/geo/EdgeTree.java | 44 ++++++++++++++--------
.../src/java/org/apache/lucene/geo/Polygon2D.java | 8 ++--
.../src/java/org/apache/lucene/geo/Line2D.java | 2 +-
.../apache/lucene/document/TestLatLonShape.java | 40 ++++++++++++++++++++
5 files changed, 76 insertions(+), 22 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index af831fa..0af2c6f 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -23,7 +23,9 @@ Optimizations
Bug Fixes
---------------------
-(No changes)
+
+* LUCENE-9055: Fix the detection of lines crossing triangles through edge points.
+ (Ignacio Vera)
Other
---------------------
diff --git a/lucene/core/src/java/org/apache/lucene/geo/EdgeTree.java b/lucene/core/src/java/org/apache/lucene/geo/EdgeTree.java
index 418c91e..239dfcf 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/EdgeTree.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/EdgeTree.java
@@ -161,7 +161,7 @@ public class EdgeTree {
/** Returns true if the triangle crosses any edge in this edge subtree */
protected boolean crossesTriangle(double minX, double maxX, double minY, double maxY,
- double ax, double ay, double bx, double by, double cx, double cy) {
+ double ax, double ay, double bx, double by, double cx, double cy, boolean includeBoundary) {
if (minY <= max) {
double dy = y1;
double ey = y2;
@@ -176,18 +176,27 @@ public class EdgeTree {
(dx > maxX && ex > maxX);
if (outside == false) {
- if (lineCrossesLine(dx, dy, ex, ey, ax, ay, bx, by) ||
- lineCrossesLine(dx, dy, ex, ey, bx, by, cx, cy) ||
- lineCrossesLine(dx, dy, ex, ey, cx, cy, ax, ay)) {
- return true;
+ if (includeBoundary == true) {
+ if (lineCrossesLineWithBoundary(dx, dy, ex, ey, ax, ay, bx, by) ||
+ lineCrossesLineWithBoundary(dx, dy, ex, ey, bx, by, cx, cy) ||
+ lineCrossesLineWithBoundary(dx, dy, ex, ey, cx, cy, ax, ay)) {
+ return true;
+ }
+ } else {
+ if (lineCrossesLine(dx, dy, ex, ey, ax, ay, bx, by) ||
+ lineCrossesLine(dx, dy, ex, ey, bx, by, cx, cy) ||
+ lineCrossesLine(dx, dy, ex, ey, cx, cy, ax, ay)) {
+ return true;
+ }
}
}
- if (left != null && left.crossesTriangle(minX, maxX, minY, maxY, ax, ay, bx, by, cx, cy)) {
+
+ if (left != null && left.crossesTriangle(minX, maxX, minY, maxY, ax, ay, bx, by, cx, cy, includeBoundary)) {
return true;
}
- if (right != null && maxY >= low && right.crossesTriangle(minX, maxX, minY, maxY, ax, ay, bx, by, cx, cy)) {
+ if (right != null && maxY >= low && right.crossesTriangle(minX, maxX, minY, maxY, ax, ay, bx, by, cx, cy, includeBoundary)) {
return true;
}
}
@@ -222,18 +231,21 @@ public class EdgeTree {
(cx > maxX && dx > maxX);
if (outside == false) {
- if (includeBoundary == true &&
- lineCrossesLineWithBoundary(cx, cy, dx, dy, minX, minY, maxX, minY) ||
+ if (includeBoundary == true) {
+ if (lineCrossesLineWithBoundary(cx, cy, dx, dy, minX, minY, maxX, minY) ||
lineCrossesLineWithBoundary(cx, cy, dx, dy, maxX, minY, maxX, maxY) ||
lineCrossesLineWithBoundary(cx, cy, dx, dy, maxX, maxY, minX, maxY) ||
lineCrossesLineWithBoundary(cx, cy, dx, dy, minX, maxY, minX, minY)) {
- // include boundaries: ensures box edges that terminate on the polygon are included
- return true;
- } else if (lineCrossesLine(cx, cy, dx, dy, minX, minY, maxX, minY) ||
- lineCrossesLine(cx, cy, dx, dy, maxX, minY, maxX, maxY) ||
- lineCrossesLine(cx, cy, dx, dy, maxX, maxY, minX, maxY) ||
- lineCrossesLine(cx, cy, dx, dy, minX, maxY, minX, minY)) {
- return true;
+ // include boundaries: ensures box edges that terminate on the polygon are included
+ return true;
+ }
+ } else {
+ if (lineCrossesLine(cx, cy, dx, dy, minX, minY, maxX, minY) ||
+ lineCrossesLine(cx, cy, dx, dy, maxX, minY, maxX, maxY) ||
+ lineCrossesLine(cx, cy, dx, dy, maxX, maxY, minX, maxY) ||
+ lineCrossesLine(cx, cy, dx, dy, minX, maxY, minX, minY)) {
+ return true;
+ }
}
}
diff --git a/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java b/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
index f8f1709..e6eefd8 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
@@ -117,7 +117,7 @@ public class Polygon2D implements Component2D {
// check each corner: if < 4 && > 0 are present, its cheaper than crossesSlowly
int numCorners = numberOfCorners(minX, maxX, minY, maxY);
if (numCorners == 4) {
- if (tree.crossesBox(minX, maxX, minY, maxY, false)) {
+ if (tree.crossesBox(minX, maxX, minY, maxY, true)) {
return Relation.CELL_CROSSES_QUERY;
}
return Relation.CELL_INSIDE_QUERY;
@@ -125,7 +125,7 @@ public class Polygon2D implements Component2D {
if (Component2D.containsPoint(tree.x1, tree.y1, minX, maxX, minY, maxY)) {
return Relation.CELL_CROSSES_QUERY;
}
- if (tree.crossesBox(minX, maxX, minY, maxY, false)) {
+ if (tree.crossesBox(minX, maxX, minY, maxY, true)) {
return Relation.CELL_CROSSES_QUERY;
}
return Relation.CELL_OUTSIDE_QUERY;
@@ -255,7 +255,7 @@ public class Polygon2D implements Component2D {
// check each corner: if < 3 && > 0 are present, its cheaper than crossesSlowly
int numCorners = numberOfTriangleCorners(ax, ay, bx, by, cx, cy);
if (numCorners == 3) {
- if (tree.crossesTriangle(minX, maxX, minY, maxY, ax, ay, bx, by, cx, cy)) {
+ if (tree.crossesTriangle(minX, maxX, minY, maxY, ax, ay, bx, by, cx, cy, false)) {
return Relation.CELL_CROSSES_QUERY;
}
return Relation.CELL_INSIDE_QUERY;
@@ -263,7 +263,7 @@ public class Polygon2D implements Component2D {
if (Component2D.pointInTriangle(minX, maxX, minY, maxY, tree.x1, tree.y1, ax, ay, bx, by, cx, cy) == true) {
return Relation.CELL_CROSSES_QUERY;
}
- if (tree.crossesTriangle(minX, maxX, minY, maxY, ax, ay, bx, by, cx, cy)) {
+ if (tree.crossesTriangle(minX, maxX, minY, maxY, ax, ay, bx, by, cx, cy, false)) {
return Relation.CELL_CROSSES_QUERY;
}
return Relation.CELL_OUTSIDE_QUERY;
diff --git a/lucene/sandbox/src/java/org/apache/lucene/geo/Line2D.java b/lucene/sandbox/src/java/org/apache/lucene/geo/Line2D.java
index ab9c087..04deee9 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/geo/Line2D.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/geo/Line2D.java
@@ -126,7 +126,7 @@ public final class Line2D implements Component2D {
}
return Relation.CELL_OUTSIDE_QUERY;
} else if (Component2D.pointInTriangle(minX, maxX, minY, maxY, tree.x1, tree.y1, ax, ay, bx, by, cx, cy) == true ||
- tree.crossesTriangle(minX, maxX, minY, maxY, ax, ay, bx, by, cx, cy)) {
+ tree.crossesTriangle(minX, maxX, minY, maxY, ax, ay, bx, by, cx, cy, true)) {
// indexed "triangle" is a triangle:
return Relation.CELL_CROSSES_QUERY;
}
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 644bfbe..37b32c2 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShape.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShape.java
@@ -659,4 +659,44 @@ public class TestLatLonShape extends LuceneTestCase {
quantizeLon(-5), quantizeLat(0));
assertEquals(PointValues.Relation.CELL_CROSSES_QUERY, r);
}
+
+ public void testLUCENE9055() throws Exception {
+ Directory dir = newDirectory();
+ RandomIndexWriter w = new RandomIndexWriter(random(), dir);
+
+ // test polygons:
+ //[5, 5], [10, 6], [10, 10], [5, 10], [5, 5] ]
+ Polygon indexPoly1 = new Polygon(
+ new double[] {5d, 6d, 10d, 10d, 5d},
+ new double[] {5d, 10d, 10d, 5d, 5d}
+ );
+
+ // [ [6, 6], [9, 6], [9, 9], [6, 9], [6, 6] ]
+ Polygon indexPoly2 = new Polygon(
+ new double[] {6d, 6d, 9d, 9d, 6d},
+ new double[] {6d, 9d, 9d, 6d, 6d}
+ );
+
+ // index polygons:
+ Document doc;
+ addPolygonsToDoc(FIELDNAME, doc = new Document(), indexPoly1);
+ w.addDocument(doc);
+ addPolygonsToDoc(FIELDNAME, doc = new Document(), indexPoly2);
+ w.addDocument(doc);
+ w.forceMerge(1);
+
+ ///// search //////
+ IndexReader reader = w.getReader();
+ w.close();
+ IndexSearcher searcher = newSearcher(reader);
+
+ // [ [0, 0], [5, 5], [7, 7] ]
+ Line searchLine = new Line(new double[] {0, 5, 7}, new double[] {0, 5, 7});
+
+
+ Query q = LatLonShape.newLineQuery(FIELDNAME, QueryRelation.INTERSECTS, searchLine);
+ assertEquals(2, searcher.count(q));
+
+ IOUtils.close(w, reader, dir);
+ }
}