You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by mi...@apache.org on 2015/10/18 12:21:12 UTC
svn commit: r1709253 - in /lucene/dev/branches/lucene6780/lucene/sandbox/src:
java/org/apache/lucene/document/ java/org/apache/lucene/search/
java/org/apache/lucene/util/ test/org/apache/lucene/search/
test/org/apache/lucene/util/
Author: mikemccand
Date: Sun Oct 18 10:21:12 2015
New Revision: 1709253
URL: http://svn.apache.org/viewvc?rev=1709253&view=rev
Log:
LUCENE-6780: don't allow too-large radius in distance query (depending on origin); reduce resolution for large bbox
Modified:
lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/document/GeoPointField.java
lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceQuery.java
lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInBBoxQueryImpl.java
lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointTermsEnum.java
lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/util/GeoHashUtils.java
lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/util/GeoProjectionUtils.java
lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/util/GeoRect.java
lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/util/GeoUtils.java
lucene/dev/branches/lucene6780/lucene/sandbox/src/test/org/apache/lucene/search/TestGeoPointQuery.java
lucene/dev/branches/lucene6780/lucene/sandbox/src/test/org/apache/lucene/util/BaseGeoPointTestCase.java
Modified: lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/document/GeoPointField.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/document/GeoPointField.java?rev=1709253&r1=1709252&r2=1709253&view=diff
==============================================================================
--- lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/document/GeoPointField.java (original)
+++ lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/document/GeoPointField.java Sun Oct 18 10:21:12 2015
@@ -106,4 +106,24 @@ public final class GeoPointField extends
}
fieldsData = GeoUtils.mortonHash(lon, lat);
}
+
+ public double getLon() {
+ return GeoUtils.mortonUnhashLon((long) fieldsData);
+ }
+
+ public double getLat() {
+ return GeoUtils.mortonUnhashLat((long) fieldsData);
+ }
+
+ @Override
+ public String toString() {
+ if (fieldsData == null) {
+ return null;
+ }
+ StringBuilder sb = new StringBuilder();
+ sb.append(GeoUtils.mortonUnhashLon((long) fieldsData));
+ sb.append(',');
+ sb.append(GeoUtils.mortonUnhashLat((long) fieldsData));
+ return sb.toString();
+ }
}
Modified: lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceQuery.java?rev=1709253&r1=1709252&r2=1709253&view=diff
==============================================================================
--- lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceQuery.java (original)
+++ lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceQuery.java Sun Oct 18 10:21:12 2015
@@ -20,6 +20,7 @@ package org.apache.lucene.search;
import org.apache.lucene.index.IndexReader;
import org.apache.lucene.util.GeoRect;
import org.apache.lucene.util.GeoUtils;
+import org.apache.lucene.util.SloppyMath;
/** Implements a simple point distance query on a GeoPoint field. This is based on
* {@link org.apache.lucene.search.GeoPointInBBoxQuery} and is implemented using a two phase approach. First,
@@ -50,6 +51,14 @@ public final class GeoPointDistanceQuery
private GeoPointDistanceQuery(final String field, GeoRect bbox, final double centerLon,
final double centerLat, final double radiusMeters) {
super(field, bbox.minLon, bbox.minLat, bbox.maxLon, bbox.maxLat);
+ {
+ // check longitudinal overlap (limits radius)
+ final double maxRadius = SloppyMath.haversin(centerLat, centerLon, centerLat, (180.0 + centerLon) % 360)*1000.0;
+ if (radiusMeters > maxRadius) {
+ throw new IllegalArgumentException("radiusMeters " + radiusMeters + " exceeds maxRadius [" + maxRadius
+ + "] at location [" + centerLon + " " + centerLat + "]");
+ }
+ }
if (GeoUtils.isValidLon(centerLon) == false) {
throw new IllegalArgumentException("invalid centerLon " + centerLon);
Modified: lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInBBoxQueryImpl.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInBBoxQueryImpl.java?rev=1709253&r1=1709252&r2=1709253&view=diff
==============================================================================
--- lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInBBoxQueryImpl.java (original)
+++ lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInBBoxQueryImpl.java Sun Oct 18 10:21:12 2015
@@ -19,10 +19,12 @@ package org.apache.lucene.search;
import java.io.IOException;
+import org.apache.lucene.document.GeoPointField;
import org.apache.lucene.index.Terms;
import org.apache.lucene.index.TermsEnum;
import org.apache.lucene.util.AttributeSource;
import org.apache.lucene.util.GeoUtils;
+import org.apache.lucene.util.SloppyMath;
import org.apache.lucene.util.ToStringUtils;
/** Package private implementation for the public facing GeoPointInBBoxQuery delegate class.
@@ -59,6 +61,23 @@ class GeoPointInBBoxQueryImpl extends Ge
super(tenum, minLon, minLat, maxLon, maxLat);
}
+ @Override
+ protected short computeMaxShift() {
+ final short shiftFactor;
+
+ // compute diagonal radius
+ double midLon = (maxLon - minLon) * 0.5;
+ double midLat = (maxLat - minLat) * 0.5;
+
+ if (SloppyMath.haversin(minLat, minLon, midLat, midLon)*1000 > 1000000) {
+ shiftFactor = 5;
+ } else {
+ shiftFactor = 4;
+ }
+
+ return (short)(GeoPointField.PRECISION_STEP * shiftFactor);
+ }
+
/**
* Determine whether the quad-cell crosses the shape
*/
Modified: lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointTermsEnum.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointTermsEnum.java?rev=1709253&r1=1709252&r2=1709253&view=diff
==============================================================================
--- lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointTermsEnum.java (original)
+++ lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointTermsEnum.java Sun Oct 18 10:21:12 2015
@@ -53,13 +53,13 @@ abstract class GeoPointTermsEnum extends
GeoPointTermsEnum(final TermsEnum tenum, final double minLon, final double minLat,
final double maxLon, final double maxLat) {
super(tenum);
- DETAIL_LEVEL = (short)(((GeoUtils.BITS<<1)-computeMaxShift())/2);
final long rectMinHash = GeoUtils.mortonHash(minLon, minLat);
final long rectMaxHash = GeoUtils.mortonHash(maxLon, maxLat);
this.minLon = GeoUtils.mortonUnhashLon(rectMinHash);
this.minLat = GeoUtils.mortonUnhashLat(rectMinHash);
this.maxLon = GeoUtils.mortonUnhashLon(rectMaxHash);
this.maxLat = GeoUtils.mortonUnhashLat(rectMaxHash);
+ DETAIL_LEVEL = (short)(((GeoUtils.BITS<<1)-computeMaxShift())/2);
computeRange(0L, (short) (((GeoUtils.BITS) << 1) - 1));
Collections.sort(rangeBounds);
Modified: lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/util/GeoHashUtils.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/util/GeoHashUtils.java?rev=1709253&r1=1709252&r2=1709253&view=diff
==============================================================================
--- lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/util/GeoHashUtils.java (original)
+++ lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/util/GeoHashUtils.java Sun Oct 18 10:21:12 2015
@@ -64,6 +64,25 @@ public class GeoHashUtils {
}
/**
+ * Encode an existing geohash long to the provided precision
+ */
+ public static long longEncode(long geohash, int level) {
+ final short precision = (short)(geohash & 15);
+ if (precision == level) {
+ return geohash;
+ } else if (precision > level) {
+ return ((geohash >>> (((precision - level) * 5) + 4)) << 4) | level;
+ }
+ return ((geohash >>> 4) << (((level - precision) * 5) + 4) | level);
+ }
+
+ public static long fromMorton(long morton, int level) {
+ long mFlipped = BitUtil.flipFlop(morton);
+ mFlipped >>>= (((GeoHashUtils.PRECISION - level) * 5) + MORTON_OFFSET);
+ return (mFlipped << 4) | level;
+ }
+
+ /**
* Encode to a geohash string from the geohash based long format
*/
public static final String stringEncode(long geoHashLong) {
@@ -71,7 +90,7 @@ public class GeoHashUtils {
geoHashLong >>>= 4;
char[] chars = new char[level];
do {
- chars[--level] = BASE_32[(int)(geoHashLong&31L)];
+ chars[--level] = BASE_32[(int) (geoHashLong&31L)];
geoHashLong>>>=5;
} while(level > 0);
@@ -89,19 +108,10 @@ public class GeoHashUtils {
* Encode to a level specific geohash string from full resolution longitude, latitude
*/
public static final String stringEncode(final double lon, final double lat, final int level) {
- // bit twiddle to geohash (since geohash is a swapped (lon/lat) encoding)
- final long hashedVal = BitUtil.flipFlop(GeoUtils.mortonHash(lon, lat));
+ // convert to geohashlong
+ final long ghLong = fromMorton(GeoUtils.mortonHash(lon, lat), level);
+ return stringEncode(ghLong);
- StringBuilder geoHash = new StringBuilder();
- short precision = 0;
- final short msf = (GeoUtils.BITS<<1)-5;
- long mask = 31L<<msf;
- do {
- geoHash.append(BASE_32[(int)((mask & hashedVal)>>>(msf-(precision*5)))]);
- // next 5 bits
- mask >>>= 5;
- } while (++precision < level);
- return geoHash.toString();
}
/**
@@ -151,7 +161,7 @@ public class GeoHashUtils {
final int level = (int)(geoHashLong&15);
final short odd = (short)(level & 1);
- return BitUtil.flipFlop((geoHashLong >>> 4) << odd) << (((12 - level) * 5) + (MORTON_OFFSET - odd));
+ return BitUtil.flipFlop(((geoHashLong >>> 4) << odd) << (((12 - level) * 5) + (MORTON_OFFSET - odd)));
}
private static final char encode(int x, int y) {
Modified: lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/util/GeoProjectionUtils.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/util/GeoProjectionUtils.java?rev=1709253&r1=1709252&r2=1709253&view=diff
==============================================================================
--- lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/util/GeoProjectionUtils.java (original)
+++ lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/util/GeoProjectionUtils.java Sun Oct 18 10:21:12 2015
@@ -31,14 +31,10 @@ public class GeoProjectionUtils {
static final double PI_OVER_2 = StrictMath.PI / 2.0D;
static final double SEMIMAJOR_AXIS2 = SEMIMAJOR_AXIS * SEMIMAJOR_AXIS;
static final double SEMIMINOR_AXIS2 = SEMIMINOR_AXIS * SEMIMINOR_AXIS;
- public static final short MIN_LON = -180;
- public static final double MIN_LON_RADIANS = StrictMath.toRadians(MIN_LON);
- public static final short MIN_LAT = -90;
- public static final double MIN_LAT_RADIANS = StrictMath.toRadians(MIN_LAT);
- public static final short MAX_LON = 180;
- public static final double MAX_LON_RADIANS = StrictMath.toRadians(MAX_LON);
- public static final short MAX_LAT = 90;
- public static final double MAX_LAT_RADIANS = StrictMath.toRadians(MAX_LAT);
+ public static final double MIN_LON_RADIANS = StrictMath.toRadians(GeoUtils.MIN_LON_INCL);
+ public static final double MIN_LAT_RADIANS = StrictMath.toRadians(GeoUtils.MIN_LAT_INCL);
+ public static final double MAX_LON_RADIANS = StrictMath.toRadians(GeoUtils.MAX_LON_INCL);
+ public static final double MAX_LAT_RADIANS = StrictMath.toRadians(GeoUtils.MAX_LAT_INCL);
/**
* Converts from geocentric earth-centered earth-fixed to geodesic lat/lon/alt
@@ -383,8 +379,8 @@ public class GeoProjectionUtils {
final double lam = lambda - (1-c) * FLATTENING * sinAlpha *
(sigma + c * sinSigma * (cos2SigmaM + c * cosSigma * (-1 + 2* cos2SigmaM*cos2SigmaM)));
- pt[0] = lon + StrictMath.toDegrees(lam);
- pt[1] = StrictMath.toDegrees(lat2);
+ pt[0] = GeoUtils.normalizeLon(lon + StrictMath.toDegrees(lam));
+ pt[1] = GeoUtils.normalizeLat(StrictMath.toDegrees(lat2));
return pt;
}
Modified: lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/util/GeoRect.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/util/GeoRect.java?rev=1709253&r1=1709252&r2=1709253&view=diff
==============================================================================
--- lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/util/GeoRect.java (original)
+++ lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/util/GeoRect.java Sun Oct 18 10:21:12 2015
@@ -29,13 +29,13 @@ public class GeoRect {
throw new IllegalArgumentException("invalid minLon " + minLon);
}
if (GeoUtils.isValidLon(maxLon) == false) {
- throw new IllegalArgumentException("invalid maxLon " + minLon);
+ throw new IllegalArgumentException("invalid maxLon " + maxLon);
}
if (GeoUtils.isValidLat(minLat) == false) {
throw new IllegalArgumentException("invalid minLat " + minLat);
}
if (GeoUtils.isValidLat(maxLat) == false) {
- throw new IllegalArgumentException("invalid maxLat " + minLat);
+ throw new IllegalArgumentException("invalid maxLat " + maxLat);
}
this.minLon = minLon;
this.maxLon = maxLon;
Modified: lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/util/GeoUtils.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/util/GeoUtils.java?rev=1709253&r1=1709252&r2=1709253&view=diff
==============================================================================
--- lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/util/GeoUtils.java (original)
+++ lucene/dev/branches/lucene6780/lucene/sandbox/src/java/org/apache/lucene/util/GeoUtils.java Sun Oct 18 10:21:12 2015
@@ -25,9 +25,9 @@ import java.util.ArrayList;
* @lucene.experimental
*/
public final class GeoUtils {
- public static final short BITS = 32;
- private static final double LON_SCALE = ((0x1L<<BITS)-1)/360.0D;
- private static final double LAT_SCALE = ((0x1L<<BITS)-1)/180.0D;
+ public static final short BITS = 31;
+ private static final double LON_SCALE = (0x1L<<BITS)/360.0D;
+ private static final double LAT_SCALE = (0x1L<<BITS)/180.0D;
public static final double TOLERANCE = 1E-6;
/** Minimum longitude value. */
@@ -59,19 +59,19 @@ public final class GeoUtils {
}
private static long scaleLon(final double val) {
- return (long) ((val-GeoProjectionUtils.MIN_LON) * LON_SCALE);
+ return (long) ((val-MIN_LON_INCL) * LON_SCALE);
}
private static long scaleLat(final double val) {
- return (long) ((val-GeoProjectionUtils.MIN_LAT) * LAT_SCALE);
+ return (long) ((val-MIN_LAT_INCL) * LAT_SCALE);
}
private static double unscaleLon(final long val) {
- return (val / LON_SCALE) + GeoProjectionUtils.MIN_LON;
+ return (val / LON_SCALE) + MIN_LON_INCL;
}
private static double unscaleLat(final long val) {
- return (val / LAT_SCALE) + GeoProjectionUtils.MIN_LAT;
+ return (val / LAT_SCALE) + MIN_LAT_INCL;
}
public static double compare(final double v1, final double v2) {
@@ -338,7 +338,7 @@ public final class GeoUtils {
public static GeoRect circleToBBox(final double centerLon, final double centerLat, final double radiusMeters) {
final double radLat = StrictMath.toRadians(centerLat);
final double radLon = StrictMath.toRadians(centerLon);
- double radDistance = (radiusMeters + 12000) / GeoProjectionUtils.SEMIMAJOR_AXIS;
+ double radDistance = radiusMeters / GeoProjectionUtils.SEMIMAJOR_AXIS;
double minLat = radLat - radDistance;
double maxLat = radLat + radDistance;
double minLon;
Modified: lucene/dev/branches/lucene6780/lucene/sandbox/src/test/org/apache/lucene/search/TestGeoPointQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene6780/lucene/sandbox/src/test/org/apache/lucene/search/TestGeoPointQuery.java?rev=1709253&r1=1709252&r2=1709253&view=diff
==============================================================================
--- lucene/dev/branches/lucene6780/lucene/sandbox/src/test/org/apache/lucene/search/TestGeoPointQuery.java (original)
+++ lucene/dev/branches/lucene6780/lucene/sandbox/src/test/org/apache/lucene/search/TestGeoPointQuery.java Sun Oct 18 10:21:12 2015
@@ -45,10 +45,8 @@ public class TestGeoPointQuery extends B
private static IndexReader reader = null;
private static IndexSearcher searcher = null;
- // error threshold for point-distance queries (in meters)
- // @todo haversine is sloppy, would be good to have a better heuristic for
- // determining the possible haversine error
- private static final int DISTANCE_ERR = 1000;
+ // error threshold for point-distance queries (in percent) NOTE: Guideline from USGS
+ private static final double DISTANCE_PCT_ERR = 0.005;
@Override
protected void addPointToDoc(String field, Document doc, double lat, double lon) {
@@ -199,7 +197,16 @@ public class TestGeoPointQuery extends B
double delta = StrictMath.abs(ptDistance - radius);
// if its within the distance error then it can be wrong
- return delta < DISTANCE_ERR;
+ return delta < (ptDistance*DISTANCE_PCT_ERR);
+ }
+
+ // nocommit fixme!
+ @AwaitsFix(bugUrl = "Fix Tolerance on GeoPolygonSearch tests")
+ public void testExplicitFailure() throws Exception {
+ TopDocs td = polygonQuery(new double[]{-116.6911, -116.6911, -116.39189, -116.39189, -116.6911},
+ new double[]{-20.357460000000003, -19.424280000000003, -19.424280000000003, -20.357460000000003, -20.357460000000003},
+ 20);
+ assertEquals("Explicit Failure", 2, td.totalHits);
}
public void testRectCrossesCircle() throws Exception {
@@ -277,6 +284,14 @@ public class TestGeoPointQuery extends B
assertEquals("testMultiValuedQuery failed", 5, td.totalHits);
}
+ public void testTooBigRadius() throws Exception {
+ try {
+ geoDistanceQuery(0.0, 85.0, 4000000, 20);
+ } catch (IllegalArgumentException e) {
+ e.getMessage().contains("exceeds maxRadius");
+ }
+ }
+
/**
* Explicitly large
*/
Modified: lucene/dev/branches/lucene6780/lucene/sandbox/src/test/org/apache/lucene/util/BaseGeoPointTestCase.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene6780/lucene/sandbox/src/test/org/apache/lucene/util/BaseGeoPointTestCase.java?rev=1709253&r1=1709252&r2=1709253&view=diff
==============================================================================
--- lucene/dev/branches/lucene6780/lucene/sandbox/src/test/org/apache/lucene/util/BaseGeoPointTestCase.java (original)
+++ lucene/dev/branches/lucene6780/lucene/sandbox/src/test/org/apache/lucene/util/BaseGeoPointTestCase.java Sun Oct 18 10:21:12 2015
@@ -672,7 +672,8 @@ public abstract class BaseGeoPointTestCa
verifyHits = new VerifyHits() {
@Override
protected Boolean shouldMatch(double pointLat, double pointLon) {
- return polyRectContainsPoint(bbox, pointLat, pointLon);
+ return GeoUtils.pointInPolygon(lons, lats, pointLat, pointLon);
+// return polyRectContainsPoint(bbox, pointLat, pointLon);
}
@Override