You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by rm...@apache.org on 2016/03/21 16:52:40 UTC
lucene-solr:branch_6_0: LUCENE-7123: deduplicate/cleanup spatial
distance
Repository: lucene-solr
Updated Branches:
refs/heads/branch_6_0 1201524d8 -> c49e761c1
LUCENE-7123: deduplicate/cleanup spatial distance
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/c49e761c
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/c49e761c
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/c49e761c
Branch: refs/heads/branch_6_0
Commit: c49e761c1bac84efa1e92a6a7b0f2169bba2612a
Parents: 1201524
Author: Robert Muir <rm...@apache.org>
Authored: Mon Mar 21 10:15:54 2016 -0400
Committer: Robert Muir <rm...@apache.org>
Committed: Mon Mar 21 11:27:55 2016 -0400
----------------------------------------------------------------------
.../java/org/apache/lucene/util/SloppyMath.java | 120 +++++++------------
.../org/apache/lucene/util/TestSloppyMath.java | 97 +++++++++++----
.../demo/facet/DistanceFacetsExample.java | 3 +-
.../js/JavascriptCompiler.properties | 2 +-
.../lucene/expressions/TestDemoExpressions.java | 6 +-
.../expressions/js/TestJavascriptFunction.java | 2 +-
.../document/LatLonPointDistanceQuery.java | 12 +-
.../document/TestLatLonPointDistanceQuery.java | 59 ++++++++-
.../lucene/search/TestLatLonPointQueries.java | 8 +-
.../geopoint/search/GeoPointDistanceQuery.java | 2 +-
.../search/GeoPointDistanceQueryImpl.java | 4 +-
.../search/GeoPointInBBoxQueryImpl.java | 2 +-
.../geopoint/search/GeoPointMultiTermQuery.java | 2 +-
.../lucene/spatial/util/GeoDistanceUtils.java | 32 +----
.../lucene/spatial/util/GeoProjectionUtils.java | 34 +++---
.../lucene/spatial/util/GeoRelationUtils.java | 64 +++++-----
.../apache/lucene/spatial/util/GeoUtils.java | 46 ++++++-
.../geopoint/search/TestGeoPointQuery.java | 6 +-
.../spatial/util/BaseGeoPointTestCase.java | 3 +-
.../lucene/spatial/util/TestGeoUtils.java | 5 +-
20 files changed, 298 insertions(+), 211 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c49e761c/lucene/core/src/java/org/apache/lucene/util/SloppyMath.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/SloppyMath.java b/lucene/core/src/java/org/apache/lucene/util/SloppyMath.java
index 8da8276..e3ba489 100644
--- a/lucene/core/src/java/org/apache/lucene/util/SloppyMath.java
+++ b/lucene/core/src/java/org/apache/lucene/util/SloppyMath.java
@@ -33,6 +33,32 @@ package org.apache.lucene.util;
public class SloppyMath {
/**
+ * Returns the Haversine distance in meters between two points
+ * specified in decimal degrees (latitude/longitude). This works correctly
+ * even if the dateline is between the two points.
+ * <p>
+ * Error is around 1E-5 (0.01mm) from the actual haversine distance.
+ *
+ * @param lat1 Latitude of the first point.
+ * @param lon1 Longitude of the first point.
+ * @param lat2 Latitude of the second point.
+ * @param lon2 Longitude of the second point.
+ * @return distance in meters.
+ */
+ public static double haversinMeters(double lat1, double lon1, double lat2, double lon2) {
+ return haversinMeters(haversinSortKey(lat1, lon1, lat2, lon2));
+ }
+
+ /**
+ * Returns the Haversine distance in meters between two points
+ * given the previous result from {@link #haversinSortKey(double, double, double, double)}
+ * @return distance in meters.
+ */
+ public static double haversinMeters(double sortKey) {
+ return TO_METERS * 2 * asin(Math.min(1, Math.sqrt(sortKey * 0.5)));
+ }
+
+ /**
* Returns the Haversine distance in kilometers between two points
* specified in decimal degrees (latitude/longitude). This works correctly
* even if the dateline is between the two points.
@@ -42,19 +68,26 @@ public class SloppyMath {
* @param lat2 Latitude of the second point.
* @param lon2 Longitude of the second point.
* @return distance in kilometers.
+ * @deprecated Use {@link #haversinMeters(double, double, double, double) instead}
*/
- public static double haversin(double lat1, double lon1, double lat2, double lon2) {
+ @Deprecated
+ public static double haversinKilometers(double lat1, double lon1, double lat2, double lon2) {
+ double h = haversinSortKey(lat1, lon1, lat2, lon2);
+ return TO_KILOMETERS * 2 * asin(Math.min(1, Math.sqrt(h * 0.5)));
+ }
+
+ /**
+ * Returns a sort key for distance. This is less expensive to compute than
+ * {@link #haversinMeters(double, double, double, double)}, but it always compares the same.
+ * This can be converted into an actual distance with {@link #haversinMeters(double)}, which
+ * effectively does the second half of the computation.
+ */
+ public static double haversinSortKey(double lat1, double lon1, double lat2, double lon2) {
double x1 = lat1 * TO_RADIANS;
double x2 = lat2 * TO_RADIANS;
double h1 = 1 - cos(x1 - x2);
double h2 = 1 - cos((lon1 - lon2) * TO_RADIANS);
- double h = (h1 + cos(x1) * cos(x2) * h2) / 2;
-
- double avgLat = (x1 + x2) / 2d;
- double diameter = earthDiameter(avgLat);
-
- return diameter * asin(Math.min(1, Math.sqrt(h)));
-
+ return h1 + cos(x1) * cos(x2) * h2;
}
/**
@@ -89,40 +122,6 @@ public class SloppyMath {
}
/**
- * Returns the trigonometric sine of an angle converted as a cos operation.
- * <p>
- * Error is around 1E-15.
- * <p>
- * Special cases:
- * <ul>
- * <li>If the argument is {@code NaN} or an infinity, then the result is {@code NaN}.
- * </ul>
- * @param a an angle, in radians.
- * @return the sine of the argument.
- * @see Math#cos(double)
- */
- public static double sin(double a) {
- return cos(a - PIO2);
- }
-
- /**
- * Returns the trigonometric tangent of an angle converted in terms of a sin/cos operation.
- * <p>
- * Error is around 1E-15.
- * <p>
- * Special cases:
- * <ul>
- * <li>If the argument is {@code NaN} or an infinity, then the result is {@code NaN}.
- * </ul>
- * @param a an angle, in radians.
- * @return the tangent of the argument.
- * @see Math#sin(double) aand Math#cos(double)
- */
- public static double tan(double a) {
- return sin(a) / cos(a);
- }
-
- /**
* Returns the arc sine of a value.
* <p>
* The returned angle is in the range <i>-pi</i>/2 through <i>pi</i>/2.
@@ -173,22 +172,18 @@ public class SloppyMath {
}
}
- /** Return an approximate value of the diameter of the earth at the given latitude, in kilometers. */
- public static double earthDiameter(double latitude) {
- final int index = (int)(Math.abs(latitude) * RADIUS_INDEXER + 0.5) % earthDiameterPerLatitude.length;
- return earthDiameterPerLatitude[index];
- }
-
// haversin
+ // TODO: remove these for java 9, they fixed Math.toDegrees()/toRadians() to work just like this.
public static final double TO_RADIANS = Math.PI / 180D;
public static final double TO_DEGREES = 180D / Math.PI;
+ private static final double TO_METERS = 6_378_137D; // equatorial radius
+ private static final double TO_KILOMETERS = 6_378.137D; // equatorial radius
// cos/asin
private static final double ONE_DIV_F2 = 1/2.0;
private static final double ONE_DIV_F3 = 1/6.0;
private static final double ONE_DIV_F4 = 1/24.0;
- public static final double PIO2 = Math.PI / 2D;
private static final double PIO2_HI = Double.longBitsToDouble(0x3FF921FB54400000L); // 1.57079632673412561417e+00 first 33 bits of pi/2
private static final double PIO2_LO = Double.longBitsToDouble(0x3DD0B4611A626331L); // 6.07710050650619224932e-11 pi/2 - PIO2_HI
private static final double TWOPI_HI = 4*PIO2_HI;
@@ -232,11 +227,6 @@ public class SloppyMath {
private static final double ASIN_QS3 = Double.longBitsToDouble(0xbfe6066c1b8d0159L); // -6.88283971605453293030e-01
private static final double ASIN_QS4 = Double.longBitsToDouble(0x3fb3b8c5b12e9282L); // 7.70381505559019352791e-02
- private static final int RADIUS_TABS_SIZE = (1<<10) + 1;
- private static final double RADIUS_DELTA = (StrictMath.PI/2d) / (RADIUS_TABS_SIZE - 1);
- private static final double RADIUS_INDEXER = 1d/RADIUS_DELTA;
- private static final double[] earthDiameterPerLatitude = new double[RADIUS_TABS_SIZE];
-
/** Initializes look-up tables. */
static {
// sin and cos
@@ -279,27 +269,5 @@ public class SloppyMath {
asinDer3DivF3Tab[i] = ((1+2*x*x)*oneMinusXSqInv2_5) * ONE_DIV_F3;
asinDer4DivF4Tab[i] = ((5+2*x*(2+x*(5-2*x)))*oneMinusXSqInv3_5) * ONE_DIV_F4;
}
-
-
- // WGS84 earth-ellipsoid major (a) and minor (b) radius
- final double a = 6_378_137; // [m]
- final double b = 6_356_752.31420; // [m]
-
- final double a2 = a*a;
- final double b2 = b*b;
-
- earthDiameterPerLatitude[0] = 2 * a / 1000d;
- earthDiameterPerLatitude[RADIUS_TABS_SIZE-1] = 2 * b / 1000d;
- // earth radius
- for (int i=1;i<RADIUS_TABS_SIZE-1;i++) {
- final double lat = Math.PI * i / (2d * RADIUS_TABS_SIZE-1);
- double one = StrictMath.pow(a2 * StrictMath.cos(lat), 2);
- double two = StrictMath.pow(b2 * StrictMath.sin(lat), 2);
- double three = StrictMath.pow(a * StrictMath.cos(lat), 2);
- double four = StrictMath.pow(b * StrictMath.sin(lat), 2);
-
- double radius = StrictMath.sqrt((one+two)/(three+four));
- earthDiameterPerLatitude[i] = 2 * radius / 1000d;
- }
}
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c49e761c/lucene/core/src/test/org/apache/lucene/util/TestSloppyMath.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/test/org/apache/lucene/util/TestSloppyMath.java b/lucene/core/src/test/org/apache/lucene/util/TestSloppyMath.java
index 7df2f78..2ccf619 100644
--- a/lucene/core/src/test/org/apache/lucene/util/TestSloppyMath.java
+++ b/lucene/core/src/test/org/apache/lucene/util/TestSloppyMath.java
@@ -19,15 +19,19 @@ package org.apache.lucene.util;
import static org.apache.lucene.util.SloppyMath.cos;
import static org.apache.lucene.util.SloppyMath.asin;
-import static org.apache.lucene.util.SloppyMath.haversin;
+import static org.apache.lucene.util.SloppyMath.haversinMeters;
+import static org.apache.lucene.util.SloppyMath.haversinSortKey;
import java.util.Random;
+
public class TestSloppyMath extends LuceneTestCase {
// accuracy for cos()
static double COS_DELTA = 1E-15;
// accuracy for asin()
static double ASIN_DELTA = 1E-7;
+ // accuracy for haversinMeters()
+ static double HAVERSIN_DELTA = 1E-5;
public void testCos() {
assertTrue(Double.isNaN(cos(Double.NaN)));
@@ -81,24 +85,24 @@ public class TestSloppyMath extends LuceneTestCase {
}
public void testHaversin() {
- assertTrue(Double.isNaN(haversin(1, 1, 1, Double.NaN)));
- assertTrue(Double.isNaN(haversin(1, 1, Double.NaN, 1)));
- assertTrue(Double.isNaN(haversin(1, Double.NaN, 1, 1)));
- assertTrue(Double.isNaN(haversin(Double.NaN, 1, 1, 1)));
+ assertTrue(Double.isNaN(haversinMeters(1, 1, 1, Double.NaN)));
+ assertTrue(Double.isNaN(haversinMeters(1, 1, Double.NaN, 1)));
+ assertTrue(Double.isNaN(haversinMeters(1, Double.NaN, 1, 1)));
+ assertTrue(Double.isNaN(haversinMeters(Double.NaN, 1, 1, 1)));
- assertEquals(0, haversin(0, 0, 0, 0), 0D);
- assertEquals(0, haversin(0, -180, 0, -180), 0D);
- assertEquals(0, haversin(0, -180, 0, 180), 0D);
- assertEquals(0, haversin(0, 180, 0, 180), 0D);
- assertEquals(0, haversin(90, 0, 90, 0), 0D);
- assertEquals(0, haversin(90, -180, 90, -180), 0D);
- assertEquals(0, haversin(90, -180, 90, 180), 0D);
- assertEquals(0, haversin(90, 180, 90, 180), 0D);
+ assertEquals(0, haversinMeters(0, 0, 0, 0), 0D);
+ assertEquals(0, haversinMeters(0, -180, 0, -180), 0D);
+ assertEquals(0, haversinMeters(0, -180, 0, 180), 0D);
+ assertEquals(0, haversinMeters(0, 180, 0, 180), 0D);
+ assertEquals(0, haversinMeters(90, 0, 90, 0), 0D);
+ assertEquals(0, haversinMeters(90, -180, 90, -180), 0D);
+ assertEquals(0, haversinMeters(90, -180, 90, 180), 0D);
+ assertEquals(0, haversinMeters(90, 180, 90, 180), 0D);
- // Test half a circle on the equator, using WGS84 earth radius
- double earthRadiusKMs = 6378.137;
- double halfCircle = earthRadiusKMs * Math.PI;
- assertEquals(halfCircle, haversin(0, 0, 0, 180), 0D);
+ // Test half a circle on the equator, using WGS84 equatorial earth radius
+ double earthRadiusMs = 6_378_137D;
+ double halfCircle = earthRadiusMs * Math.PI;
+ assertEquals(halfCircle, haversinMeters(0, 0, 0, 180), 0D);
Random r = random();
double randomLat1 = 40.7143528 + (r.nextInt(10) - 5) * 360;
@@ -107,16 +111,59 @@ public class TestSloppyMath extends LuceneTestCase {
double randomLat2 = 40.65 + (r.nextInt(10) - 5) * 360;
double randomLon2 = -73.95 + (r.nextInt(10) - 5) * 360;
- assertEquals(8.572, haversin(randomLat1, randomLon1, randomLat2, randomLon2), 0.01D);
+ assertEquals(8_581.7047, haversinMeters(randomLat1, randomLon1, randomLat2, randomLon2), 0.01D);
// from solr and ES tests (with their respective epsilons)
- assertEquals(0, haversin(40.7143528, -74.0059731, 40.7143528, -74.0059731), 0D);
- assertEquals(5.286, haversin(40.7143528, -74.0059731, 40.759011, -73.9844722), 0.01D);
- assertEquals(0.4621, haversin(40.7143528, -74.0059731, 40.718266, -74.007819), 0.01D);
- assertEquals(1.055, haversin(40.7143528, -74.0059731, 40.7051157, -74.0088305), 0.01D);
- assertEquals(1.258, haversin(40.7143528, -74.0059731, 40.7247222, -74), 0.01D);
- assertEquals(2.029, haversin(40.7143528, -74.0059731, 40.731033, -73.9962255), 0.01D);
- assertEquals(8.572, haversin(40.7143528, -74.0059731, 40.65, -73.95), 0.01D);
+ assertEquals(0, haversinMeters(40.7143528, -74.0059731, 40.7143528, -74.0059731), 0D);
+ assertEquals(5_291.80, haversinMeters(40.7143528, -74.0059731, 40.759011, -73.9844722), 0.01D);
+ assertEquals(462.62, haversinMeters(40.7143528, -74.0059731, 40.718266, -74.007819), 0.01D);
+ assertEquals(1_056.16, haversinMeters(40.7143528, -74.0059731, 40.7051157, -74.0088305), 0.01D);
+ assertEquals(1_259.53, haversinMeters(40.7143528, -74.0059731, 40.7247222, -74), 0.01D);
+ assertEquals(2_030.79, haversinMeters(40.7143528, -74.0059731, 40.731033, -73.9962255), 0.01D);
+ assertEquals(8_581.70, haversinMeters(40.7143528, -74.0059731, 40.65, -73.95), 0.01D);
+ }
+
+ /** Test this method sorts the same way as real haversin */
+ public void testHaversinSortKey() {
+ for (int i = 0; i < 100000; i++) {
+ double centerLat = -90 + 180.0 * random().nextDouble();
+ double centerLon = -180 + 360.0 * random().nextDouble();
+
+ double lat1 = -90 + 180.0 * random().nextDouble();
+ double lon1 = -180 + 360.0 * random().nextDouble();
+
+ double lat2 = -90 + 180.0 * random().nextDouble();
+ double lon2 = -180 + 360.0 * random().nextDouble();
+
+ int expected = Integer.signum(Double.compare(haversinMeters(centerLat, centerLon, lat1, lon1),
+ haversinMeters(centerLat, centerLon, lat2, lon2)));
+ int actual = Integer.signum(Double.compare(haversinSortKey(centerLat, centerLon, lat1, lon1),
+ haversinSortKey(centerLat, centerLon, lat2, lon2)));
+ assertEquals(expected, actual);
+ assertEquals(haversinMeters(centerLat, centerLon, lat1, lon1), haversinMeters(haversinSortKey(centerLat, centerLon, lat1, lon1)), 0.0D);
+ assertEquals(haversinMeters(centerLat, centerLon, lat2, lon2), haversinMeters(haversinSortKey(centerLat, centerLon, lat2, lon2)), 0.0D);
+ }
+ }
+
+ public void testAgainstSlowVersion() {
+ for (int i = 0; i < 100_000; i++) {
+ double lat1 = -90 + 180.0 * random().nextDouble();
+ double lon1 = -180 + 360.0 * random().nextDouble();
+ double lat2 = -90 + 180.0 * random().nextDouble();
+ double lon2 = -180 + 360.0 * random().nextDouble();
+
+ double expected = haversinMeters(lat1, lon1, lat2, lon2);
+ double actual = slowHaversin(lat1, lon1, lat2, lon2);
+ assertEquals(expected, actual, HAVERSIN_DELTA);
+ }
+ }
+
+ // simple incorporation of the wikipedia formula
+ private static double slowHaversin(double lat1, double lon1, double lat2, double lon2) {
+ double h1 = (1 - StrictMath.cos(StrictMath.toRadians(lat2) - StrictMath.toRadians(lat1))) / 2;
+ double h2 = (1 - StrictMath.cos(StrictMath.toRadians(lon2) - StrictMath.toRadians(lon1))) / 2;
+ double h = h1 + StrictMath.cos(StrictMath.toRadians(lat1)) * StrictMath.cos(StrictMath.toRadians(lat2)) * h2;
+ return 2 * 6378137 * StrictMath.asin(Math.min(1, Math.sqrt(h)));
}
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c49e761c/lucene/demo/src/java/org/apache/lucene/demo/facet/DistanceFacetsExample.java
----------------------------------------------------------------------
diff --git a/lucene/demo/src/java/org/apache/lucene/demo/facet/DistanceFacetsExample.java b/lucene/demo/src/java/org/apache/lucene/demo/facet/DistanceFacetsExample.java
index fff3bff..8328f97 100644
--- a/lucene/demo/src/java/org/apache/lucene/demo/facet/DistanceFacetsExample.java
+++ b/lucene/demo/src/java/org/apache/lucene/demo/facet/DistanceFacetsExample.java
@@ -46,7 +46,6 @@ import org.apache.lucene.search.SortField;
import org.apache.lucene.search.TopDocs;
import org.apache.lucene.store.Directory;
import org.apache.lucene.store.RAMDirectory;
-import org.apache.lucene.util.SloppyMath;
import java.io.Closeable;
import java.io.IOException;
@@ -151,7 +150,7 @@ public class DistanceFacetsExample implements Closeable {
double originLatRadians = Math.toRadians(originLat);
double originLngRadians = Math.toRadians(originLng);
- double angle = maxDistanceKM / (SloppyMath.earthDiameter(originLat) / 2.0);
+ double angle = maxDistanceKM / EARTH_RADIUS_KM;
double minLat = originLatRadians - angle;
double maxLat = originLatRadians + angle;
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c49e761c/lucene/expressions/src/resources/org/apache/lucene/expressions/js/JavascriptCompiler.properties
----------------------------------------------------------------------
diff --git a/lucene/expressions/src/resources/org/apache/lucene/expressions/js/JavascriptCompiler.properties b/lucene/expressions/src/resources/org/apache/lucene/expressions/js/JavascriptCompiler.properties
index 8cecb33..3fc2bc4 100644
--- a/lucene/expressions/src/resources/org/apache/lucene/expressions/js/JavascriptCompiler.properties
+++ b/lucene/expressions/src/resources/org/apache/lucene/expressions/js/JavascriptCompiler.properties
@@ -31,7 +31,7 @@ cos = java.lang.Math, cos, 1
cosh = java.lang.Math, cosh, 1
exp = java.lang.Math, exp, 1
floor = java.lang.Math, floor, 1
-haversin = org.apache.lucene.util.SloppyMath, haversin, 4
+haversin = org.apache.lucene.util.SloppyMath, haversinKilometers, 4
ln = java.lang.Math, log, 1
log10 = java.lang.Math, log10, 1
logn = org.apache.lucene.util.MathUtil, log, 2
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c49e761c/lucene/expressions/src/test/org/apache/lucene/expressions/TestDemoExpressions.java
----------------------------------------------------------------------
diff --git a/lucene/expressions/src/test/org/apache/lucene/expressions/TestDemoExpressions.java b/lucene/expressions/src/test/org/apache/lucene/expressions/TestDemoExpressions.java
index 4699b85..6b35942 100644
--- a/lucene/expressions/src/test/org/apache/lucene/expressions/TestDemoExpressions.java
+++ b/lucene/expressions/src/test/org/apache/lucene/expressions/TestDemoExpressions.java
@@ -224,13 +224,13 @@ public class TestDemoExpressions extends LuceneTestCase {
TopFieldDocs td = searcher.search(new MatchAllDocsQuery(), 3, sort);
FieldDoc d = (FieldDoc) td.scoreDocs[0];
- assertEquals(0.4619D, (Double)d.fields[0], 1E-4);
+ assertEquals(0.4626D, (Double)d.fields[0], 1E-4);
d = (FieldDoc) td.scoreDocs[1];
- assertEquals(1.0546D, (Double)d.fields[0], 1E-4);
+ assertEquals(1.0562D, (Double)d.fields[0], 1E-4);
d = (FieldDoc) td.scoreDocs[2];
- assertEquals(5.2842D, (Double)d.fields[0], 1E-4);
+ assertEquals(5.2918D, (Double)d.fields[0], 1E-4);
}
public void testStaticExtendedVariableExample() throws Exception {
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c49e761c/lucene/expressions/src/test/org/apache/lucene/expressions/js/TestJavascriptFunction.java
----------------------------------------------------------------------
diff --git a/lucene/expressions/src/test/org/apache/lucene/expressions/js/TestJavascriptFunction.java b/lucene/expressions/src/test/org/apache/lucene/expressions/js/TestJavascriptFunction.java
index 207b993..ce38acd 100644
--- a/lucene/expressions/src/test/org/apache/lucene/expressions/js/TestJavascriptFunction.java
+++ b/lucene/expressions/src/test/org/apache/lucene/expressions/js/TestJavascriptFunction.java
@@ -158,7 +158,7 @@ public class TestJavascriptFunction extends LuceneTestCase {
}
public void testHaversinMethod() throws Exception {
- assertEvaluatesTo("haversin(40.7143528,-74.0059731,40.759011,-73.9844722)", 5.284299568309);
+ assertEvaluatesTo("haversin(40.7143528,-74.0059731,40.759011,-73.9844722)", 5.291799723323441);
}
public void testLnMethod() throws Exception {
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c49e761c/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java
index 9374b17..e24401a 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java
@@ -30,10 +30,10 @@ import org.apache.lucene.search.IndexSearcher;
import org.apache.lucene.search.Query;
import org.apache.lucene.search.Scorer;
import org.apache.lucene.search.Weight;
-import org.apache.lucene.spatial.util.GeoDistanceUtils;
import org.apache.lucene.spatial.util.GeoRect;
import org.apache.lucene.spatial.util.GeoUtils;
import org.apache.lucene.util.DocIdSetBuilder;
+import org.apache.lucene.util.SloppyMath;
/**
* Distance query for {@link LatLonPoint}.
@@ -108,7 +108,7 @@ final class LatLonPointDistanceQuery extends Query {
assert packedValue.length == 8;
double lat = LatLonPoint.decodeLatitude(packedValue, 0);
double lon = LatLonPoint.decodeLongitude(packedValue, Integer.BYTES);
- if (GeoDistanceUtils.haversin(latitude, longitude, lat, lon) <= radiusMeters) {
+ if (SloppyMath.haversinMeters(latitude, longitude, lat, lon) <= radiusMeters) {
visit(docID);
}
}
@@ -129,10 +129,10 @@ final class LatLonPointDistanceQuery extends Query {
// we are fully outside of bounding box(es), don't proceed any further.
return Relation.CELL_OUTSIDE_QUERY;
} else if (lonMax - longitude < 90 && longitude - lonMin < 90 &&
- GeoDistanceUtils.haversin(latitude, longitude, latMin, lonMin) <= radiusMeters &&
- GeoDistanceUtils.haversin(latitude, longitude, latMin, lonMax) <= radiusMeters &&
- GeoDistanceUtils.haversin(latitude, longitude, latMax, lonMin) <= radiusMeters &&
- GeoDistanceUtils.haversin(latitude, longitude, latMax, lonMax) <= radiusMeters) {
+ SloppyMath.haversinMeters(latitude, longitude, latMin, lonMin) <= radiusMeters &&
+ SloppyMath.haversinMeters(latitude, longitude, latMin, lonMax) <= radiusMeters &&
+ SloppyMath.haversinMeters(latitude, longitude, latMax, lonMin) <= radiusMeters &&
+ SloppyMath.haversinMeters(latitude, longitude, latMax, lonMax) <= radiusMeters) {
// we are fully enclosed, collect everything within this subtree
return Relation.CELL_INSIDE_QUERY;
} else {
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c49e761c/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceQuery.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceQuery.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceQuery.java
index fa95710..d14e351 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceQuery.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceQuery.java
@@ -34,9 +34,11 @@ import org.apache.lucene.search.IndexSearcher;
import org.apache.lucene.search.ScoreDoc;
import org.apache.lucene.search.Sort;
import org.apache.lucene.search.TopDocs;
-import org.apache.lucene.spatial.util.GeoDistanceUtils;
+import org.apache.lucene.spatial.util.GeoRect;
+import org.apache.lucene.spatial.util.GeoUtils;
import org.apache.lucene.store.Directory;
import org.apache.lucene.util.LuceneTestCase;
+import org.apache.lucene.util.SloppyMath;
import org.apache.lucene.util.TestUtil;
import org.apache.lucene.util.bkd.BKDWriter;
@@ -159,7 +161,7 @@ public class TestLatLonPointDistanceQuery extends LuceneTestCase {
for (int doc = 0; doc < reader.maxDoc(); doc++) {
double docLatitude = reader.document(doc).getField("lat").numericValue().doubleValue();
double docLongitude = reader.document(doc).getField("lon").numericValue().doubleValue();
- double distance = GeoDistanceUtils.haversin(lat, lon, docLatitude, docLongitude);
+ double distance = SloppyMath.haversinMeters(lat, lon, docLatitude, docLongitude);
if (distance <= radius) {
expected.set(doc);
}
@@ -177,7 +179,7 @@ public class TestLatLonPointDistanceQuery extends LuceneTestCase {
for (int doc = 0; doc < reader.maxDoc(); doc++) {
double docLatitude = reader.document(doc).getField("lat").numericValue().doubleValue();
double docLongitude = reader.document(doc).getField("lon").numericValue().doubleValue();
- double distance = GeoDistanceUtils.haversin(lat, lon, docLatitude, docLongitude);
+ double distance = SloppyMath.haversinMeters(lat, lon, docLatitude, docLongitude);
System.out.println("" + doc + ": (" + docLatitude + "," + docLongitude + "), distance=" + distance);
}
throw e;
@@ -187,4 +189,55 @@ public class TestLatLonPointDistanceQuery extends LuceneTestCase {
writer.close();
dir.close();
}
+
+ public void testBoundingBoxOpto() {
+ for (int i = 0; i < 1000; i++) {
+ double lat = -90 + 180.0 * random().nextDouble();
+ double lon = -180 + 360.0 * random().nextDouble();
+ double radius = 50000000 * random().nextDouble();
+ GeoRect box = GeoUtils.circleToBBox(lon, lat, radius);
+ final GeoRect box1;
+ final GeoRect box2;
+ if (box.crossesDateline()) {
+ box1 = new GeoRect(-180, box.maxLon, box.minLat, box.maxLat);
+ box2 = new GeoRect(box.minLon, 180, box.minLat, box.maxLat);
+ } else {
+ box1 = box;
+ box2 = null;
+ }
+
+ for (int j = 0; j < 10000; j++) {
+ double lat2 = -90 + 180.0 * random().nextDouble();
+ double lon2 = -180 + 360.0 * random().nextDouble();
+ // if the point is within radius, then it should be in our bounding box
+ if (SloppyMath.haversinMeters(lat, lon, lat2, lon2) <= radius) {
+ assertTrue(lat >= box.minLat && lat <= box.maxLat);
+ assertTrue(lon >= box1.minLon && lon <= box1.maxLon || (box2 != null && lon >= box2.minLon && lon <= box2.maxLon));
+ }
+ }
+ }
+ }
+
+ public void testHaversinOpto() {
+ for (int i = 0; i < 1000; i++) {
+ double lat = -90 + 180.0 * random().nextDouble();
+ double lon = -180 + 360.0 * random().nextDouble();
+ double radius = 50000000 * random().nextDouble();
+ GeoRect box = GeoUtils.circleToBBox(lon, lat, radius);
+
+ if (box.maxLon - lon < 90 && lon - box.minLon < 90) {
+ double minPartialDistance = Math.max(SloppyMath.haversinSortKey(lat, lon, lat, box.maxLon),
+ SloppyMath.haversinSortKey(lat, lon, box.maxLat, lon));
+
+ for (int j = 0; j < 10000; j++) {
+ double lat2 = -90 + 180.0 * random().nextDouble();
+ double lon2 = -180 + 360.0 * random().nextDouble();
+ // if the point is within radius, then it should be <= our sort key
+ if (SloppyMath.haversinMeters(lat, lon, lat2, lon2) <= radius) {
+ assertTrue(SloppyMath.haversinSortKey(lat, lon, lat2, lon2) <= minPartialDistance);
+ }
+ }
+ }
+ }
+ }
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c49e761c/lucene/sandbox/src/test/org/apache/lucene/search/TestLatLonPointQueries.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/search/TestLatLonPointQueries.java b/lucene/sandbox/src/test/org/apache/lucene/search/TestLatLonPointQueries.java
index 028d6b8..90502f9 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/search/TestLatLonPointQueries.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/search/TestLatLonPointQueries.java
@@ -19,9 +19,9 @@ package org.apache.lucene.search;
import org.apache.lucene.document.Document;
import org.apache.lucene.document.LatLonPoint;
import org.apache.lucene.spatial.util.BaseGeoPointTestCase;
-import org.apache.lucene.spatial.util.GeoDistanceUtils;
import org.apache.lucene.spatial.util.GeoRect;
import org.apache.lucene.spatial.util.GeoUtils;
+import org.apache.lucene.util.SloppyMath;
public class TestLatLonPointQueries extends BaseGeoPointTestCase {
// TODO: remove this!
@@ -136,7 +136,7 @@ public class TestLatLonPointQueries extends BaseGeoPointTestCase {
@Override
protected Boolean circleContainsPoint(double centerLat, double centerLon, double radiusMeters, double pointLat, double pointLon) {
- double distanceMeters = GeoDistanceUtils.haversin(centerLat, centerLon, pointLat, pointLon);
+ double distanceMeters = SloppyMath.haversinMeters(centerLat, centerLon, pointLat, pointLon);
boolean result = distanceMeters <= radiusMeters;
//System.out.println(" shouldMatch? centerLon=" + centerLon + " centerLat=" + centerLat + " pointLon=" + pointLon + " pointLat=" + pointLat + " result=" + result + " distanceMeters=" + (distanceKM * 1000));
return result;
@@ -144,7 +144,7 @@ public class TestLatLonPointQueries extends BaseGeoPointTestCase {
@Override
protected Boolean distanceRangeContainsPoint(double centerLat, double centerLon, double minRadiusMeters, double radiusMeters, double pointLat, double pointLon) {
- final double d = GeoDistanceUtils.haversin(centerLat, centerLon, pointLat, pointLon);
+ final double d = SloppyMath.haversinMeters(centerLat, centerLon, pointLat, pointLon);
return d >= minRadiusMeters && d <= radiusMeters;
}
@@ -199,7 +199,7 @@ public class TestLatLonPointQueries extends BaseGeoPointTestCase {
}
}
- double distanceMeters = GeoDistanceUtils.haversin(centerLat, centerLon, lat, lon);
+ double distanceMeters = SloppyMath.haversinMeters(centerLat, centerLon, lat, lon);
// Haversin says it's within the circle:
boolean haversinSays = distanceMeters <= radiusMeters;
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c49e761c/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQuery.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQuery.java b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQuery.java
index 396d88e..a513b3d 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQuery.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQuery.java
@@ -31,7 +31,7 @@ import org.apache.lucene.spatial.util.GeoUtils;
* the morton codes of the min and max lat/lon pairs that intersect the boundary of the point-radius
* circle. Terms
* passing this initial filter are then passed to a secondary {@code postFilter} method that verifies whether the
- * decoded lat/lon point fall within the specified query distance (see {@link org.apache.lucene.util.SloppyMath#haversin}.
+ * decoded lat/lon point fall within the specified query distance (see {@link org.apache.lucene.util.SloppyMath#haversinMeters(double, double, double, double)}.
* All morton value comparisons are subject to the same precision tolerance defined in
* {@value org.apache.lucene.spatial.util.GeoEncodingUtils#TOLERANCE} and distance comparisons are subject to the accuracy of the
* haversine formula (from R.W. Sinnott, "Virtues of the Haversine", Sky and Telescope, vol. 68, no. 2, 1984, p. 159)
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c49e761c/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQueryImpl.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQueryImpl.java b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQueryImpl.java
index f091bcb..6a54e23 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQueryImpl.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQueryImpl.java
@@ -73,11 +73,11 @@ final class GeoPointDistanceQueryImpl extends GeoPointInBBoxQueryImpl {
* The two-phase query approach. The parent {@link GeoPointTermsEnum} class matches
* encoded terms that fall within the minimum bounding box of the point-radius circle. Those documents that pass
* the initial bounding box filter are then post filter compared to the provided distance using the
- * {@link org.apache.lucene.util.SloppyMath#haversin} method.
+ * {@link org.apache.lucene.util.SloppyMath#haversinMeters(double, double, double, double)} method.
*/
@Override
protected boolean postFilter(final double lon, final double lat) {
- return (SloppyMath.haversin(distanceQuery.centerLat, centerLon, lat, lon) * 1000.0 <= distanceQuery.radiusMeters);
+ return SloppyMath.haversinMeters(distanceQuery.centerLat, centerLon, lat, lon) <= distanceQuery.radiusMeters;
}
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c49e761c/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInBBoxQueryImpl.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInBBoxQueryImpl.java b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInBBoxQueryImpl.java
index 675b2a1..107b136 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInBBoxQueryImpl.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInBBoxQueryImpl.java
@@ -53,7 +53,7 @@ class GeoPointInBBoxQueryImpl extends GeoPointMultiTermQuery {
double midLon = (minLon + maxLon) * 0.5;
double midLat = (minLat + maxLat) * 0.5;
- if (SloppyMath.haversin(minLat, minLon, midLat, midLon)*1000 > 1000000) {
+ if (SloppyMath.haversinMeters(minLat, minLon, midLat, midLon) > 1000000) {
shiftFactor = 5;
} else {
shiftFactor = 4;
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c49e761c/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointMultiTermQuery.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointMultiTermQuery.java b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointMultiTermQuery.java
index b83d680..edbd53d 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointMultiTermQuery.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointMultiTermQuery.java
@@ -105,7 +105,7 @@ abstract class GeoPointMultiTermQuery extends MultiTermQuery {
double midLon = (minLon + maxLon) * 0.5;
double midLat = (minLat + maxLat) * 0.5;
- if (SloppyMath.haversin(minLat, minLon, midLat, midLon)*1000 > 1000000) {
+ if (SloppyMath.haversinMeters(minLat, minLon, midLat, midLon) > 1000000) {
shiftFactor = 5;
} else {
shiftFactor = 4;
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c49e761c/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoDistanceUtils.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoDistanceUtils.java b/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoDistanceUtils.java
index e845c9e..482ed0f 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoDistanceUtils.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoDistanceUtils.java
@@ -34,28 +34,6 @@ public class GeoDistanceUtils {
}
/**
- * Compute the great-circle distance using original haversine implementation published by Sinnot in:
- * R.W. Sinnott, "Virtues of the Haversine", Sky and Telescope, vol. 68, no. 2, 1984, p. 159
- *
- * NOTE: this differs from {@link org.apache.lucene.util.SloppyMath#haversin} in that it uses the semi-major axis
- * of the earth instead of an approximation based on the average latitude of the two points (which can introduce an
- * additional error up to .337%, or ~67.6 km at the equator)
- */
- public static double haversin(double lat1, double lon1, double lat2, double lon2) {
- double dLat = TO_RADIANS * (lat2 - lat1);
- double dLon = TO_RADIANS * (lon2 - lon1);
- lat1 = TO_RADIANS * (lat1);
- lat2 = TO_RADIANS * (lat2);
-
- final double sinDLatO2 = SloppyMath.sin(dLat / 2);
- final double sinDLonO2 = SloppyMath.sin(dLon / 2);
-
- double a = sinDLatO2*sinDLatO2 + sinDLonO2 * sinDLonO2 * SloppyMath.cos(lat1) * SloppyMath.cos(lat2);
- double c = 2 * SloppyMath.asin(Math.sqrt(a));
- return (GeoProjectionUtils.SEMIMAJOR_AXIS * c);
- }
-
- /**
* Compute the distance between two geo-points using vincenty distance formula
* Vincenty uses the oblate spheroid whereas haversine uses unit sphere, this will give roughly
* 22m better accuracy (in worst case) than haversine
@@ -138,12 +116,11 @@ public class GeoDistanceUtils {
* @return Sloppy distance in degrees longitude for provided distance in meters
*/
public static double distanceToDegreesLon(double lat, double distance) {
- distance /= 1000.0;
// convert latitude to radians
lat = StrictMath.toRadians(lat);
// get the diameter at the latitude
- final double diameter = SloppyMath.earthDiameter(StrictMath.toRadians(lat));
+ final double diameter = 2 * GeoProjectionUtils.SEMIMAJOR_AXIS;
// compute inverse haversine
double a = StrictMath.sin(distance/diameter);
@@ -197,9 +174,9 @@ public class GeoDistanceUtils {
/** Returns the maximum distance/radius (in meters) from the point 'center' before overlapping */
public static double maxRadialDistanceMeters(final double centerLon, final double centerLat) {
if (Math.abs(centerLat) == GeoUtils.MAX_LAT_INCL) {
- return GeoDistanceUtils.haversin(centerLat, centerLon, 0, centerLon);
+ return SloppyMath.haversinMeters(centerLat, centerLon, 0, centerLon);
}
- return GeoDistanceUtils.haversin(centerLat, centerLon, centerLat, (GeoUtils.MAX_LON_INCL + centerLon) % 360);
+ return SloppyMath.haversinMeters(centerLat, centerLon, centerLat, (GeoUtils.MAX_LON_INCL + centerLon) % 360);
}
/**
@@ -210,8 +187,7 @@ public class GeoDistanceUtils {
*/
public static double distanceToDegreesLat(double lat, double distance) {
// get the diameter at the latitude
- final double diameter = SloppyMath.earthDiameter(StrictMath.toRadians(lat));
- distance /= 1000.0;
+ final double diameter = 2 * GeoProjectionUtils.SEMIMAJOR_AXIS;
// compute inverse haversine
double a = StrictMath.sin(distance/diameter);
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c49e761c/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoProjectionUtils.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoProjectionUtils.java b/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoProjectionUtils.java
index 5a81adc..12d1350 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoProjectionUtils.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoProjectionUtils.java
@@ -20,9 +20,6 @@ import static java.lang.StrictMath.sqrt;
import static org.apache.lucene.util.SloppyMath.asin;
import static org.apache.lucene.util.SloppyMath.cos;
-import static org.apache.lucene.util.SloppyMath.sin;
-import static org.apache.lucene.util.SloppyMath.tan;
-import static org.apache.lucene.util.SloppyMath.PIO2;
import static org.apache.lucene.util.SloppyMath.TO_DEGREES;
import static org.apache.lucene.util.SloppyMath.TO_RADIANS;
@@ -30,8 +27,11 @@ import static org.apache.lucene.spatial.util.GeoUtils.MAX_LAT_INCL;
import static org.apache.lucene.spatial.util.GeoUtils.MAX_LON_INCL;
import static org.apache.lucene.spatial.util.GeoUtils.MIN_LAT_INCL;
import static org.apache.lucene.spatial.util.GeoUtils.MIN_LON_INCL;
+import static org.apache.lucene.spatial.util.GeoUtils.PIO2;
import static org.apache.lucene.spatial.util.GeoUtils.normalizeLat;
import static org.apache.lucene.spatial.util.GeoUtils.normalizeLon;
+import static org.apache.lucene.spatial.util.GeoUtils.sloppySin;
+import static org.apache.lucene.spatial.util.GeoUtils.sloppyTan;
/**
* Reusable geo-spatial projection utility methods.
@@ -149,7 +149,7 @@ public class GeoProjectionUtils {
lon = TO_RADIANS * lon;
lat = TO_RADIANS * lat;
- final double sl = sin(lat);
+ final double sl = sloppySin(lat);
final double s2 = sl*sl;
final double cl = cos(lat);
@@ -170,7 +170,7 @@ public class GeoProjectionUtils {
final double rn = SEMIMAJOR_AXIS / StrictMath.sqrt(1.0D - E2 * s2);
ecf[0] = (rn+alt) * cl * cos(lon);
- ecf[1] = (rn+alt) * cl * sin(lon);
+ ecf[1] = (rn+alt) * cl * sloppySin(lon);
ecf[2] = ((rn*(1.0-E2))+alt)*sl;
return ecf;
@@ -304,9 +304,9 @@ public class GeoProjectionUtils {
originLon = TO_RADIANS * originLon;
originLat = TO_RADIANS * originLat;
- final double sLon = sin(originLon);
+ final double sLon = sloppySin(originLon);
final double cLon = cos(originLon);
- final double sLat = sin(originLat);
+ final double sLat = sloppySin(originLat);
final double cLat = cos(originLat);
phiMatrix[0][0] = -sLon;
@@ -338,9 +338,9 @@ public class GeoProjectionUtils {
originLon = TO_RADIANS * originLon;
originLat = TO_RADIANS * originLat;
- final double sLat = sin(originLat);
+ final double sLat = sloppySin(originLat);
final double cLat = cos(originLat);
- final double sLon = sin(originLon);
+ final double sLon = sloppySin(originLon);
final double cLon = cos(originLon);
phiMatrix[0][0] = -sLon;
@@ -374,8 +374,8 @@ public class GeoProjectionUtils {
final double alpha1 = TO_RADIANS * bearing;
final double cosA1 = cos(alpha1);
- final double sinA1 = sin(alpha1);
- final double tanU1 = (1-FLATTENING) * tan(TO_RADIANS * lat);
+ final double sinA1 = sloppySin(alpha1);
+ final double tanU1 = (1-FLATTENING) * sloppyTan(TO_RADIANS * lat);
final double cosU1 = 1 / StrictMath.sqrt((1+tanU1*tanU1));
final double sinU1 = tanU1*cosU1;
final double sig1 = StrictMath.atan2(tanU1, cosA1);
@@ -391,7 +391,7 @@ public class GeoProjectionUtils {
do {
cos2SigmaM = cos(2*sig1 + sigma);
- sinSigma = sin(sigma);
+ sinSigma = sloppySin(sigma);
cosSigma = cos(sigma);
deltaSigma = B * sinSigma * (cos2SigmaM + (B/4D) * (cosSigma*(-1+2*cos2SigmaM*cos2SigmaM)-
@@ -435,12 +435,12 @@ public class GeoProjectionUtils {
bearing *= TO_RADIANS;
final double cLat = cos(lat);
- final double sLat = sin(lat);
- final double sinDoR = sin(dist / GeoProjectionUtils.SEMIMAJOR_AXIS);
+ final double sLat = sloppySin(lat);
+ final double sinDoR = sloppySin(dist / GeoProjectionUtils.SEMIMAJOR_AXIS);
final double cosDoR = cos(dist / GeoProjectionUtils.SEMIMAJOR_AXIS);
pt[1] = asin(sLat*cosDoR + cLat * sinDoR * cos(bearing));
- pt[0] = TO_DEGREES * (lon + Math.atan2(sin(bearing) * sinDoR * cLat, cosDoR - sLat * sin(pt[1])));
+ pt[0] = TO_DEGREES * (lon + Math.atan2(sloppySin(bearing) * sinDoR * cLat, cosDoR - sLat * sloppySin(pt[1])));
pt[1] *= TO_DEGREES;
return pt;
@@ -458,8 +458,8 @@ public class GeoProjectionUtils {
double dLon = (lon2 - lon1) * TO_RADIANS;
lat2 *= TO_RADIANS;
lat1 *= TO_RADIANS;
- double y = sin(dLon) * cos(lat2);
- double x = cos(lat1) * sin(lat2) - sin(lat1) * cos(lat2) * cos(dLon);
+ double y = sloppySin(dLon) * cos(lat2);
+ double x = cos(lat1) * sloppySin(lat2) - sloppySin(lat1) * cos(lat2) * cos(dLon);
return Math.atan2(y, x) * TO_DEGREES;
}
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c49e761c/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoRelationUtils.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoRelationUtils.java b/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoRelationUtils.java
index d9d6991..e40b91a 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoRelationUtils.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoRelationUtils.java
@@ -289,10 +289,10 @@ public class GeoRelationUtils {
}
double w = Math.abs(rMaxX - rMinX);
if (w <= 90.0) {
- return GeoDistanceUtils.haversin(centerLat, centerLon, rMinY, rMinX) <= radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMaxY, rMinX) <= radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMaxY, rMaxX) <= radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMinY, rMaxX) <= radiusMeters;
+ return SloppyMath.haversinMeters(centerLat, centerLon, rMinY, rMinX) <= radiusMeters
+ || SloppyMath.haversinMeters(centerLat, centerLon, rMaxY, rMinX) <= radiusMeters
+ || SloppyMath.haversinMeters(centerLat, centerLon, rMaxY, rMaxX) <= radiusMeters
+ || SloppyMath.haversinMeters(centerLat, centerLon, rMinY, rMaxX) <= radiusMeters;
}
// partition
w /= 4;
@@ -300,24 +300,24 @@ public class GeoRelationUtils {
final double p2 = p1 + w;
final double p3 = p2 + w;
- return GeoDistanceUtils.haversin(centerLat, centerLon, rMinY, rMinX) <= radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMaxY, rMinX) <= radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMaxY, p1) <= radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMinY, p1) <= radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMinY, p2) <= radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMaxY, p2) <= radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMaxY, p3) <= radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMinY, p3) <= radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMaxY, rMaxX) <= radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMinY, rMaxX) <= radiusMeters;
+ return SloppyMath.haversinMeters(centerLat, centerLon, rMinY, rMinX) <= radiusMeters
+ || SloppyMath.haversinMeters(centerLat, centerLon, rMaxY, rMinX) <= radiusMeters
+ || SloppyMath.haversinMeters(centerLat, centerLon, rMaxY, p1) <= radiusMeters
+ || SloppyMath.haversinMeters(centerLat, centerLon, rMinY, p1) <= radiusMeters
+ || SloppyMath.haversinMeters(centerLat, centerLon, rMinY, p2) <= radiusMeters
+ || SloppyMath.haversinMeters(centerLat, centerLon, rMaxY, p2) <= radiusMeters
+ || SloppyMath.haversinMeters(centerLat, centerLon, rMaxY, p3) <= radiusMeters
+ || SloppyMath.haversinMeters(centerLat, centerLon, rMinY, p3) <= radiusMeters
+ || SloppyMath.haversinMeters(centerLat, centerLon, rMaxY, rMaxX) <= radiusMeters
+ || SloppyMath.haversinMeters(centerLat, centerLon, rMinY, rMaxX) <= radiusMeters;
}
private static boolean rectAnyCornersInCircleSloppy(final double rMinX, final double rMinY, final double rMaxX, final double rMaxY,
final double centerLon, final double centerLat, final double radiusMeters) {
- return SloppyMath.haversin(centerLat, centerLon, rMinY, rMinX)*1000.0 <= radiusMeters
- || SloppyMath.haversin(centerLat, centerLon, rMaxY, rMinX)*1000.0 <= radiusMeters
- || SloppyMath.haversin(centerLat, centerLon, rMaxY, rMaxX)*1000.0 <= radiusMeters
- || SloppyMath.haversin(centerLat, centerLon, rMinY, rMaxX)*1000.0 <= radiusMeters;
+ return SloppyMath.haversinMeters(centerLat, centerLon, rMinY, rMinX) <= radiusMeters
+ || SloppyMath.haversinMeters(centerLat, centerLon, rMaxY, rMinX) <= radiusMeters
+ || SloppyMath.haversinMeters(centerLat, centerLon, rMaxY, rMaxX) <= radiusMeters
+ || SloppyMath.haversinMeters(centerLat, centerLon, rMinY, rMaxX) <= radiusMeters;
}
/**
@@ -336,10 +336,10 @@ public class GeoRelationUtils {
}
// if span is less than 70 degrees we can approximate using distance alone
if (Math.abs(rMaxX - rMinX) <= 70.0) {
- return GeoDistanceUtils.haversin(centerLat, centerLon, rMinY, rMinX) > radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMaxY, rMinX) > radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMaxY, rMaxX) > radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMinY, rMaxX) > radiusMeters;
+ return SloppyMath.haversinMeters(centerLat, centerLon, rMinY, rMinX) > radiusMeters
+ || SloppyMath.haversinMeters(centerLat, centerLon, rMaxY, rMinX) > radiusMeters
+ || SloppyMath.haversinMeters(centerLat, centerLon, rMaxY, rMaxX) > radiusMeters
+ || SloppyMath.haversinMeters(centerLat, centerLon, rMinY, rMaxX) > radiusMeters;
}
return rectCrossesOblateCircle(centerLon, centerLat, radiusMeters, rMinX, rMinY, rMaxX, rMaxY);
}
@@ -363,10 +363,10 @@ public class GeoRelationUtils {
final double d1, d2;
// short-circuit if we find a corner outside the circle
- if ( (d1 = GeoDistanceUtils.haversin(centerLat, centerLon, rMinLat, p1)) > radiusMeters
- || (d2 = GeoDistanceUtils.haversin(centerLat, centerLon, rMinLat, maxLon)) > radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMaxLat, p1) > radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMaxLat, maxLon) > radiusMeters) {
+ if ( (d1 = SloppyMath.haversinMeters(centerLat, centerLon, rMinLat, p1)) > radiusMeters
+ || (d2 = SloppyMath.haversinMeters(centerLat, centerLon, rMinLat, maxLon)) > radiusMeters
+ || SloppyMath.haversinMeters(centerLat, centerLon, rMaxLat, p1) > radiusMeters
+ || SloppyMath.haversinMeters(centerLat, centerLon, rMaxLat, maxLon) > radiusMeters) {
return true;
}
@@ -379,7 +379,7 @@ public class GeoRelationUtils {
GeoProjectionUtils.bearingGreatCircle(maxLon, rMinLat, maxLon, rMaxLat), radiusMeters - d2, pt))[1] < rMinLat || pt[1] < rMaxLat
|| (pt = GeoProjectionUtils.pointFromLonLatBearingGreatCircle(maxLon, rMinLat,
GeoProjectionUtils.bearingGreatCircle(maxLon, rMinLat, (midLon = p1 + 0.5*(maxLon - p1)), rMaxLat),
- radiusMeters - GeoDistanceUtils.haversin(centerLat, centerLon, rMinLat, midLon), pt))[1] < rMinLat
+ radiusMeters - SloppyMath.haversinMeters(centerLat, centerLon, rMinLat, midLon), pt))[1] < rMinLat
|| pt[1] < rMaxLat == false ) {
return true;
}
@@ -390,10 +390,10 @@ public class GeoRelationUtils {
private static boolean rectAnyCornersOutsideCircleSloppy(final double rMinX, final double rMinY, final double rMaxX, final double rMaxY,
final double centerLon, final double centerLat, final double radiusMeters) {
- return SloppyMath.haversin(centerLat, centerLon, rMinY, rMinX)*1000.0 > radiusMeters
- || SloppyMath.haversin(centerLat, centerLon, rMaxY, rMinX)*1000.0 > radiusMeters
- || SloppyMath.haversin(centerLat, centerLon, rMaxY, rMaxX)*1000.0 > radiusMeters
- || SloppyMath.haversin(centerLat, centerLon, rMinY, rMaxX)*1000.0 > radiusMeters;
+ return SloppyMath.haversinMeters(centerLat, centerLon, rMinY, rMinX) > radiusMeters
+ || SloppyMath.haversinMeters(centerLat, centerLon, rMaxY, rMinX) > radiusMeters
+ || SloppyMath.haversinMeters(centerLat, centerLon, rMaxY, rMaxX) > radiusMeters
+ || SloppyMath.haversinMeters(centerLat, centerLon, rMinY, rMaxX) > radiusMeters;
}
/**
@@ -446,7 +446,7 @@ public class GeoRelationUtils {
final boolean approx) {
double[] closestPt = {0, 0};
GeoDistanceUtils.closestPointOnBBox(rMinX, rMinY, rMaxX, rMaxY, centerLon, centerLat, closestPt);
- boolean haverShortCut = GeoDistanceUtils.haversin(centerLat, centerLon, closestPt[1], closestPt[0]) <= radiusMeters;
+ boolean haverShortCut = SloppyMath.haversinMeters(centerLat, centerLon, closestPt[1], closestPt[0]) <= radiusMeters;
if (approx == true || haverShortCut == true) {
return haverShortCut;
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c49e761c/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoUtils.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoUtils.java b/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoUtils.java
index 5becef7..6d755ce 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoUtils.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoUtils.java
@@ -18,6 +18,8 @@ package org.apache.lucene.spatial.util;
import java.util.ArrayList;
+import org.apache.lucene.util.SloppyMath;
+
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.PI;
@@ -25,7 +27,6 @@ import static java.lang.Math.abs;
import static org.apache.lucene.util.SloppyMath.asin;
import static org.apache.lucene.util.SloppyMath.cos;
-import static org.apache.lucene.util.SloppyMath.sin;
import static org.apache.lucene.util.SloppyMath.TO_DEGREES;
import static org.apache.lucene.util.SloppyMath.TO_RADIANS;
import static org.apache.lucene.spatial.util.GeoEncodingUtils.TOLERANCE;
@@ -137,7 +138,7 @@ public final class GeoUtils {
double maxLon;
if (minLat > MIN_LAT_RADIANS && maxLat < MAX_LAT_RADIANS) {
- double deltaLon = asin(sin(radDistance) / cos(radLat));
+ double deltaLon = asin(sloppySin(radDistance) / cos(radLat));
minLon = radLon - deltaLon;
if (minLon < MIN_LON_RADIANS) {
minLon += 2d * PI;
@@ -184,4 +185,45 @@ public final class GeoUtils {
return new GeoRect(max(minLon - TOLERANCE, MIN_LON_INCL), min(maxLon + TOLERANCE, MAX_LON_INCL),
max(minLat - TOLERANCE, MIN_LAT_INCL), min(maxLat + TOLERANCE, MAX_LAT_INCL));
}
+
+
+ // some sloppyish stuff, do we really need this to be done in a sloppy way?
+ // unless it is performance sensitive, we should try to remove.
+ static final double PIO2 = Math.PI / 2D;
+ /**
+ * Returns the trigonometric sine of an angle converted as a cos operation.
+ * <p>
+ * Note that this is not quite right... e.g. sin(0) != 0
+ * <p>
+ * Special cases:
+ * <ul>
+ * <li>If the argument is {@code NaN} or an infinity, then the result is {@code NaN}.
+ * </ul>
+ * @param a an angle, in radians.
+ * @return the sine of the argument.
+ * @see Math#sin(double)
+ */
+ // TODO: deprecate/remove this? at least its no longer public.
+ static double sloppySin(double a) {
+ return cos(a - PIO2);
+ }
+
+
+ /**
+ * Returns the trigonometric tangent of an angle converted in terms of a sin/cos operation.
+ * <p>
+ * Note that this is probably not quite right (untested)
+ * <p>
+ * Special cases:
+ * <ul>
+ * <li>If the argument is {@code NaN} or an infinity, then the result is {@code NaN}.
+ * </ul>
+ * @param a an angle, in radians.
+ * @return the tangent of the argument.
+ * @see Math#sin(double) aand Math#cos(double)
+ */
+ // TODO: deprecate/remove this? at least its no longer public.
+ static double sloppyTan(double a) {
+ return sloppySin(a) / cos(a);
+ }
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c49e761c/lucene/spatial/src/test/org/apache/lucene/spatial/geopoint/search/TestGeoPointQuery.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/test/org/apache/lucene/spatial/geopoint/search/TestGeoPointQuery.java b/lucene/spatial/src/test/org/apache/lucene/spatial/geopoint/search/TestGeoPointQuery.java
index 13ce235..2fd64bd 100644
--- a/lucene/spatial/src/test/org/apache/lucene/spatial/geopoint/search/TestGeoPointQuery.java
+++ b/lucene/spatial/src/test/org/apache/lucene/spatial/geopoint/search/TestGeoPointQuery.java
@@ -205,7 +205,7 @@ public class TestGeoPointQuery extends BaseGeoPointTestCase {
if (radiusQueryCanBeWrong(centerLat, centerLon, pointLon, pointLat, radiusMeters)) {
return null;
} else {
- return SloppyMath.haversin(centerLat, centerLon, pointLat, pointLon)*1000.0 <= radiusMeters;
+ return SloppyMath.haversinMeters(centerLat, centerLon, pointLat, pointLon) <= radiusMeters;
}
}
@@ -215,7 +215,7 @@ public class TestGeoPointQuery extends BaseGeoPointTestCase {
|| radiusQueryCanBeWrong(centerLat, centerLon, pointLon, pointLat, radiusMeters)) {
return null;
} else {
- final double d = SloppyMath.haversin(centerLat, centerLon, pointLat, pointLon)*1000.0;
+ final double d = SloppyMath.haversinMeters(centerLat, centerLon, pointLat, pointLon);
return d >= minRadiusMeters && d <= radiusMeters;
}
}
@@ -229,7 +229,7 @@ public class TestGeoPointQuery extends BaseGeoPointTestCase {
ptLon = GeoEncodingUtils.mortonUnhashLon(hashedPt);
ptLat = GeoEncodingUtils.mortonUnhashLat(hashedPt);
- double ptDistance = SloppyMath.haversin(centerLat, centerLon, ptLat, ptLon)*1000.0;
+ double ptDistance = SloppyMath.haversinMeters(centerLat, centerLon, ptLat, ptLon);
double delta = StrictMath.abs(ptDistance - radius);
// if its within the distance error then it can be wrong
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c49e761c/lucene/spatial/src/test/org/apache/lucene/spatial/util/BaseGeoPointTestCase.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/test/org/apache/lucene/spatial/util/BaseGeoPointTestCase.java b/lucene/spatial/src/test/org/apache/lucene/spatial/util/BaseGeoPointTestCase.java
index e7f9913..e14ffbd 100644
--- a/lucene/spatial/src/test/org/apache/lucene/spatial/util/BaseGeoPointTestCase.java
+++ b/lucene/spatial/src/test/org/apache/lucene/spatial/util/BaseGeoPointTestCase.java
@@ -47,6 +47,7 @@ import org.apache.lucene.store.Directory;
import org.apache.lucene.util.FixedBitSet;
import org.apache.lucene.util.IOUtils;
import org.apache.lucene.util.LuceneTestCase;
+import org.apache.lucene.util.SloppyMath;
import org.apache.lucene.util.TestUtil;
import org.junit.BeforeClass;
@@ -724,7 +725,7 @@ public abstract class BaseGeoPointTestCase extends LuceneTestCase {
@Override
protected void describe(int docID, double pointLat, double pointLon) {
- double distanceMeters = GeoDistanceUtils.haversin(centerLat, centerLon, pointLat, pointLon);
+ double distanceMeters = SloppyMath.haversinMeters(centerLat, centerLon, pointLat, pointLon);
System.out.println(" docID=" + docID + " centerLon=" + centerLon + " centerLat=" + centerLat
+ " pointLon=" + pointLon + " pointLat=" + pointLat + " distanceMeters=" + distanceMeters
+ " vs" + ((rangeQuery == true) ? " minRadiusMeters=" + minRadiusMeters : "") + " radiusMeters=" + radiusMeters);
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c49e761c/lucene/spatial/src/test/org/apache/lucene/spatial/util/TestGeoUtils.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/test/org/apache/lucene/spatial/util/TestGeoUtils.java b/lucene/spatial/src/test/org/apache/lucene/spatial/util/TestGeoUtils.java
index d58e480..bc76852 100644
--- a/lucene/spatial/src/test/org/apache/lucene/spatial/util/TestGeoUtils.java
+++ b/lucene/spatial/src/test/org/apache/lucene/spatial/util/TestGeoUtils.java
@@ -26,6 +26,7 @@ import java.util.Set;
import org.apache.lucene.util.BytesRefBuilder;
import org.apache.lucene.util.LuceneTestCase;
+import org.apache.lucene.util.SloppyMath;
import org.junit.BeforeClass;
import com.carrotsearch.randomizedtesting.generators.RandomInts;
@@ -315,7 +316,7 @@ public class TestGeoUtils extends LuceneTestCase {
// Leaf cell: brute force check all docs that fall within this cell:
for(int docID=0;docID<docLons.length;docID++) {
if (cell.contains(docLons[docID], docLats[docID])) {
- double distanceMeters = GeoDistanceUtils.haversin(centerLat, centerLon, docLats[docID], docLons[docID]);
+ double distanceMeters = SloppyMath.haversinMeters(centerLat, centerLon, docLats[docID], docLons[docID]);
if (distanceMeters <= radiusMeters) {
if (VERBOSE) {
log.println(" check doc=" + docID + ": match!");
@@ -517,7 +518,7 @@ public class TestGeoUtils extends LuceneTestCase {
// Done matching, now verify:
for(int docID=0;docID<numDocs;docID++) {
- double distanceMeters = GeoDistanceUtils.haversin(centerLat, centerLon, docLats[docID], docLons[docID]);
+ double distanceMeters = SloppyMath.haversinMeters(centerLat, centerLon, docLats[docID], docLons[docID]);
final Boolean expected;
final double percentError = Math.abs(distanceMeters - radiusMeters) / distanceMeters;
if (percentError <= DISTANCE_PCT_ERR) {