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/03/12 07:41:00 UTC
[lucene-solr] branch master updated: LUCENE-8712: Polygon2D does
not detect crossings in some cases (#598)
This is an automated email from the ASF dual-hosted git repository.
ivera pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git
The following commit(s) were added to refs/heads/master by this push:
new 4582053 LUCENE-8712: Polygon2D does not detect crossings in some cases (#598)
4582053 is described below
commit 458205396efa160ec92829f45971103a0c4e6892
Author: Ignacio Vera <iv...@gmail.com>
AuthorDate: Tue Mar 12 08:40:54 2019 +0100
LUCENE-8712: Polygon2D does not detect crossings in some cases (#598)
LUCENE-8712: revert crossing logic to use boolean logic and skip lines
over the dateline to support dateline crossing logic
---
lucene/CHANGES.txt | 5 +++
.../src/java/org/apache/lucene/geo/EdgeTree.java | 47 +++++++++-------------
.../src/java/org/apache/lucene/geo/GeoUtils.java | 23 ++++-------
.../src/java/org/apache/lucene/geo/Polygon2D.java | 4 +-
.../test/org/apache/lucene/geo/TestPolygon2D.java | 30 ++++++++++++++
.../src/java/org/apache/lucene/geo/Line2D.java | 5 ++-
.../apache/lucene/document/TestLatLonShape.java | 27 ++++++++++---
7 files changed, 87 insertions(+), 54 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index d2c27e4..c395666 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -17,6 +17,11 @@ Bug fixes:
======================= Lucene 8.1.0 =======================
+Bug fixes
+
+* LUCENE-8712: Polygon2D does not detect crossings through segment edges.
+ (Ignacio Vera)
+
Improvements
* LUCENE-8673: Use radix partitioning when merging dimensional points instead
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 55a3379..aa25ff0 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/EdgeTree.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/EdgeTree.java
@@ -22,7 +22,7 @@ import java.util.Comparator;
import org.apache.lucene.index.PointValues.Relation;
import org.apache.lucene.util.ArrayUtil;
-import static org.apache.lucene.geo.GeoUtils.lineRelateLine;
+import static org.apache.lucene.geo.GeoUtils.lineCrossesLine;
import static org.apache.lucene.geo.GeoUtils.orient;
/**
@@ -211,6 +211,8 @@ public abstract class EdgeTree {
// lat-lon pair (in original order) of the two vertices
final double lat1, lat2;
final double lon1, lon2;
+ //edge belongs to the dateline
+ final boolean dateline;
/** min of this edge */
final double low;
/** max latitude of this edge or any children */
@@ -228,17 +230,18 @@ public abstract class EdgeTree {
this.lon2 = lon2;
this.low = low;
this.max = max;
+ dateline = (lon1 == GeoUtils.MIN_LON_INCL && lon2 == GeoUtils.MIN_LON_INCL)
+ || (lon1 == GeoUtils.MAX_LON_INCL && lon2 == GeoUtils.MAX_LON_INCL);
}
/** Returns true if the triangle crosses any edge in this edge subtree */
- Relation relateTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
+ boolean crossesTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
// compute bounding box of triangle
double minLat = StrictMath.min(StrictMath.min(ay, by), cy);
double minLon = StrictMath.min(StrictMath.min(ax, bx), cx);
double maxLat = StrictMath.max(StrictMath.max(ay, by), cy);
double maxLon = StrictMath.max(StrictMath.max(ax, bx), cx);
- Relation r = Relation.CELL_OUTSIDE_QUERY;
if (minLat <= max) {
double dy = lat1;
double ey = lat2;
@@ -252,53 +255,39 @@ public abstract class EdgeTree {
(dx < minLon && ex < minLon) ||
(dx > maxLon && ex > maxLon);
- if (outside == false) {
- int insideEdges = 0;
+ if (dateline == false && outside == false) {
// does triangle's first edge intersect polyline?
// ax, ay -> bx, by
- if ((r = lineRelateLine(ax, ay, bx, by, dx, dy, ex, ey)) == Relation.CELL_CROSSES_QUERY) {
- return r;
- } else if (r == Relation.CELL_INSIDE_QUERY) {
- ++insideEdges;
+ if (lineCrossesLine(ax, ay, bx, by, dx, dy, ex, ey)) {
+ return true;
}
// does triangle's second edge intersect polyline?
// bx, by -> cx, cy
- if ((r = lineRelateLine(bx, by, cx, cy, dx, dy, ex, ey)) == Relation.CELL_CROSSES_QUERY) {
- return r;
- } else if (r == Relation.CELL_INSIDE_QUERY) {
- ++insideEdges;
+ if (lineCrossesLine(bx, by, cx, cy, dx, dy, ex, ey)) {
+ return true;
}
// does triangle's third edge intersect polyline?
// cx, cy -> ax, ay
- if ((r = lineRelateLine(cx, cy, ax, ay, dx, dy, ex, ey)) == Relation.CELL_CROSSES_QUERY) {
- return r;
- } else if (r == Relation.CELL_INSIDE_QUERY) {
- ++insideEdges;
- }
- if (insideEdges == 3) {
- // fully inside, we can return
- return Relation.CELL_INSIDE_QUERY;
- } else {
- //reset relation to not crossing
- r = Relation.CELL_OUTSIDE_QUERY;
+ if (lineCrossesLine(cx, cy, ax, ay, dx, dy, ex, ey)) {
+ return true;
}
}
if (left != null) {
- if ((r = left.relateTriangle(ax, ay, bx, by, cx, cy)) != Relation.CELL_OUTSIDE_QUERY) {
- return r;
+ if (left.crossesTriangle(ax, ay, bx, by, cx, cy)) {
+ return true;
}
}
if (right != null && maxLat >= low) {
- if ((r = right.relateTriangle(ax, ay, bx, by, cx, cy)) != Relation.CELL_OUTSIDE_QUERY) {
- return r;
+ if (right.crossesTriangle(ax, ay, bx, by, cx, cy)) {
+ return true;
}
}
}
- return r;
+ return false;
}
/** Returns true if the box crosses any edge in this edge subtree */
diff --git a/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java b/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
index eb797e2..0c73032 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
@@ -194,27 +194,18 @@ public final class GeoUtils {
}
}
- /**
- * uses orient method to compute relation between two line segments
- * note the following return values:
- * CELL_CROSSES_QUERY - if the two line segments fully cross
- * CELL_INSIDE_QUERY - if the one line segment terminates on the other
- * CELL_OUTSIDE_QUERY - if the two segments do not cross
- **/
- public static Relation lineRelateLine(double a1x, double a1y, double b1x, double b1y, double a2x, double a2y, double b2x, double b2y) {
+ /** uses orient method to compute whether two line segments cross */
+ public static boolean lineCrossesLine(double a1x, double a1y, double b1x, double b1y, double a2x, double a2y, double b2x, double b2y) {
// shortcut: either "line" is actually a point
if ((a1x == b1x && a1y == b1y) || (a2x == b2x && a2y == b2y)) {
- return Relation.CELL_OUTSIDE_QUERY;
+ return false;
}
- int a = orient(a2x, a2y, b2x, b2y, a1x, a1y) * orient(a2x, a2y, b2x, b2y, b1x, b1y);
- int b = orient(a1x, a1y, b1x, b1y, a2x, a2y) * orient(a1x, a1y, b1x, b1y, b2x, b2y);
-
- if (a <= 0 && b <= 0) {
- return a == 0 || b == 0 ? Relation.CELL_INSIDE_QUERY : Relation.CELL_CROSSES_QUERY;
+ if (orient(a2x, a2y, b2x, b2y, a1x, a1y) * orient(a2x, a2y, b2x, b2y, b1x, b1y) <= 0 &&
+ orient(a1x, a1y, b1x, b1y, a2x, a2y) * orient(a1x, a1y, b1x, b1y, b2x, b2y) <= 0) {
+ return true;
}
-
- return Relation.CELL_OUTSIDE_QUERY;
+ return false;
}
/**
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 0ba3d51..47ab259 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
@@ -122,7 +122,7 @@ public final class Polygon2D extends EdgeTree {
// 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.relateTriangle(ax, ay, bx, by, cx, cy) == Relation.CELL_CROSSES_QUERY) {
+ if (tree.crossesTriangle(ax, ay, bx, by, cx, cy)) {
return Relation.CELL_CROSSES_QUERY;
}
return Relation.CELL_INSIDE_QUERY;
@@ -130,7 +130,7 @@ public final class Polygon2D extends EdgeTree {
if (pointInTriangle(tree.lon1, tree.lat1, ax, ay, bx, by, cx, cy) == true) {
return Relation.CELL_CROSSES_QUERY;
}
- if (tree.relateTriangle(ax, ay, bx, by, cx, cy) == Relation.CELL_CROSSES_QUERY) {
+ if (tree.crossesTriangle(ax, ay, bx, by, cx, cy)) {
return Relation.CELL_CROSSES_QUERY;
}
return Relation.CELL_OUTSIDE_QUERY;
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 f85536a..ff2c894 100644
--- a/lucene/core/src/test/org/apache/lucene/geo/TestPolygon2D.java
+++ b/lucene/core/src/test/org/apache/lucene/geo/TestPolygon2D.java
@@ -25,6 +25,7 @@ import static org.apache.lucene.geo.GeoTestUtil.nextPolygon;
import com.carrotsearch.randomizedtesting.generators.RandomNumbers;
import org.apache.lucene.index.PointValues.Relation;
import org.apache.lucene.util.LuceneTestCase;
+import org.apache.lucene.util.TestUtil;
/** Test Polygon2D impl */
public class TestPolygon2D extends LuceneTestCase {
@@ -338,4 +339,33 @@ public class TestPolygon2D extends LuceneTestCase {
}
}
}
+
+ public void testLineCrossingPolygonPoints() {
+ Polygon p = new Polygon(new double[] {0, -1, 0, 1, 0}, new double[] {-1, 0, 1, 0, -1});
+ Polygon2D polygon2D = Polygon2D.create(p);
+ Relation rel = polygon2D.relateTriangle(GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(-1.5)),
+ GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0)),
+ GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(1.5)),
+ GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0)),
+ GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(-1.5)),
+ GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0)));
+ assertEquals(Relation.CELL_CROSSES_QUERY, rel);
+ }
+
+ public void testRandomLineCrossingPolygon() {
+ Polygon p = GeoTestUtil.createRegularPolygon(0, 0, 1000, TestUtil.nextInt(random(), 100, 10000));
+ Polygon2D polygon2D = Polygon2D.create(p);
+ for (int i=0; i < 1000; i ++) {
+ double longitude = GeoTestUtil.nextLongitude();
+ double latitude = GeoTestUtil.nextLatitude();
+ Relation rel = polygon2D.relateTriangle(
+ GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(-longitude)),
+ GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(-latitude)),
+ GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(longitude)),
+ GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(latitude)),
+ GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(-longitude)),
+ GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(-latitude)));
+ assertNotEquals(Relation.CELL_OUTSIDE_QUERY, rel);
+ }
+ }
}
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 94d9222..7aff1aa 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/geo/Line2D.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/geo/Line2D.java
@@ -50,6 +50,9 @@ public final class Line2D extends EdgeTree {
@Override
protected PointValues.Relation componentRelateTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
- return tree.relateTriangle(ax, ay, bx, by, cx, cy);
+ if (tree.crossesTriangle(ax, ay, bx, by, cx, cy)) {
+ return PointValues.Relation.CELL_CROSSES_QUERY;
+ }
+ return PointValues.Relation.CELL_OUTSIDE_QUERY;
}
}
\ No newline at end of file
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 ce99487..79af141 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShape.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShape.java
@@ -309,6 +309,21 @@ public class TestLatLonShape extends LuceneTestCase {
Query q = LatLonShape.newPolygonQuery("test", QueryRelation.WITHIN, searchPoly);
assertEquals(1, searcher.count(q));
+ q = LatLonShape.newPolygonQuery("test", QueryRelation.INTERSECTS, searchPoly);
+ assertEquals(1, searcher.count(q));
+
+ q = LatLonShape.newPolygonQuery("test", QueryRelation.DISJOINT, searchPoly);
+ assertEquals(0, searcher.count(q));
+
+ q = LatLonShape.newBoxQuery("test", QueryRelation.WITHIN, -20, 20, 170, -170);
+ assertEquals(1, searcher.count(q));
+
+ q = LatLonShape.newBoxQuery("test", QueryRelation.INTERSECTS, -20, 20, 170, -170);
+ assertEquals(1, searcher.count(q));
+
+ q = LatLonShape.newBoxQuery("test", QueryRelation.DISJOINT, -20, 20, 170, -170);
+ assertEquals(0, searcher.count(q));
+
IOUtils.close(w, reader, dir);
}
@@ -327,7 +342,7 @@ public class TestLatLonShape extends LuceneTestCase {
GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(alon)),
GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(alat)));
- assertEquals(PointValues.Relation.CELL_OUTSIDE_QUERY, rel);
+ assertEquals(PointValues.Relation.CELL_CROSSES_QUERY, rel);
rel = polygon2D.relateTriangle(GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(alon)),
GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(blat)),
@@ -336,7 +351,7 @@ public class TestLatLonShape extends LuceneTestCase {
GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(blon)),
GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(blat)));
- assertEquals(PointValues.Relation.CELL_OUTSIDE_QUERY, rel);
+ assertEquals(PointValues.Relation.CELL_CROSSES_QUERY, rel);
}
public void testTriangleTouchingEdges() {
@@ -349,7 +364,7 @@ public class TestLatLonShape extends LuceneTestCase {
GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0.5)),
GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(0.5)),
GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(1)));
- assertEquals(PointValues.Relation.CELL_INSIDE_QUERY, rel);
+ assertEquals(PointValues.Relation.CELL_CROSSES_QUERY, rel);
//2 shared points
rel = polygon2D.relateTriangle(GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(0.5)),
GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0)),
@@ -357,7 +372,7 @@ public class TestLatLonShape extends LuceneTestCase {
GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0.5)),
GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(0.5)),
GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0.75)));
- assertEquals(PointValues.Relation.CELL_INSIDE_QUERY, rel);
+ assertEquals(PointValues.Relation.CELL_CROSSES_QUERY, rel);
//1 shared point
rel = polygon2D.relateTriangle(
GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(0.5)),
@@ -366,7 +381,7 @@ public class TestLatLonShape extends LuceneTestCase {
GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0)),
GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(0.75)),
GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0.75)));
- assertEquals(PointValues.Relation.CELL_INSIDE_QUERY, rel);
+ assertEquals(PointValues.Relation.CELL_CROSSES_QUERY, rel);
// 1 shared point but out
rel = polygon2D.relateTriangle(GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(1)),
GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0.5)),
@@ -390,7 +405,7 @@ public class TestLatLonShape extends LuceneTestCase {
GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(1)),
GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(0.5)),
GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0.5)));
- assertEquals(PointValues.Relation.CELL_INSIDE_QUERY, rel);
+ assertEquals(PointValues.Relation.CELL_CROSSES_QUERY, rel);
//share one edge outside
rel = polygon2D.relateTriangle(GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(0)),
GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(1)),