You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by rj...@apache.org on 2014/01/15 02:20:47 UTC
svn commit: r1558259 - in /lucene/dev/trunk/lucene: ./
core/src/java/org/apache/lucene/util/ core/src/test/org/apache/lucene/util/
expressions/src/test/org/apache/lucene/expressions/
expressions/src/test/org/apache/lucene/expressions/js/
Author: rjernst
Date: Wed Jan 15 01:20:47 2014
New Revision: 1558259
URL: http://svn.apache.org/r1558259
Log:
LUCENE-5271: A slightly more accurate SloppyMath distance
Modified:
lucene/dev/trunk/lucene/CHANGES.txt
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/SloppyMath.java
lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestSloppyMath.java
lucene/dev/trunk/lucene/expressions/src/test/org/apache/lucene/expressions/TestDemoExpressions.java
lucene/dev/trunk/lucene/expressions/src/test/org/apache/lucene/expressions/js/TestJavascriptFunction.java
Modified: lucene/dev/trunk/lucene/CHANGES.txt
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/CHANGES.txt?rev=1558259&r1=1558258&r2=1558259&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/CHANGES.txt (original)
+++ lucene/dev/trunk/lucene/CHANGES.txt Wed Jan 15 01:20:47 2014
@@ -167,6 +167,9 @@ Optimizations
* LUCENE-5372: Replace StringBuffer by StringBuilder, where possible.
(Joshua Hartman via Uwe Schindler, Dawid Weiss, Mike McCandless)
+* LUCENE-5271: A slightly more accurate SloppyMath distance.
+ (Gilad Barkai via Ryan Ernst)
+
Changes in Runtime Behavior
* LUCENE-5362: IndexReader and SegmentCoreReaders now throw
Modified: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/SloppyMath.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/SloppyMath.java?rev=1558259&r1=1558258&r2=1558259&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/SloppyMath.java (original)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/SloppyMath.java Wed Jan 15 01:20:47 2014
@@ -44,10 +44,16 @@ public class SloppyMath {
public static double haversin(double lat1, double lon1, double lat2, double lon2) {
double x1 = lat1 * TO_RADIANS;
double x2 = lat2 * TO_RADIANS;
- double h1 = (1 - cos(x1 - x2)) / 2;
- double h2 = (1 - cos((lon1 - lon2) * TO_RADIANS)) / 2;
- double h = h1 + cos(x1) * cos(x2) * h2;
- return TO_KILOMETERS * 2 * asin(Math.min(1, Math.sqrt(h)));
+ 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 = Math.abs((x1 + x2) / 2d);
+ int index = (int)(avgLat * RADIUS_INDEXER + 0.5) % earthDiameterPerLatitude.length;
+ double radius = earthDiameterPerLatitude[index];
+
+ return radius * asin(Math.min(1, Math.sqrt(h)));
+
}
/**
@@ -134,7 +140,6 @@ public class SloppyMath {
// haversin
private static final double TO_RADIANS = Math.PI / 180D;
- private static final double TO_KILOMETERS = 6371.0087714D;
// cos/asin
private static final double ONE_DIV_F2 = 1/2.0;
@@ -184,6 +189,11 @@ 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
@@ -226,5 +236,27 @@ 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;
+ }
}
}
Modified: lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestSloppyMath.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestSloppyMath.java?rev=1558259&r1=1558258&r2=1558259&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestSloppyMath.java (original)
+++ lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestSloppyMath.java Wed Jan 15 01:20:47 2014
@@ -21,6 +21,8 @@ import static org.apache.lucene.util.Slo
import static org.apache.lucene.util.SloppyMath.asin;
import static org.apache.lucene.util.SloppyMath.haversin;
+import java.util.Random;
+
public class TestSloppyMath extends LuceneTestCase {
// accuracy for cos()
static double COS_DELTA = 1E-15;
@@ -93,8 +95,22 @@ public class TestSloppyMath extends Luce
assertEquals(0, haversin(90, -180, 90, 180), 0D);
assertEquals(0, haversin(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);
+
+ Random r = random();
+ double randomLat1 = 40.7143528 + (r.nextInt(10) - 5) * 360;
+ double randomLon1 = -74.0059731 + (r.nextInt(10) - 5) * 360;
+
+ 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);
+
+
// from solr and ES tests (with their respective epsilons)
- assertEquals(314.40338, haversin(1, 2, 3, 4), 10e-5);
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);
Modified: lucene/dev/trunk/lucene/expressions/src/test/org/apache/lucene/expressions/TestDemoExpressions.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/expressions/src/test/org/apache/lucene/expressions/TestDemoExpressions.java?rev=1558259&r1=1558258&r2=1558259&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/expressions/src/test/org/apache/lucene/expressions/TestDemoExpressions.java (original)
+++ lucene/dev/trunk/lucene/expressions/src/test/org/apache/lucene/expressions/TestDemoExpressions.java Wed Jan 15 01:20:47 2014
@@ -198,12 +198,12 @@ public class TestDemoExpressions extend
TopFieldDocs td = searcher.search(new MatchAllDocsQuery(), null, 3, sort);
FieldDoc d = (FieldDoc) td.scoreDocs[0];
- assertEquals(0.4621D, (Double)d.fields[0], 1E-4);
+ assertEquals(0.4619D, (Double)d.fields[0], 1E-4);
d = (FieldDoc) td.scoreDocs[1];
- assertEquals(1.0550D, (Double)d.fields[0], 1E-4);
+ assertEquals(1.0546D, (Double)d.fields[0], 1E-4);
d = (FieldDoc) td.scoreDocs[2];
- assertEquals(5.2859D, (Double)d.fields[0], 1E-4);
+ assertEquals(5.2842D, (Double)d.fields[0], 1E-4);
}
}
Modified: lucene/dev/trunk/lucene/expressions/src/test/org/apache/lucene/expressions/js/TestJavascriptFunction.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/expressions/src/test/org/apache/lucene/expressions/js/TestJavascriptFunction.java?rev=1558259&r1=1558258&r2=1558259&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/expressions/src/test/org/apache/lucene/expressions/js/TestJavascriptFunction.java (original)
+++ lucene/dev/trunk/lucene/expressions/src/test/org/apache/lucene/expressions/js/TestJavascriptFunction.java Wed Jan 15 01:20:47 2014
@@ -158,7 +158,7 @@ public class TestJavascriptFunction exte
}
public void testHaversinMethod() throws Exception {
- assertEvaluatesTo("haversin(40.7143528,-74.0059731,40.759011,-73.9844722)", 5.285885589128);
+ assertEvaluatesTo("haversin(40.7143528,-74.0059731,40.759011,-73.9844722)", 5.284299568309);
}
public void testLnMethod() throws Exception {