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/01/23 07:29:53 UTC
[lucene-solr] branch branch_7x updated: LUCENE-8654:
Polygon2D#relateTriangle returns the wrong answer if polygon is inside the
triangle
This is an automated email from the ASF dual-hosted git repository.
ivera pushed a commit to branch branch_7x
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git
The following commit(s) were added to refs/heads/branch_7x by this push:
new 5ac3bbc LUCENE-8654: Polygon2D#relateTriangle returns the wrong answer if polygon is inside the triangle
5ac3bbc is described below
commit 5ac3bbc539620bf8ba09f66f13c73b210715be68
Author: iverase <iv...@apache.org>
AuthorDate: Wed Jan 23 08:28:57 2019 +0100
LUCENE-8654: Polygon2D#relateTriangle returns the wrong answer if polygon is inside the triangle
---
lucene/CHANGES.txt | 3 +++
.../src/java/org/apache/lucene/geo/EdgeTree.java | 28 ++++++++++++++++++++++
.../test/org/apache/lucene/geo/TestPolygon2D.java | 6 +++++
3 files changed, 37 insertions(+)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 3169066..10248e3 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -34,6 +34,9 @@ Bug fixes:
* LUCENE-8649: LatLonShape's within and disjoint queries can return false positives with
indexed multi-shapes. (Ignacio Vera)
+* LUCENE-8654: Polygon2D#relateTriangle returns the wrong answer if polygon is inside
+ the triangle. (Ignacio Vera)
+
New Features
* LUCENE-8026: ExitableDirectoryReader may now time out queries that run on
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 d954f88..fc3540d 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/EdgeTree.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/EdgeTree.java
@@ -150,6 +150,11 @@ public abstract class EdgeTree {
if (tree.crossesTriangle(ax, ay, bx, by, cx, cy)) {
return Relation.CELL_CROSSES_QUERY;
}
+
+ if (pointInTriangle(tree.lon1, tree.lat1, ax, ay, bx, by, cx, cy) == true) {
+ return Relation.CELL_CROSSES_QUERY;
+ }
+
return Relation.CELL_OUTSIDE_QUERY;
}
@@ -379,6 +384,29 @@ public abstract class EdgeTree {
}
}
+ //This should be moved when LatLonShape is moved from sandbox!
+ /**
+ * Compute whether the given x, y point is in a triangle; uses the winding order method */
+ private static boolean pointInTriangle (double x, double y, double ax, double ay, double bx, double by, double cx, double cy) {
+ double minX = StrictMath.min(ax, StrictMath.min(bx, cx));
+ double minY = StrictMath.min(ay, StrictMath.min(by, cy));
+ double maxX = StrictMath.max(ax, StrictMath.max(bx, cx));
+ double maxY = StrictMath.max(ay, StrictMath.max(by, cy));
+ //check the bounding box because if the triangle is degenerated, e.g points and lines, we need to filter out
+ //coplanar points that are not part of the triangle.
+ if (x >= minX && x <= maxX && y >= minY && y <= maxY ) {
+ int a = orient(x, y, ax, ay, bx, by);
+ int b = orient(x, y, bx, by, cx, cy);
+ if (a == 0 || b == 0 || a < 0 == b < 0) {
+ int c = orient(x, y, cx, cy, ax, ay);
+ return c == 0 || (c < 0 == (b < 0 || a < 0));
+ }
+ return false;
+ } else {
+ return false;
+ }
+ }
+
/**
* Creates an edge interval tree from a set of geometry vertices.
* @return root node of the tree.
diff --git a/lucene/core/src/test/org/apache/lucene/geo/TestPolygon2D.java b/lucene/core/src/test/org/apache/lucene/geo/TestPolygon2D.java
index 053f008..f85536a 100644
--- a/lucene/core/src/test/org/apache/lucene/geo/TestPolygon2D.java
+++ b/lucene/core/src/test/org/apache/lucene/geo/TestPolygon2D.java
@@ -312,6 +312,12 @@ public class TestPolygon2D extends LuceneTestCase {
}
}
+ public void testRelateTriangleContainsPolygon() {
+ Polygon polygon = new Polygon(new double[]{0, 0, 1, 1, 0}, new double[]{0, 1, 1, 0, 0});
+ Polygon2D impl = Polygon2D.create(polygon);
+ assertEquals(Relation.CELL_CROSSES_QUERY, impl.relateTriangle(-10 , -1, 2, -1, 10, 10));
+ }
+
// test
public void testRelateTriangleEdgeCases() {
for (int i = 0; i < 100; ++i) {