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/19 07:43:11 UTC
[lucene-solr] branch branch_8_4 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_8_4
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git
The following commit(s) were added to refs/heads/branch_8_4 by this push:
new 4812596 LUCENE-9055: Fix the detection of lines crossing triangles through edge points (#1020)
4812596 is described below
commit 481259621367d8df12b43303d5cfc134a1e0f93c
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)
# Conflicts:
# lucene/CHANGES.txt
---
lucene/CHANGES.txt | 3 ++
.../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(+), 21 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 51ba3f8..a9de565 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -79,6 +79,9 @@ Bug Fixes
* LUCENE-8996: maxScore was sometimes missing from distributed grouped responses.
(Julien Massenet, Diego Ceccarelli, Munendra S N, Christine Poerschke)
+* LUCENE-9055: Fix the detection of lines crossing triangles through edge points.
+ (Ignacio Vera)
+
Other
* LUCENE-8979: Code Cleanup: Use entryset for map iteration wherever possible. - Part 2 (Koen De Groote)
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);
+ }
}