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 2020/02/28 09:26:58 UTC
[lucene-solr] branch branch_8x updated: LUCENE-9250: Add support
for Circle2d#intersectsLine around the dateline. (#1289)
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 16663db LUCENE-9250: Add support for Circle2d#intersectsLine around the dateline. (#1289)
16663db is described below
commit 16663db0996108d01e848bdbf4f017eed16b7ebd
Author: Ignacio Vera <iv...@apache.org>
AuthorDate: Fri Feb 28 10:22:27 2020 +0100
LUCENE-9250: Add support for Circle2d#intersectsLine around the dateline. (#1289)
---
lucene/CHANGES.txt | 2 +
.../src/java/org/apache/lucene/geo/Circle2D.java | 75 ++++++++++++++--------
.../test/org/apache/lucene/geo/TestCircle2D.java | 13 ++++
3 files changed, 64 insertions(+), 26 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index c13cf6a..9ac5711 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -115,6 +115,8 @@ Bug Fixes
so an query for UNORDERED(foo, foo) would match a document containing 'foo'
only once. (Alan Woodward)
+* LUCENE-9250: Add support for Circle2d#intersectsLine around the dateline. (Ignacio Vera)
+
Other
---------------------
diff --git a/lucene/core/src/java/org/apache/lucene/geo/Circle2D.java b/lucene/core/src/java/org/apache/lucene/geo/Circle2D.java
index 18bc587..91690f1 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Circle2D.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Circle2D.java
@@ -112,7 +112,7 @@ class Circle2D implements Component2D {
// if any of the edges intersects an the edge belongs to the shape then it cannot be within.
// if it only intersects edges that do not belong to the shape, then it is a candidate
// we skip edges at the dateline to support shapes crossing it
- if (intersectsLine(ax, ay, bx, by)) {
+ if (calculator.intersectsLine(ax, ay, bx, by)) {
if (ab == true) {
return WithinRelation.NOTWITHIN;
} else {
@@ -120,14 +120,14 @@ class Circle2D implements Component2D {
}
}
- if (intersectsLine(bx, by, cx, cy)) {
+ if (calculator.intersectsLine(bx, by, cx, cy)) {
if (bc == true) {
return WithinRelation.NOTWITHIN;
} else {
relation = WithinRelation.CANDIDATE;
}
}
- if (intersectsLine(cx, cy, ax, ay)) {
+ if (calculator.intersectsLine(cx, cy, ax, ay)) {
if (ca == true) {
return WithinRelation.NOTWITHIN;
} else {
@@ -162,7 +162,7 @@ class Circle2D implements Component2D {
if (numCorners == 2) {
return Relation.CELL_INSIDE_QUERY;
} else if (numCorners == 0) {
- if (intersectsLine(a2x, a2y, b2x, b2y)) {
+ if (calculator.intersectsLine(a2x, a2y, b2x, b2y)) {
return Relation.CELL_CROSSES_QUERY;
}
return Relation.CELL_OUTSIDE_QUERY;
@@ -181,9 +181,9 @@ class Circle2D implements Component2D {
if (Component2D.pointInTriangle(minX, maxX, minY, maxY, calculator.geX(), calculator.getY(), ax, ay, bx, by, cx, cy) == true) {
return Relation.CELL_CROSSES_QUERY;
}
- if (intersectsLine(ax, ay, bx, by) ||
- intersectsLine(bx, by, cx, cy) ||
- intersectsLine(cx, cy, ax, ay)) {
+ if (calculator.intersectsLine(ax, ay, bx, by) ||
+ calculator.intersectsLine(bx, by, cx, cy) ||
+ calculator.intersectsLine(cx, cy, ax, ay)) {
return Relation.CELL_CROSSES_QUERY;
}
return Relation.CELL_OUTSIDE_QUERY;
@@ -210,14 +210,16 @@ class Circle2D implements Component2D {
return containsCount;
}
- // This methods in a new helper class XYUtil?
- private boolean intersectsLine(double aX, double aY, double bX, double bY) {
+ private static boolean intersectsLine(double centerX, double centerY, double aX, double aY, double bX, double bY, DistanceCalculator calculator) {
//Algorithm based on this thread : https://stackoverflow.com/questions/3120357/get-closest-point-to-a-line
- final double[] vectorAP = new double[] {calculator.geX() - aX, calculator.getY() - aY};
- final double[] vectorAB = new double[] {bX - aX, bY - aY};
+ final double vectorAPX = centerX - aX;
+ final double vectorAPY = centerY - aY;
- final double magnitudeAB = vectorAB[0] * vectorAB[0] + vectorAB[1] * vectorAB[1];
- final double dotProduct = vectorAP[0] * vectorAB[0] + vectorAP[1] * vectorAB[1];
+ final double vectorABX = bX - aX;
+ final double vectorABY = bY - aY;
+
+ final double magnitudeAB = vectorABX * vectorABX + vectorABY * vectorABY;
+ final double dotProduct = vectorAPX * vectorABX + vectorAPY * vectorABY;
final double distance = dotProduct / magnitudeAB;
@@ -225,8 +227,8 @@ class Circle2D implements Component2D {
return false;
}
- final double pX = aX + vectorAB[0] * distance;
- final double pY = aY + vectorAB[1] * distance;
+ final double pX = aX + vectorABX * distance;
+ final double pY = aY + vectorABY * distance;
final double minX = StrictMath.min(aX, bX);
final double minY = StrictMath.min(aY, bY);
@@ -234,31 +236,34 @@ class Circle2D implements Component2D {
final double maxY = StrictMath.max(aY, bY);
if (pX >= minX && pX <= maxX && pY >= minY && pY <= maxY) {
- return contains(pX, pY);
+ return calculator.contains(pX, pY);
}
return false;
}
private interface DistanceCalculator {
- Relation relate(double minX, double maxX, double minY, double maxY);
-
+ /** check if the point is within a distance */
boolean contains(double x, double y);
-
+ /** check if the line is within a distance */
+ boolean intersectsLine(double aX, double aY, double bX, double bY);
+ /** Relates this calculator to the provided bounding box */
+ Relation relate(double minX, double maxX, double minY, double maxY);
+ /** check if the bounding box is disjoint with this calculator bounding box */
boolean disjoint(double minX, double maxX, double minY, double maxY);
-
+ /** check if the bounding box is contains this calculator bounding box */
boolean within(double minX, double maxX, double minY, double maxY);
-
+ /** get min X of this calculator */
double getMinX();
-
+ /** get max X of this calculator */
double getMaxX();
-
+ /** get min Y of this calculator */
double getMinY();
-
+ /** get max Y of this calculator */
double getMaxY();
-
+ /** get center X */
double geX();
-
+ /** get center Y */
double getY();
}
@@ -322,6 +327,11 @@ class Circle2D implements Component2D {
}
@Override
+ public boolean intersectsLine(double aX, double aY, double bX, double bY) {
+ return Circle2D.intersectsLine(centerX, centerY, aX, aY, bX, bY, this);
+ }
+
+ @Override
public boolean disjoint(double minX, double maxX, double minY, double maxY) {
return Component2D.disjoint(this.minX, this.maxX, this.minY, this.maxY, minX, maxX, minY, maxY);
}
@@ -390,6 +400,19 @@ class Circle2D implements Component2D {
return SloppyMath.haversinSortKey(y, x, this.centerLat, this.centerLon) <= sortKey;
}
+
+ @Override
+ public boolean intersectsLine(double aX, double aY, double bX, double bY) {
+ if (Circle2D.intersectsLine(centerLon, centerLat, aX, aY, bX, bY, this)) {
+ return true;
+ }
+ if (crossesDateline) {
+ double newCenterLon = (centerLon > 0) ? centerLon - 360 : centerLon + 360;
+ return Circle2D.intersectsLine(newCenterLon, centerLat, aX, aY, bX, bY, this);
+ }
+ return false;
+ }
+
@Override
public boolean disjoint(double minX, double maxX, double minY, double maxY) {
if (crossesDateline) {
diff --git a/lucene/core/src/test/org/apache/lucene/geo/TestCircle2D.java b/lucene/core/src/test/org/apache/lucene/geo/TestCircle2D.java
index 3d58c8d..ce17284 100644
--- a/lucene/core/src/test/org/apache/lucene/geo/TestCircle2D.java
+++ b/lucene/core/src/test/org/apache/lucene/geo/TestCircle2D.java
@@ -60,6 +60,19 @@ public class TestCircle2D extends LuceneTestCase {
assertEquals(Component2D.WithinRelation.NOTWITHIN, circle2D.withinTriangle(ax, ay, true, bx, by, true, cx, cy, true));
}
+ public void testTriangleDateLineIntersects() {
+ Component2D circle2D = LatLonGeometry.create(new Circle(0, 179, 222400));
+ double ax = -179;
+ double ay = 1;
+ double bx = -179;
+ double by = -1;
+ double cx = -178;
+ double cy = 0;
+ // we just touch the edge from the dateline
+ assertEquals(PointValues.Relation.CELL_CROSSES_QUERY, circle2D.relateTriangle(ax, ay, bx, by , cx, cy));
+ assertEquals(Component2D.WithinRelation.NOTWITHIN, circle2D.withinTriangle(ax, ay, true, bx, by, true, cx, cy, true));
+ }
+
public void testTriangleContains() {
Component2D circle2D;
if (random().nextBoolean()) {