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/12/21 12:40:14 UTC
svn commit: r1721134 [16/48] - in /lucene/dev/branches/lucene6835: ./
dev-tools/ dev-tools/eclipse/dot.settings/ dev-tools/idea/.idea/libraries/
dev-tools/maven/ dev-tools/maven/lucene/analysis/morfologik/
dev-tools/scripts/ lucene/ lucene/analysis/ lu...
Modified: lucene/dev/branches/lucene6835/lucene/sandbox/src/java/org/apache/lucene/util/GeoProjectionUtils.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene6835/lucene/sandbox/src/java/org/apache/lucene/util/GeoProjectionUtils.java?rev=1721134&r1=1721133&r2=1721134&view=diff
==============================================================================
--- lucene/dev/branches/lucene6835/lucene/sandbox/src/java/org/apache/lucene/util/GeoProjectionUtils.java (original)
+++ lucene/dev/branches/lucene6835/lucene/sandbox/src/java/org/apache/lucene/util/GeoProjectionUtils.java Mon Dec 21 11:39:57 2015
@@ -17,6 +17,10 @@ package org.apache.lucene.util;
* limitations under the License.
*/
+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;
+
/**
* Reusable geo-spatial projection utility methods.
*
@@ -24,13 +28,18 @@ package org.apache.lucene.util;
*/
public class GeoProjectionUtils {
// WGS84 earth-ellipsoid major (a) minor (b) radius, (f) flattening and eccentricity (e)
- static final double SEMIMAJOR_AXIS = 6_378_137; // [m]
- static final double FLATTENING = 1.0/298.257223563;
- static final double SEMIMINOR_AXIS = SEMIMAJOR_AXIS * (1.0 - FLATTENING); //6_356_752.31420; // [m]
- static final double ECCENTRICITY = StrictMath.sqrt((2.0 - FLATTENING) * FLATTENING);
- static final double PI_OVER_2 = StrictMath.PI / 2.0D;
+ public static final double SEMIMAJOR_AXIS = 6_378_137; // [m]
+ public static final double FLATTENING = 1.0/298.257223563;
+ public static final double SEMIMINOR_AXIS = SEMIMAJOR_AXIS * (1.0 - FLATTENING); //6_356_752.31420; // [m]
+ public static final double ECCENTRICITY = StrictMath.sqrt((2.0 - FLATTENING) * FLATTENING);
static final double SEMIMAJOR_AXIS2 = SEMIMAJOR_AXIS * SEMIMAJOR_AXIS;
static final double SEMIMINOR_AXIS2 = SEMIMINOR_AXIS * SEMIMINOR_AXIS;
+ public static final double MIN_LON_RADIANS = TO_RADIANS * GeoUtils.MIN_LON_INCL;
+ public static final double MIN_LAT_RADIANS = TO_RADIANS * GeoUtils.MIN_LAT_INCL;
+ public static final double MAX_LON_RADIANS = TO_RADIANS * GeoUtils.MAX_LON_INCL;
+ public static final double MAX_LAT_RADIANS = TO_RADIANS * GeoUtils.MAX_LAT_INCL;
+ private static final double E2 = (SEMIMAJOR_AXIS2 - SEMIMINOR_AXIS2)/(SEMIMAJOR_AXIS2);
+ private static final double EP2 = (SEMIMAJOR_AXIS2 - SEMIMINOR_AXIS2)/(SEMIMINOR_AXIS2);
/**
* Converts from geocentric earth-centered earth-fixed to geodesic lat/lon/alt
@@ -43,8 +52,6 @@ public class GeoProjectionUtils {
public static final double[] ecfToLLA(final double x, final double y, final double z, double[] lla) {
boolean atPole = false;
final double ad_c = 1.0026000D;
- final double e2 = (SEMIMAJOR_AXIS2 - SEMIMINOR_AXIS2)/(SEMIMAJOR_AXIS2);
- final double ep2 = (SEMIMAJOR_AXIS2 - SEMIMINOR_AXIS2)/(SEMIMINOR_AXIS2);
final double cos67P5 = 0.38268343236508977D;
if (lla == null) {
@@ -55,18 +62,18 @@ public class GeoProjectionUtils {
lla[0] = StrictMath.atan2(y,x);
} else {
if (y > 0) {
- lla[0] = PI_OVER_2;
+ lla[0] = PIO2;
} else if (y < 0) {
- lla[0] = -PI_OVER_2;
+ lla[0] = -PIO2;
} else {
atPole = true;
lla[0] = 0.0D;
if (z > 0.0) {
- lla[1] = PI_OVER_2;
+ lla[1] = PIO2;
} else if (z < 0.0) {
- lla[1] = -PI_OVER_2;
+ lla[1] = -PIO2;
} else {
- lla[1] = PI_OVER_2;
+ lla[1] = PIO2;
lla[2] = -SEMIMINOR_AXIS;
return lla;
}
@@ -80,25 +87,25 @@ public class GeoProjectionUtils {
final double sinB0 = t0 / s0;
final double cosB0 = w / s0;
final double sin3B0 = sinB0 * sinB0 * sinB0;
- final double t1 = z + SEMIMINOR_AXIS * ep2 * sin3B0;
- final double sum = w - SEMIMAJOR_AXIS * e2 * cosB0 * cosB0 * cosB0;
+ final double t1 = z + SEMIMINOR_AXIS * EP2 * sin3B0;
+ final double sum = w - SEMIMAJOR_AXIS * E2 * cosB0 * cosB0 * cosB0;
final double s1 = StrictMath.sqrt(t1 * t1 + sum * sum);
final double sinP1 = t1 / s1;
final double cosP1 = sum / s1;
- final double rn = SEMIMAJOR_AXIS / StrictMath.sqrt(1.0D - e2 * sinP1 * sinP1);
+ final double rn = SEMIMAJOR_AXIS / StrictMath.sqrt(1.0D - E2 * sinP1 * sinP1);
if (cosP1 >= cos67P5) {
lla[2] = w / cosP1 - rn;
} else if (cosP1 <= -cos67P5) {
lla[2] = w / -cosP1 - rn;
} else {
- lla[2] = z / sinP1 + rn * (e2 - 1.0);
+ lla[2] = z / sinP1 + rn * (E2 - 1.0);
}
if (!atPole) {
lla[1] = StrictMath.atan(sinP1/cosP1);
}
- lla[0] = StrictMath.toDegrees(lla[0]);
- lla[1] = StrictMath.toDegrees(lla[1]);
+ lla[0] = TO_DEGREES * lla[0];
+ lla[1] = TO_DEGREES * lla[1];
return lla;
}
@@ -112,33 +119,32 @@ public class GeoProjectionUtils {
* @return either a new ecef array or the reusable ecf parameter
*/
public static final double[] llaToECF(double lon, double lat, double alt, double[] ecf) {
- lon = StrictMath.toRadians(lon);
- lat = StrictMath.toRadians(lat);
+ lon = TO_RADIANS * lon;
+ lat = TO_RADIANS * lat;
- final double sl = StrictMath.sin(lat);
+ final double sl = SloppyMath.sin(lat);
final double s2 = sl*sl;
- final double cl = StrictMath.cos(lat);
- final double ge2 = (SEMIMAJOR_AXIS2 - SEMIMINOR_AXIS2)/(SEMIMAJOR_AXIS2);
+ final double cl = SloppyMath.cos(lat);
if (ecf == null) {
ecf = new double[3];
}
- if (lat < -PI_OVER_2 && lat > -1.001D * PI_OVER_2) {
- lat = -PI_OVER_2;
- } else if (lat > PI_OVER_2 && lat < 1.001D * PI_OVER_2) {
- lat = PI_OVER_2;
+ if (lat < -PIO2 && lat > -1.001D * PIO2) {
+ lat = -PIO2;
+ } else if (lat > PIO2 && lat < 1.001D * PIO2) {
+ lat = PIO2;
}
- assert (lat >= -PI_OVER_2) || (lat <= PI_OVER_2);
+ assert (lat >= -PIO2) || (lat <= PIO2);
if (lon > StrictMath.PI) {
lon -= (2*StrictMath.PI);
}
- final double rn = SEMIMAJOR_AXIS / StrictMath.sqrt(1.0D - ge2 * s2);
- ecf[0] = (rn+alt) * cl * StrictMath.cos(lon);
- ecf[1] = (rn+alt) * cl * StrictMath.sin(lon);
- ecf[2] = ((rn*(1.0-ge2))+alt)*sl;
+ final double rn = SEMIMAJOR_AXIS / StrictMath.sqrt(1.0D - E2 * s2);
+ ecf[0] = (rn+alt) * cl * SloppyMath.cos(lon);
+ ecf[1] = (rn+alt) * cl * SloppyMath.sin(lon);
+ ecf[2] = ((rn*(1.0-E2))+alt)*sl;
return ecf;
}
@@ -268,13 +274,13 @@ public class GeoProjectionUtils {
phiMatrix = new double[3][3];
}
- originLon = StrictMath.toRadians(originLon);
- originLat = StrictMath.toRadians(originLat);
+ originLon = TO_RADIANS * originLon;
+ originLat = TO_RADIANS * originLat;
- final double sLon = StrictMath.sin(originLon);
- final double cLon = StrictMath.cos(originLon);
- final double sLat = StrictMath.sin(originLat);
- final double cLat = StrictMath.cos(originLat);
+ final double sLon = SloppyMath.sin(originLon);
+ final double cLon = SloppyMath.cos(originLon);
+ final double sLat = SloppyMath.sin(originLat);
+ final double cLat = SloppyMath.cos(originLat);
phiMatrix[0][0] = -sLon;
phiMatrix[0][1] = cLon;
@@ -302,13 +308,13 @@ public class GeoProjectionUtils {
phiMatrix = new double[3][3];
}
- originLon = StrictMath.toRadians(originLon);
- originLat = StrictMath.toRadians(originLat);
+ originLon = TO_RADIANS * originLon;
+ originLat = TO_RADIANS * originLat;
- final double sLat = StrictMath.sin(originLat);
- final double cLat = StrictMath.cos(originLat);
- final double sLon = StrictMath.sin(originLon);
- final double cLon = StrictMath.cos(originLon);
+ final double sLat = SloppyMath.sin(originLat);
+ final double cLat = SloppyMath.cos(originLat);
+ final double sLon = SloppyMath.sin(originLon);
+ final double cLon = SloppyMath.cos(originLon);
phiMatrix[0][0] = -sLon;
phiMatrix[1][0] = cLon;
@@ -333,22 +339,22 @@ public class GeoProjectionUtils {
* @param pt resulting point
* @return the point along a bearing at a given distance in meters
*/
- public static final double[] pointFromLonLatBearing(double lon, double lat, double bearing, double dist, double[] pt) {
+ public static final double[] pointFromLonLatBearingVincenty(double lon, double lat, double bearing, double dist, double[] pt) {
if (pt == null) {
pt = new double[2];
}
- final double alpha1 = StrictMath.toRadians(bearing);
- final double cosA1 = StrictMath.cos(alpha1);
- final double sinA1 = StrictMath.sin(alpha1);
- final double tanU1 = (1-FLATTENING) * StrictMath.tan(StrictMath.toRadians(lat));
+ final double alpha1 = TO_RADIANS * bearing;
+ final double cosA1 = SloppyMath.cos(alpha1);
+ final double sinA1 = SloppyMath.sin(alpha1);
+ final double tanU1 = (1-FLATTENING) * SloppyMath.tan(TO_RADIANS * lat);
final double cosU1 = 1 / StrictMath.sqrt((1+tanU1*tanU1));
final double sinU1 = tanU1*cosU1;
final double sig1 = StrictMath.atan2(tanU1, cosA1);
final double sinAlpha = cosU1 * sinA1;
final double cosSqAlpha = 1 - sinAlpha*sinAlpha;
- final double uSq = cosSqAlpha * (SEMIMAJOR_AXIS2 - SEMIMINOR_AXIS2) / SEMIMINOR_AXIS2;
+ final double uSq = cosSqAlpha * EP2;
final double A = 1 + uSq/16384D*(4096D + uSq * (-768D + uSq * (320D - 175D*uSq)));
final double B = uSq/1024D * (256D + uSq * (-128D + uSq * (74D - 47D * uSq)));
@@ -357,9 +363,9 @@ public class GeoProjectionUtils {
double sinSigma, cosSigma, cos2SigmaM, deltaSigma;
do {
- cos2SigmaM = StrictMath.cos(2*sig1 + sigma);
- sinSigma = StrictMath.sin(sigma);
- cosSigma = StrictMath.cos(sigma);
+ cos2SigmaM = SloppyMath.cos(2*sig1 + sigma);
+ sinSigma = SloppyMath.sin(sigma);
+ cosSigma = SloppyMath.cos(sigma);
deltaSigma = B * sinSigma * (cos2SigmaM + (B/4D) * (cosSigma*(-1+2*cos2SigmaM*cos2SigmaM)-
(B/6) * cos2SigmaM*(-3+4*sinSigma*sinSigma)*(-3+4*cos2SigmaM*cos2SigmaM)));
@@ -375,9 +381,42 @@ 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 + TO_DEGREES * lam);
+ pt[1] = GeoUtils.normalizeLat(TO_DEGREES * lat2);
+
+ return pt;
+ }
+
+ /**
+ * Finds a point along a bearing from a given lon,lat geolocation using great circle arc
+ *
+ * @param lon origin longitude in degrees
+ * @param lat origin latitude in degrees
+ * @param bearing azimuthal bearing in degrees
+ * @param dist distance in meters
+ * @param pt resulting point
+ * @return the point along a bearing at a given distance in meters
+ */
+ public static final double[] pointFromLonLatBearingGreatCircle(double lon, double lat, double bearing, double dist, double[] pt) {
+
+ if (pt == null) {
+ pt = new double[2];
+ }
+
+ lon *= TO_RADIANS;
+ lat *= TO_RADIANS;
+ bearing *= TO_RADIANS;
+
+ final double cLat = SloppyMath.cos(lat);
+ final double sLat = SloppyMath.sin(lat);
+ final double sinDoR = SloppyMath.sin(dist / GeoProjectionUtils.SEMIMAJOR_AXIS);
+ final double cosDoR = SloppyMath.cos(dist / GeoProjectionUtils.SEMIMAJOR_AXIS);
+
+ pt[1] = SloppyMath.asin(sLat*cosDoR + cLat * sinDoR * SloppyMath.cos(bearing));
+ pt[0] = TO_DEGREES * (lon + Math.atan2(SloppyMath.sin(bearing) * sinDoR * cLat, cosDoR - sLat * SloppyMath.sin(pt[1])));
+ pt[1] *= TO_DEGREES;
return pt;
}
+
}
Modified: lucene/dev/branches/lucene6835/lucene/sandbox/src/java/org/apache/lucene/util/GeoUtils.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene6835/lucene/sandbox/src/java/org/apache/lucene/util/GeoUtils.java?rev=1721134&r1=1721133&r2=1721134&view=diff
==============================================================================
--- lucene/dev/branches/lucene6835/lucene/sandbox/src/java/org/apache/lucene/util/GeoUtils.java (original)
+++ lucene/dev/branches/lucene6835/lucene/sandbox/src/java/org/apache/lucene/util/GeoUtils.java Mon Dec 21 11:39:57 2015
@@ -19,17 +19,18 @@ package org.apache.lucene.util;
import java.util.ArrayList;
+import static org.apache.lucene.util.SloppyMath.TO_DEGREES;
+import static org.apache.lucene.util.SloppyMath.TO_RADIANS;
+
/**
* Basic reusable geo-spatial utility methods
*
* @lucene.experimental
*/
public final class GeoUtils {
- private static final short MIN_LON = -180;
- private static final short MIN_LAT = -90;
- 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. */
@@ -48,37 +49,40 @@ public final class GeoUtils {
private GeoUtils() {
}
- public static Long mortonHash(final double lon, final double lat) {
+ public static final Long mortonHash(final double lon, final double lat) {
return BitUtil.interleave(scaleLon(lon), scaleLat(lat));
}
- public static double mortonUnhashLon(final long hash) {
+ public static final double mortonUnhashLon(final long hash) {
return unscaleLon(BitUtil.deinterleave(hash));
}
- public static double mortonUnhashLat(final long hash) {
+ public static final double mortonUnhashLat(final long hash) {
return unscaleLat(BitUtil.deinterleave(hash >>> 1));
}
- private static long scaleLon(final double val) {
- return (long) ((val-MIN_LON) * LON_SCALE);
+ private static final long scaleLon(final double val) {
+ return (long) ((val-MIN_LON_INCL) * LON_SCALE);
}
- private static long scaleLat(final double val) {
- return (long) ((val-MIN_LAT) * LAT_SCALE);
+ private static final long scaleLat(final double val) {
+ return (long) ((val-MIN_LAT_INCL) * LAT_SCALE);
}
- private static double unscaleLon(final long val) {
- return (val / LON_SCALE) + MIN_LON;
+ private static final double unscaleLon(final long val) {
+ return (val / LON_SCALE) + MIN_LON_INCL;
}
- private static double unscaleLat(final long val) {
- return (val / LAT_SCALE) + MIN_LAT;
+ private static final double unscaleLat(final long val) {
+ return (val / LAT_SCALE) + MIN_LAT_INCL;
}
+ /**
+ * Compare two position values within a {@link org.apache.lucene.util.GeoUtils#TOLERANCE} factor
+ */
public static double compare(final double v1, final double v2) {
- final double compare = v1-v2;
- return Math.abs(compare) <= TOLERANCE ? 0 : compare;
+ final double delta = v1-v2;
+ return Math.abs(delta) <= TOLERANCE ? 0 : delta;
}
/**
@@ -109,39 +113,6 @@ public final class GeoUtils {
return (off <= 180 ? off : 360-off) - 90;
}
- public static final boolean bboxContains(final double lon, final double lat, final double minLon,
- final double minLat, final double maxLon, final double maxLat) {
- return (compare(lon, minLon) >= 0 && compare(lon, maxLon) <= 0
- && compare(lat, minLat) >= 0 && compare(lat, maxLat) <= 0);
- }
-
- /**
- * simple even-odd point in polygon computation
- * 1. Determine if point is contained in the longitudinal range
- * 2. Determine whether point crosses the edge by computing the latitudinal delta
- * between the end-point of a parallel vector (originating at the point) and the
- * y-component of the edge sink
- *
- * NOTE: Requires polygon point (x,y) order either clockwise or counter-clockwise
- */
- public static boolean pointInPolygon(double[] x, double[] y, double lat, double lon) {
- assert x.length == y.length;
- boolean inPoly = false;
- /**
- * Note: This is using a euclidean coordinate system which could result in
- * upwards of 110KM error at the equator.
- * TODO convert coordinates to cylindrical projection (e.g. mercator)
- */
- for (int i = 1; i < x.length; i++) {
- if (x[i] < lon && x[i-1] >= lon || x[i-1] < lon && x[i] >= lon) {
- if (y[i] + (lon - x[i]) / (x[i-1] - x[i]) * (y[i-1] - y[i]) < lat) {
- inPoly = !inPoly;
- }
- }
- }
- return inPoly;
- }
-
public static String geoTermToString(long term) {
StringBuilder s = new StringBuilder(64);
final int numberOfLeadingZeros = Long.numberOfLeadingZeros(term);
@@ -154,105 +125,16 @@ public final class GeoUtils {
return s.toString();
}
-
- public static boolean rectDisjoint(final double aMinX, final double aMinY, final double aMaxX, final double aMaxY,
- final double bMinX, final double bMinY, final double bMaxX, final double bMaxY) {
- return (aMaxX < bMinX || aMinX > bMaxX || aMaxY < bMinY || aMinY > bMaxY);
- }
-
- /**
- * Computes whether a rectangle is wholly within another rectangle (shared boundaries allowed)
- */
- public static boolean rectWithin(final double aMinX, final double aMinY, final double aMaxX, final double aMaxY,
- final double bMinX, final double bMinY, final double bMaxX, final double bMaxY) {
- return !(aMinX < bMinX || aMinY < bMinY || aMaxX > bMaxX || aMaxY > bMaxY);
- }
-
- public static boolean rectCrosses(final double aMinX, final double aMinY, final double aMaxX, final double aMaxY,
- final double bMinX, final double bMinY, final double bMaxX, final double bMaxY) {
- return !(rectDisjoint(aMinX, aMinY, aMaxX, aMaxY, bMinX, bMinY, bMaxX, bMaxY) ||
- rectWithin(aMinX, aMinY, aMaxX, aMaxY, bMinX, bMinY, bMaxX, bMaxY));
- }
-
- /**
- * Computes whether rectangle a contains rectangle b (touching allowed)
- */
- public static boolean rectContains(final double aMinX, final double aMinY, final double aMaxX, final double aMaxY,
- final double bMinX, final double bMinY, final double bMaxX, final double bMaxY) {
- return !(bMinX < aMinX || bMinY < aMinY || bMaxX > aMaxX || bMaxY > aMaxY);
- }
-
- /**
- * Computes whether a rectangle intersects another rectangle (crosses, within, touching, etc)
- */
- public static boolean rectIntersects(final double aMinX, final double aMinY, final double aMaxX, final double aMaxY,
- final double bMinX, final double bMinY, final double bMaxX, final double bMaxY) {
- return !((aMaxX < bMinX || aMinX > bMaxX || aMaxY < bMinY || aMinY > bMaxY) );
- }
-
- /**
- * Computes whether a rectangle crosses a shape. (touching not allowed)
- */
- public static boolean rectCrossesPoly(final double rMinX, final double rMinY, final double rMaxX,
- final double rMaxY, final double[] shapeX, final double[] shapeY,
- final double sMinX, final double sMinY, final double sMaxX,
- final double sMaxY) {
- // short-circuit: if the bounding boxes are disjoint then the shape does not cross
- if (rectDisjoint(rMinX, rMinY, rMaxX, rMaxY, sMinX, sMinY, sMaxX, sMaxY)) {
- return false;
- }
-
- final double[][] bbox = new double[][] { {rMinX, rMinY}, {rMaxX, rMinY}, {rMaxX, rMaxY}, {rMinX, rMaxY}, {rMinX, rMinY} };
- final int polyLength = shapeX.length-1;
- double d, s, t, a1, b1, c1, a2, b2, c2;
- double x00, y00, x01, y01, x10, y10, x11, y11;
-
- // computes the intersection point between each bbox edge and the polygon edge
- for (short b=0; b<4; ++b) {
- a1 = bbox[b+1][1]-bbox[b][1];
- b1 = bbox[b][0]-bbox[b+1][0];
- c1 = a1*bbox[b+1][0] + b1*bbox[b+1][1];
- for (int p=0; p<polyLength; ++p) {
- a2 = shapeY[p+1]-shapeY[p];
- b2 = shapeX[p]-shapeX[p+1];
- // compute determinant
- d = a1*b2 - a2*b1;
- if (d != 0) {
- // lines are not parallel, check intersecting points
- c2 = a2*shapeX[p+1] + b2*shapeY[p+1];
- s = (1/d)*(b2*c1 - b1*c2);
- t = (1/d)*(a1*c2 - a2*c1);
- x00 = StrictMath.min(bbox[b][0], bbox[b+1][0]) - TOLERANCE;
- x01 = StrictMath.max(bbox[b][0], bbox[b+1][0]) + TOLERANCE;
- y00 = StrictMath.min(bbox[b][1], bbox[b+1][1]) - TOLERANCE;
- y01 = StrictMath.max(bbox[b][1], bbox[b+1][1]) + TOLERANCE;
- x10 = StrictMath.min(shapeX[p], shapeX[p+1]) - TOLERANCE;
- x11 = StrictMath.max(shapeX[p], shapeX[p+1]) + TOLERANCE;
- y10 = StrictMath.min(shapeY[p], shapeY[p+1]) - TOLERANCE;
- y11 = StrictMath.max(shapeY[p], shapeY[p+1]) + TOLERANCE;
- // check whether the intersection point is touching one of the line segments
- boolean touching = ((x00 == s && y00 == t) || (x01 == s && y01 == t))
- || ((x10 == s && y10 == t) || (x11 == s && y11 == t));
- // if line segments are not touching and the intersection point is within the range of either segment
- if (!(touching || x00 > s || x01 < s || y00 > t || y01 < t || x10 > s || x11 < s || y10 > t || y11 < t)) {
- return true;
- }
- }
- } // for each poly edge
- } // for each bbox edge
- return false;
- }
-
/**
* Converts a given circle (defined as a point/radius) to an approximated line-segment polygon
*
* @param lon longitudinal center of circle (in degrees)
* @param lat latitudinal center of circle (in degrees)
- * @param radius distance radius of circle (in meters)
+ * @param radiusMeters distance radius of circle (in meters)
* @return a list of lon/lat points representing the circle
*/
@SuppressWarnings({"unchecked","rawtypes"})
- public static ArrayList<double[]> circleToPoly(final double lon, final double lat, final double radius) {
+ public static ArrayList<double[]> circleToPoly(final double lon, final double lat, final double radiusMeters) {
double angle;
// a little under-sampling (to limit the number of polygonal points): using archimedes estimation of pi
final int sides = 25;
@@ -264,7 +146,7 @@ public final class GeoUtils {
final int sidesLen = sides-1;
for (int i=0; i<sidesLen; ++i) {
angle = (i*360/sides);
- pt = GeoProjectionUtils.pointFromLonLatBearing(lon, lat, angle, radius, pt);
+ pt = GeoProjectionUtils.pointFromLonLatBearingGreatCircle(lon, lat, angle, radiusMeters, pt);
lons[i] = pt[0];
lats[i] = pt[1];
}
@@ -278,115 +160,78 @@ public final class GeoUtils {
}
/**
- * Computes whether a rectangle is within a given polygon (shared boundaries allowed)
+ * Compute Bounding Box for a circle using WGS-84 parameters
*/
- public static boolean rectWithinPoly(final double rMinX, final double rMinY, final double rMaxX, final double rMaxY,
- final double[] shapeX, final double[] shapeY, final double sMinX,
- final double sMinY, final double sMaxX, final double sMaxY) {
- // check if rectangle crosses poly (to handle concave/pacman polys), then check that all 4 corners
- // are contained
- return !(rectCrossesPoly(rMinX, rMinY, rMaxX, rMaxY, shapeX, shapeY, sMinX, sMinY, sMaxX, sMaxY) ||
- !pointInPolygon(shapeX, shapeY, rMinY, rMinX) || !pointInPolygon(shapeX, shapeY, rMinY, rMaxX) ||
- !pointInPolygon(shapeX, shapeY, rMaxY, rMaxX) || !pointInPolygon(shapeX, shapeY, rMaxY, rMinX));
- }
-
- private static boolean rectAnyCornersOutsideCircle(final double rMinX, final double rMinY, final double rMaxX, final double rMaxY,
- final double centerLon, final double centerLat, final double radius) {
- return (SloppyMath.haversin(centerLat, centerLon, rMinY, rMinX)*1000.0 > radius
- || SloppyMath.haversin(centerLat, centerLon, rMaxY, rMinX)*1000.0 > radius
- || SloppyMath.haversin(centerLat, centerLon, rMaxY, rMaxX)*1000.0 > radius
- || SloppyMath.haversin(centerLat, centerLon, rMinY, rMaxX)*1000.0 > radius);
- }
-
- private static boolean rectAnyCornersInCircle(final double rMinX, final double rMinY, final double rMaxX, final double rMaxY,
- final double centerLon, final double centerLat, final double radius) {
- return (SloppyMath.haversin(centerLat, centerLon, rMinY, rMinX)*1000.0 <= radius
- || SloppyMath.haversin(centerLat, centerLon, rMaxY, rMinX)*1000.0 <= radius
- || SloppyMath.haversin(centerLat, centerLon, rMaxY, rMaxX)*1000.0 <= radius
- || SloppyMath.haversin(centerLat, centerLon, rMinY, rMaxX)*1000.0 <= radius);
- }
-
- public static boolean rectWithinCircle(final double rMinX, final double rMinY, final double rMaxX, final double rMaxY,
- final double centerLon, final double centerLat, final double radius) {
- return !(rectAnyCornersOutsideCircle(rMinX, rMinY, rMaxX, rMaxY, centerLon, centerLat, radius));
- }
+ public static GeoRect circleToBBox(final double centerLon, final double centerLat, final double radiusMeters) {
+ final double radLat = TO_RADIANS * centerLat;
+ final double radLon = TO_RADIANS * centerLon;
+ double radDistance = radiusMeters / GeoProjectionUtils.SEMIMAJOR_AXIS;
+ double minLat = radLat - radDistance;
+ double maxLat = radLat + radDistance;
+ double minLon;
+ double maxLon;
+
+ if (minLat > GeoProjectionUtils.MIN_LAT_RADIANS && maxLat < GeoProjectionUtils.MAX_LAT_RADIANS) {
+ double deltaLon = SloppyMath.asin(SloppyMath.sin(radDistance) / SloppyMath.cos(radLat));
+ minLon = radLon - deltaLon;
+ if (minLon < GeoProjectionUtils.MIN_LON_RADIANS) {
+ minLon += 2d * StrictMath.PI;
+ }
+ maxLon = radLon + deltaLon;
+ if (maxLon > GeoProjectionUtils.MAX_LON_RADIANS) {
+ maxLon -= 2d * StrictMath.PI;
+ }
+ } else {
+ // a pole is within the distance
+ minLat = StrictMath.max(minLat, GeoProjectionUtils.MIN_LAT_RADIANS);
+ maxLat = StrictMath.min(maxLat, GeoProjectionUtils.MAX_LAT_RADIANS);
+ minLon = GeoProjectionUtils.MIN_LON_RADIANS;
+ maxLon = GeoProjectionUtils.MAX_LON_RADIANS;
+ }
- /**
- * Computes whether a rectangle crosses a circle
- */
- public static boolean rectCrossesCircle(final double rMinX, final double rMinY, final double rMaxX, final double rMaxY,
- final double centerLon, final double centerLat, final double radius) {
- return rectAnyCornersInCircle(rMinX, rMinY, rMaxX, rMaxY, centerLon, centerLat, radius)
- || lineCrossesSphere(rMinX, rMinY, 0, rMaxX, rMinY, 0, centerLon, centerLat, 0, radius)
- || lineCrossesSphere(rMaxX, rMinY, 0, rMaxX, rMaxY, 0, centerLon, centerLat, 0, radius)
- || lineCrossesSphere(rMaxX, rMaxY, 0, rMinX, rMaxY, 0, centerLon, centerLat, 0, radius)
- || lineCrossesSphere(rMinX, rMaxY, 0, rMinX, rMinY, 0, centerLon, centerLat, 0, radius);
- }
-
- public static boolean circleWithinRect(double rMinX, final double rMinY, final double rMaxX, final double rMaxY,
- final double centerLon, final double centerLat, final double radius) {
- return !(centerLon < rMinX || centerLon > rMaxX || centerLat > rMaxY || centerLat < rMinY
- || SloppyMath.haversin(rMinY, centerLon, centerLat, centerLon) < radius
- || SloppyMath.haversin(rMaxY, centerLon, centerLat, centerLon) < radius
- || SloppyMath.haversin(centerLat, rMinX, centerLat, centerLon) < radius
- || SloppyMath.haversin(centerLat, rMaxX, centerLat, centerLon) < radius);
+ return new GeoRect(TO_DEGREES * minLon, TO_DEGREES * maxLon, TO_DEGREES * minLat, TO_DEGREES * maxLat);
}
/**
- * Computes whether or a 3dimensional line segment intersects or crosses a sphere
- *
- * @param lon1 longitudinal location of the line segment start point (in degrees)
- * @param lat1 latitudinal location of the line segment start point (in degrees)
- * @param alt1 altitude of the line segment start point (in degrees)
- * @param lon2 longitudinal location of the line segment end point (in degrees)
- * @param lat2 latitudinal location of the line segment end point (in degrees)
- * @param alt2 altitude of the line segment end point (in degrees)
- * @param centerLon longitudinal location of center search point (in degrees)
- * @param centerLat latitudinal location of center search point (in degrees)
- * @param centerAlt altitude of the center point (in meters)
- * @param radius search sphere radius (in meters)
- * @return whether the provided line segment is a secant of the
+ * Compute Bounding Box for a polygon using WGS-84 parameters
*/
- private static boolean lineCrossesSphere(double lon1, double lat1, double alt1, double lon2,
- double lat2, double alt2, double centerLon, double centerLat,
- double centerAlt, double radius) {
- // convert to cartesian 3d (in meters)
- double[] ecf1 = GeoProjectionUtils.llaToECF(lon1, lat1, alt1, null);
- double[] ecf2 = GeoProjectionUtils.llaToECF(lon2, lat2, alt2, null);
- double[] cntr = GeoProjectionUtils.llaToECF(centerLon, centerLat, centerAlt, null);
-
- final double dX = ecf2[0] - ecf1[0];
- final double dY = ecf2[1] - ecf1[1];
- final double dZ = ecf2[2] - ecf1[2];
- final double fX = ecf1[0] - cntr[0];
- final double fY = ecf1[1] - cntr[1];
- final double fZ = ecf1[2] - cntr[2];
-
- final double a = dX*dX + dY*dY + dZ*dZ;
- final double b = 2 * (fX*dX + fY*dY + fZ*dZ);
- final double c = (fX*fX + fY*fY + fZ*fZ) - (radius*radius);
-
- double discrim = (b*b)-(4*a*c);
- if (discrim < 0) {
- return false;
+ public static GeoRect polyToBBox(double[] polyLons, double[] polyLats) {
+ if (polyLons.length != polyLats.length) {
+ throw new IllegalArgumentException("polyLons and polyLats must be equal length");
}
- discrim = StrictMath.sqrt(discrim);
- final double a2 = 2*a;
- final double t1 = (-b - discrim)/a2;
- final double t2 = (-b + discrim)/a2;
+ double minLon = Double.POSITIVE_INFINITY;
+ double maxLon = Double.NEGATIVE_INFINITY;
+ double minLat = Double.POSITIVE_INFINITY;
+ double maxLat = Double.NEGATIVE_INFINITY;
- if ( (t1 < 0 || t1 > 1) ) {
- return !(t2 < 0 || t2 > 1);
+ for (int i=0;i<polyLats.length;i++) {
+ if (GeoUtils.isValidLon(polyLons[i]) == false) {
+ throw new IllegalArgumentException("invalid polyLons[" + i + "]=" + polyLons[i]);
+ }
+ if (GeoUtils.isValidLat(polyLats[i]) == false) {
+ throw new IllegalArgumentException("invalid polyLats[" + i + "]=" + polyLats[i]);
+ }
+ minLon = Math.min(polyLons[i], minLon);
+ maxLon = Math.max(polyLons[i], maxLon);
+ minLat = Math.min(polyLats[i], minLat);
+ maxLat = Math.max(polyLats[i], maxLat);
}
- return true;
+ return new GeoRect(GeoUtils.unscaleLon(GeoUtils.scaleLon(minLon)), GeoUtils.unscaleLon(GeoUtils.scaleLon(maxLon)),
+ GeoUtils.unscaleLat(GeoUtils.scaleLat(minLat)), GeoUtils.unscaleLat(GeoUtils.scaleLat(maxLat)));
}
+ /**
+ * validates latitude value is within standard +/-90 coordinate bounds
+ */
public static boolean isValidLat(double lat) {
return Double.isNaN(lat) == false && lat >= MIN_LAT_INCL && lat <= MAX_LAT_INCL;
}
+ /**
+ * validates longitude value is within standard +/-180 coordinate bounds
+ */
public static boolean isValidLon(double lon) {
return Double.isNaN(lon) == false && lon >= MIN_LON_INCL && lon <= MAX_LON_INCL;
}
Modified: lucene/dev/branches/lucene6835/lucene/sandbox/src/test/org/apache/lucene/search/TestDocValuesRangeQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene6835/lucene/sandbox/src/test/org/apache/lucene/search/TestDocValuesRangeQuery.java?rev=1721134&r1=1721133&r2=1721134&view=diff
==============================================================================
--- lucene/dev/branches/lucene6835/lucene/sandbox/src/test/org/apache/lucene/search/TestDocValuesRangeQuery.java (original)
+++ lucene/dev/branches/lucene6835/lucene/sandbox/src/test/org/apache/lucene/search/TestDocValuesRangeQuery.java Mon Dec 21 11:39:57 2015
@@ -19,9 +19,9 @@ package org.apache.lucene.search;
import java.io.IOException;
+import org.apache.lucene.document.DimensionalLongField;
import org.apache.lucene.document.Document;
import org.apache.lucene.document.Field.Store;
-import org.apache.lucene.document.LongField;
import org.apache.lucene.document.NumericDocValuesField;
import org.apache.lucene.document.SortedDocValuesField;
import org.apache.lucene.document.SortedNumericDocValuesField;
@@ -34,9 +34,9 @@ import org.apache.lucene.index.Term;
import org.apache.lucene.search.BooleanClause.Occur;
import org.apache.lucene.store.Directory;
import org.apache.lucene.util.BytesRef;
-import org.apache.lucene.util.BytesRefBuilder;
import org.apache.lucene.util.LuceneTestCase;
import org.apache.lucene.util.NumericUtils;
+import org.apache.lucene.util.RamUsageEstimator;
import org.apache.lucene.util.TestUtil;
public class TestDocValuesRangeQuery extends LuceneTestCase {
@@ -53,12 +53,12 @@ public class TestDocValuesRangeQuery ext
for (int j = 0; j < numValues; ++j) {
final long value = TestUtil.nextLong(random(), -100, 10000);
doc.add(new SortedNumericDocValuesField("dv", value));
- doc.add(new LongField("idx", value, Store.NO));
+ doc.add(new DimensionalLongField("idx", value));
}
iw.addDocument(doc);
}
if (random().nextBoolean()) {
- iw.deleteDocuments(NumericRangeQuery.newLongRange("idx", 0L, 10L, true, true));
+ iw.deleteDocuments(DimensionalRangeQuery.new1DLongRange("idx", 0L, true, 10L, true));
}
iw.commit();
final IndexReader reader = iw.getReader();
@@ -70,7 +70,7 @@ public class TestDocValuesRangeQuery ext
final Long max = random().nextBoolean() ? null : TestUtil.nextLong(random(), -100, 1000);
final boolean minInclusive = random().nextBoolean();
final boolean maxInclusive = random().nextBoolean();
- final Query q1 = NumericRangeQuery.newLongRange("idx", min, max, minInclusive, maxInclusive);
+ final Query q1 = DimensionalRangeQuery.new1DLongRange("idx", min, minInclusive, max, maxInclusive);
final Query q2 = DocValuesRangeQuery.newLongRange("dv", min, max, minInclusive, maxInclusive);
assertSameMatches(searcher, q1, q2, false);
}
@@ -84,9 +84,9 @@ public class TestDocValuesRangeQuery ext
if (l == null) {
return null;
} else {
- final BytesRefBuilder bytes = new BytesRefBuilder();
- NumericUtils.longToPrefixCoded(l, 0, bytes);
- return bytes.get();
+ byte[] bytes = new byte[RamUsageEstimator.NUM_BYTES_LONG];
+ NumericUtils.longToBytes(l, bytes, 0);
+ return new BytesRef(bytes);
}
}
@@ -180,13 +180,13 @@ public class TestDocValuesRangeQuery ext
final long value = TestUtil.nextLong(random(), -100, 10000);
doc.add(new SortedNumericDocValuesField("dv1", value));
doc.add(new SortedSetDocValuesField("dv2", toSortableBytes(value)));
- doc.add(new LongField("idx", value, Store.NO));
+ doc.add(new DimensionalLongField("idx", value));
doc.add(new StringField("f", random().nextBoolean() ? "a" : "b", Store.NO));
}
iw.addDocument(doc);
}
if (random().nextBoolean()) {
- iw.deleteDocuments(NumericRangeQuery.newLongRange("idx", 0L, 10L, true, true));
+ iw.deleteDocuments(DimensionalRangeQuery.new1DLongRange("idx", 0L, true, 10L, true));
}
iw.commit();
final IndexReader reader = iw.getReader();
@@ -200,7 +200,7 @@ public class TestDocValuesRangeQuery ext
final boolean maxInclusive = random().nextBoolean();
BooleanQuery.Builder ref = new BooleanQuery.Builder();
- ref.add(NumericRangeQuery.newLongRange("idx", min, max, minInclusive, maxInclusive), Occur.FILTER);
+ ref.add(DimensionalRangeQuery.new1DLongRange("idx", min, minInclusive, max, maxInclusive), Occur.FILTER);
ref.add(new TermQuery(new Term("f", "a")), Occur.MUST);
BooleanQuery.Builder bq1 = new BooleanQuery.Builder();
@@ -265,12 +265,12 @@ public class TestDocValuesRangeQuery ext
Query q1 = DocValuesRangeQuery.newLongRange("dv1", 0L, 100L, random().nextBoolean(), random().nextBoolean());
Weight w = searcher.createNormalizedWeight(q1, true);
Scorer s = w.scorer(ctx);
- assertNotNull(s.asTwoPhaseIterator());
+ assertNotNull(s.twoPhaseIterator());
Query q2 = DocValuesRangeQuery.newBytesRefRange("dv2", toSortableBytes(0L), toSortableBytes(100L), random().nextBoolean(), random().nextBoolean());
w = searcher.createNormalizedWeight(q2, true);
s = w.scorer(ctx);
- assertNotNull(s.asTwoPhaseIterator());
+ assertNotNull(s.twoPhaseIterator());
reader.close();
dir.close();
Modified: lucene/dev/branches/lucene6835/lucene/sandbox/src/test/org/apache/lucene/search/TestGeoPointQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene6835/lucene/sandbox/src/test/org/apache/lucene/search/TestGeoPointQuery.java?rev=1721134&r1=1721133&r2=1721134&view=diff
==============================================================================
--- lucene/dev/branches/lucene6835/lucene/sandbox/src/test/org/apache/lucene/search/TestGeoPointQuery.java (original)
+++ lucene/dev/branches/lucene6835/lucene/sandbox/src/test/org/apache/lucene/search/TestGeoPointQuery.java Mon Dec 21 11:39:57 2015
@@ -17,57 +17,69 @@ package org.apache.lucene.search;
* limitations under the License.
*/
-import java.io.IOException;
-import java.util.ArrayList;
-import java.util.HashSet;
-import java.util.List;
-import java.util.Set;
-import java.util.concurrent.CountDownLatch;
-
import org.apache.lucene.analysis.MockAnalyzer;
import org.apache.lucene.document.Document;
import org.apache.lucene.document.Field;
import org.apache.lucene.document.FieldType;
import org.apache.lucene.document.GeoPointField;
-import org.apache.lucene.document.NumericDocValuesField;
-import org.apache.lucene.index.DirectoryReader;
+import org.apache.lucene.document.StringField;
import org.apache.lucene.index.IndexReader;
-import org.apache.lucene.index.IndexWriter;
-import org.apache.lucene.index.IndexWriterConfig;
-import org.apache.lucene.index.LeafReaderContext;
-import org.apache.lucene.index.MultiDocValues;
-import org.apache.lucene.index.NumericDocValues;
import org.apache.lucene.index.RandomIndexWriter;
-import org.apache.lucene.index.Term;
import org.apache.lucene.store.Directory;
-import org.apache.lucene.util.FixedBitSet;
-import org.apache.lucene.util.GeoDistanceUtils;
+import org.apache.lucene.util.BaseGeoPointTestCase;
+import org.apache.lucene.util.GeoRect;
+import org.apache.lucene.util.GeoRelationUtils;
import org.apache.lucene.util.GeoUtils;
-import org.apache.lucene.util.IOUtils;
-import org.apache.lucene.util.LuceneTestCase;
import org.apache.lucene.util.SloppyMath;
-import org.apache.lucene.util.TestGeoUtils;
import org.apache.lucene.util.TestUtil;
import org.junit.AfterClass;
import org.junit.BeforeClass;
-import org.junit.Test;
/**
* Unit testing for basic GeoPoint query logic
*
* @lucene.experimental
*/
-public class TestGeoPointQuery extends LuceneTestCase {
+
+public class TestGeoPointQuery extends BaseGeoPointTestCase {
+
private static Directory directory = null;
private static IndexReader reader = null;
private static IndexSearcher searcher = null;
- private static final String FIELD_NAME = "geoField";
+ // error threshold for point-distance queries (in percent) NOTE: Guideline from USGS
+ private static final double DISTANCE_PCT_ERR = 0.005;
+
+ @Override
+ protected boolean forceSmall() {
+ // TODO: GeoUtils are potentially slow if we use small=false with heavy testing
+ return true;
+ }
+
+ @Override
+ protected void addPointToDoc(String field, Document doc, double lat, double lon) {
+ doc.add(new GeoPointField(field, lon, lat, Field.Store.NO));
+ }
- // 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;
+ @Override
+ protected Query newRectQuery(String field, GeoRect rect) {
+ return new GeoPointInBBoxQuery(field, rect.minLon, rect.minLat, rect.maxLon, rect.maxLat);
+ }
+
+ @Override
+ protected Query newDistanceQuery(String field, double centerLat, double centerLon, double radiusMeters) {
+ return new GeoPointDistanceQuery(field, centerLon, centerLat, radiusMeters);
+ }
+
+ @Override
+ protected Query newDistanceRangeQuery(String field, double centerLat, double centerLon, double minRadiusMeters, double radiusMeters) {
+ return new GeoPointDistanceRangeQuery(field, centerLon, centerLat, minRadiusMeters, radiusMeters);
+ }
+
+ @Override
+ protected Query newPolygonQuery(String field, double[] lats, double[] lons) {
+ return new GeoPointInPolygonQuery(field, lons, lats);
+ }
@BeforeClass
public static void beforeClass() throws Exception {
@@ -90,10 +102,10 @@ public class TestGeoPointQuery extends L
new GeoPointField(FIELD_NAME, -96.4538113027811, 32.94823588839368, storedPoint),
new GeoPointField(FIELD_NAME, -96.65084838867188, 33.06047141970814, storedPoint),
new GeoPointField(FIELD_NAME, -96.7772, 32.778650, storedPoint),
- new GeoPointField(FIELD_NAME, -83.99724648980559, 58.29438379542874, storedPoint),
+ new GeoPointField(FIELD_NAME, -177.23537676036358, -88.56029371730983, storedPoint),
new GeoPointField(FIELD_NAME, -26.779373834241003, 33.541429799076354, storedPoint),
new GeoPointField(FIELD_NAME, -77.35379276106497, 26.774024500421728, storedPoint),
- new GeoPointField(FIELD_NAME, -14.796283808944777, -62.455081198245665, storedPoint),
+ new GeoPointField(FIELD_NAME, -14.796283808944777, -90.0, storedPoint),
new GeoPointField(FIELD_NAME, -178.8538113027811, 32.94823588839368, storedPoint),
new GeoPointField(FIELD_NAME, 178.8538113027811, 32.94823588839368, storedPoint),
new GeoPointField(FIELD_NAME, -73.998776, 40.720611, storedPoint),
@@ -113,6 +125,13 @@ public class TestGeoPointQuery extends L
writer.addDocument(doc);
}
+ // index random string documents
+ for (int i=0; i<random().nextInt(10); ++i) {
+ Document doc = new Document();
+ doc.add(new StringField("string", Integer.toString(i), Field.Store.NO));
+ writer.addDocument(doc);
+ }
+
reader = writer.getReader();
searcher = newSearcher(reader);
writer.close();
@@ -142,13 +161,81 @@ public class TestGeoPointQuery extends L
return searcher.search(q, limit);
}
- @Test
+ @Override
+ protected Boolean rectContainsPoint(GeoRect rect, double pointLat, double pointLon) {
+ if (GeoUtils.compare(pointLon, rect.minLon) == 0.0 ||
+ GeoUtils.compare(pointLon, rect.maxLon) == 0.0 ||
+ GeoUtils.compare(pointLat, rect.minLat) == 0.0 ||
+ GeoUtils.compare(pointLat, rect.maxLat) == 0.0) {
+ // Point is very close to rect boundary
+ return null;
+ }
+
+ if (rect.minLon < rect.maxLon) {
+ return GeoRelationUtils.pointInRect(pointLon, pointLat, rect.minLon, rect.minLat, rect.maxLon, rect.maxLat);
+ } else {
+ // Rect crosses dateline:
+ return GeoRelationUtils.pointInRect(pointLon, pointLat, -180.0, rect.minLat, rect.maxLon, rect.maxLat)
+ || GeoRelationUtils.pointInRect(pointLon, pointLat, rect.minLon, rect.minLat, 180.0, rect.maxLat);
+ }
+ }
+
+ @Override
+ protected Boolean polyRectContainsPoint(GeoRect rect, double pointLat, double pointLon) {
+ return rectContainsPoint(rect, pointLat, pointLon);
+ }
+
+ @Override
+ protected Boolean circleContainsPoint(double centerLat, double centerLon, double radiusMeters, double pointLat, double pointLon) {
+ if (radiusQueryCanBeWrong(centerLat, centerLon, pointLon, pointLat, radiusMeters)) {
+ return null;
+ } else {
+ return SloppyMath.haversin(centerLat, centerLon, pointLat, pointLon)*1000.0 <= radiusMeters;
+ }
+ }
+
+ @Override
+ protected Boolean distanceRangeContainsPoint(double centerLat, double centerLon, double minRadiusMeters, double radiusMeters, double pointLat, double pointLon) {
+ if (radiusQueryCanBeWrong(centerLat, centerLon, pointLon, pointLat, minRadiusMeters)
+ || radiusQueryCanBeWrong(centerLat, centerLon, pointLon, pointLat, radiusMeters)) {
+ return null;
+ } else {
+ final double d = SloppyMath.haversin(centerLat, centerLon, pointLat, pointLon)*1000.0;
+ return d >= minRadiusMeters && d <= radiusMeters;
+ }
+ }
+
+ private static boolean radiusQueryCanBeWrong(double centerLat, double centerLon, double ptLon, double ptLat,
+ final double radius) {
+ final long hashedCntr = GeoUtils.mortonHash(centerLon, centerLat);
+ centerLon = GeoUtils.mortonUnhashLon(hashedCntr);
+ centerLat = GeoUtils.mortonUnhashLat(hashedCntr);
+ final long hashedPt = GeoUtils.mortonHash(ptLon, ptLat);
+ ptLon = GeoUtils.mortonUnhashLon(hashedPt);
+ ptLat = GeoUtils.mortonUnhashLat(hashedPt);
+
+ double ptDistance = SloppyMath.haversin(centerLat, centerLon, ptLat, ptLon)*1000.0;
+ double delta = StrictMath.abs(ptDistance - radius);
+
+ // if its within the distance error then it can be wrong
+ return delta < (ptDistance*DISTANCE_PCT_ERR);
+ }
+
+ public void testRectCrossesCircle() throws Exception {
+ assertTrue(GeoRelationUtils.rectCrossesCircle(-180, -90, 180, 0.0, 0.667, 0.0, 88000.0));
+ }
+
+ private TopDocs geoDistanceRangeQuery(double lon, double lat, double minRadius, double maxRadius, int limit)
+ throws Exception {
+ GeoPointDistanceRangeQuery q = new GeoPointDistanceRangeQuery(FIELD_NAME, lon, lat, minRadius, maxRadius);
+ return searcher.search(q, limit);
+ }
+
public void testBBoxQuery() throws Exception {
TopDocs td = bboxQuery(-96.7772, 32.778650, -96.77690000, 32.778950, 5);
assertEquals("GeoBoundingBoxQuery failed", 4, td.totalHits);
}
- @Test
public void testPolyQuery() throws Exception {
TopDocs td = polygonQuery(new double[]{-96.7682647, -96.8280029, -96.6288757, -96.4929199,
-96.6041564, -96.7449188, -96.76826477, -96.7682647},
@@ -157,7 +244,6 @@ public class TestGeoPointQuery extends L
assertEquals("GeoPolygonQuery failed", 2, td.totalHits);
}
- @Test
public void testPacManPolyQuery() throws Exception {
// pacman
double[] px = {0, 10, 10, 0, -8, -10, -8, 0, 10, 10, 0};
@@ -176,30 +262,26 @@ public class TestGeoPointQuery extends L
double yMax = 1;//5;
// test cell crossing poly
- assertTrue(GeoUtils.rectCrossesPoly(xMin, yMin, xMax, yMax, px, py, xMinA, yMinA, xMaxA, yMaxA));
- assertFalse(GeoUtils.rectCrossesPoly(-5, 0, 0.000001, 5, px, py, xMin, yMin, xMax, yMax));
- assertTrue(GeoUtils.rectWithinPoly(-5, 0, -2, 5, px, py, xMin, yMin, xMax, yMax));
+ assertTrue(GeoRelationUtils.rectCrossesPoly(xMin, yMin, xMax, yMax, px, py, xMinA, yMinA, xMaxA, yMaxA));
+ assertFalse(GeoRelationUtils.rectCrossesPoly(-5, 0, 0.000001, 5, px, py, xMin, yMin, xMax, yMax));
+ assertTrue(GeoRelationUtils.rectWithinPoly(-5, 0, -2, 5, px, py, xMin, yMin, xMax, yMax));
}
- @Test
public void testBBoxCrossDateline() throws Exception {
TopDocs td = bboxQuery(179.0, -45.0, -179.0, -44.0, 20);
assertEquals("BBoxCrossDateline query failed", 2, td.totalHits);
}
- @Test
public void testWholeMap() throws Exception {
- TopDocs td = bboxQuery(-179.9, -89.9, 179.9, 89.9, 20);
+ TopDocs td = bboxQuery(GeoUtils.MIN_LON_INCL, GeoUtils.MIN_LAT_INCL, GeoUtils.MAX_LON_INCL, GeoUtils.MAX_LAT_INCL, 20);
assertEquals("testWholeMap failed", 24, td.totalHits);
}
- @Test
public void smallTest() throws Exception {
TopDocs td = geoDistanceQuery(-73.998776, 40.720611, 1, 20);
assertEquals("smallTest failed", 2, td.totalHits);
}
- @Test
public void testInvalidBBox() throws Exception {
try {
bboxQuery(179.0, -92.0, 181.0, -91.0, 20);
@@ -209,35 +291,44 @@ public class TestGeoPointQuery extends L
throw new Exception("GeoBoundingBox should not accept invalid lat/lon");
}
- @Test
public void testGeoDistanceQuery() throws Exception {
TopDocs td = geoDistanceQuery(-96.4538113027811, 32.94823588839368, 6000, 20);
assertEquals("GeoDistanceQuery failed", 2, td.totalHits);
}
- @Test
+ /** see https://issues.apache.org/jira/browse/LUCENE-6905 */
+ public void testNonEmptyTermsEnum() throws Exception {
+ TopDocs td = geoDistanceQuery(-177.23537676036358, -88.56029371730983, 7757.999232959935, 20);
+ assertEquals("GeoDistanceQuery failed", 2, td.totalHits);
+ }
+
public void testMultiValuedQuery() throws Exception {
TopDocs td = bboxQuery(-96.4538113027811, 32.7559529921407, -96.7706036567688, 32.7756745755423, 20);
// 3 single valued docs + 2 multi-valued docs
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
*/
- @Nightly
public void testGeoDistanceQueryHuge() throws Exception {
- TopDocs td = geoDistanceQuery(-96.4538113027811, 32.94823588839368, 2000000, 20);
- assertEquals("GeoDistanceQuery failed", 13, td.totalHits);
+ TopDocs td = geoDistanceQuery(-96.4538113027811, 32.94823588839368, 6000000, 20);
+ assertEquals("GeoDistanceQuery failed", 16, td.totalHits);
}
- @Test
public void testGeoDistanceQueryCrossDateline() throws Exception {
TopDocs td = geoDistanceQuery(-179.9538113027811, 32.94823588839368, 120000, 20);
assertEquals("GeoDistanceQuery failed", 3, td.totalHits);
}
- @Test
public void testInvalidGeoDistanceQuery() throws Exception {
try {
geoDistanceQuery(181.0, 92.0, 120000, 20);
@@ -247,393 +338,14 @@ public class TestGeoPointQuery extends L
throw new Exception("GeoDistanceQuery should not accept invalid lat/lon as origin");
}
- public void testRandomTiny() throws Exception {
- // Make sure single-leaf-node case is OK:
- doTestRandom(10);
- }
-
- public void testRandom() throws Exception {
- doTestRandom(10000);
+ public void testMaxDistanceRangeQuery() throws Exception {
+ TopDocs td = geoDistanceRangeQuery(0.0, 0.0, 10, 20000000, 20);
+ assertEquals("GeoDistanceRangeQuery failed", 24, td.totalHits);
}
- @Test
public void testMortonEncoding() throws Exception {
long hash = GeoUtils.mortonHash(180, 90);
assertEquals(180.0, GeoUtils.mortonUnhashLon(hash), 0);
assertEquals(90.0, GeoUtils.mortonUnhashLat(hash), 0);
}
-
- @Nightly
- public void testRandomBig() throws Exception {
- doTestRandom(200000);
- }
-
- private void doTestRandom(int count) throws Exception {
-
- int numPoints = atLeast(count);
-
- if (VERBOSE) {
- System.out.println("TEST: numPoints=" + numPoints);
- }
-
- double[] lats = new double[numPoints];
- double[] lons = new double[numPoints];
-
- boolean haveRealDoc = false;
-
- for (int docID=0;docID<numPoints;docID++) {
- int x = random().nextInt(20);
- if (x == 17) {
- // Some docs don't have a point:
- lats[docID] = Double.NaN;
- if (VERBOSE) {
- //System.out.println(" doc=" + docID + " is missing");
- }
- continue;
- }
-
- if (docID > 0 && x < 3 && haveRealDoc) {
- int oldDocID;
- while (true) {
- oldDocID = random().nextInt(docID);
- if (Double.isNaN(lats[oldDocID]) == false) {
- break;
- }
- }
-
- if (x == 0) {
- // Identical lat to old point
- lats[docID] = lats[oldDocID];
- lons[docID] = TestGeoUtils.randomLon();
- if (VERBOSE) {
- //System.out.println(" doc=" + docID + " lat=" + lats[docID] + " lon=" + lons[docID] + " (same lat as doc=" + oldDocID + ")");
- }
- } else if (x == 1) {
- // Identical lon to old point
- lats[docID] = TestGeoUtils.randomLat();
- lons[docID] = lons[oldDocID];
- if (VERBOSE) {
- //System.out.println(" doc=" + docID + " lat=" + lats[docID] + " lon=" + lons[docID] + " (same lon as doc=" + oldDocID + ")");
- }
- } else {
- assert x == 2;
- // Fully identical point:
- lats[docID] = lats[oldDocID];
- lons[docID] = lons[oldDocID];
- if (VERBOSE) {
- //System.out.println(" doc=" + docID + " lat=" + lats[docID] + " lon=" + lons[docID] + " (same lat/lon as doc=" + oldDocID + ")");
- }
- }
- } else {
- lats[docID] = TestGeoUtils.randomLat();
- lons[docID] = TestGeoUtils.randomLon();
- haveRealDoc = true;
- if (VERBOSE) {
- //System.out.println(" doc=" + docID + " lat=" + lats[docID] + " lon=" + lons[docID]);
- }
- }
- }
-
- verify(lats, lons);
- }
-
- private static void verify(double[] lats, double[] lons) throws Exception {
- IndexWriterConfig iwc = newIndexWriterConfig();
- Directory dir;
- if (lats.length > 100000) {
- dir = newFSDirectory(createTempDir("TestGeoPointQuery"));
- iwc.setCodec(TestUtil.getDefaultCodec());
- } else {
- dir = newDirectory();
- }
- Set<Integer> deleted = new HashSet<>();
- // RandomIndexWriter is too slow here:
- IndexWriter w = new IndexWriter(dir, iwc);
- for(int id=0;id<lats.length;id++) {
- Document doc = new Document();
- doc.add(newStringField("id", ""+id, Field.Store.NO));
- doc.add(new NumericDocValuesField("id", id));
- if (Double.isNaN(lats[id]) == false) {
- if (VERBOSE) {
- System.out.println(" id=" + id + " lat=" + lats[id] + " lon=" + lons[id]);
- }
- doc.add(new GeoPointField(FIELD_NAME, lons[id], lats[id], Field.Store.NO));
- } else if (VERBOSE) {
- System.out.println(" id=" + id + " skipped");
- }
- w.addDocument(doc);
- if (id > 0 && random().nextInt(100) == 42) {
- int idToDelete = random().nextInt(id);
- w.deleteDocuments(new Term("id", ""+idToDelete));
- deleted.add(idToDelete);
- if (VERBOSE) {
- System.out.println(" delete id=" + idToDelete);
- }
- }
- }
- if (random().nextBoolean()) {
- w.forceMerge(1);
- }
- IndexReader r = DirectoryReader.open(w, true);
- w.close();
-
- IndexSearcher s = newSearcher(r);
-
- // Make sure queries are thread safe:
- int numThreads = TestUtil.nextInt(random(), 2, 5);
-
- List<Thread> threads = new ArrayList<>();
- final int iters = atLeast(10);
-
- final CountDownLatch startingGun = new CountDownLatch(1);
-
- for(int i=0;i<numThreads;i++) {
- Thread thread = new Thread() {
- @Override
- public void run() {
- try {
- _run();
- } catch (Exception e) {
- throw new RuntimeException(e);
- }
- }
-
- private void _run() throws Exception {
- startingGun.await();
-
- NumericDocValues docIDToID = MultiDocValues.getNumericValues(r, "id");
-
- for (int iter=0;iter<iters;iter++) {
- if (VERBOSE) {
- System.out.println("\nTEST: iter=" + iter);
- }
-
- Query query;
-
- VerifyHits verifyHits;
-
- if (random().nextBoolean()) {
- GeoBoundingBox bbox = randomBBox();
-
- query = new GeoPointInBBoxQuery(FIELD_NAME, bbox.minLon, bbox.minLat, bbox.maxLon, bbox.maxLat);
- verifyHits = new VerifyHits() {
- @Override
- protected Boolean shouldMatch(double pointLat, double pointLon) {
-
- // morton encode & decode to compare apples to apples (that is, compare with same hash precision error
- // present in the index)
- long pointHash = GeoUtils.mortonHash(pointLon, pointLat);
- pointLon = GeoUtils.mortonUnhashLon(pointHash);
- pointLat = GeoUtils.mortonUnhashLat(pointHash);
-
- if (bboxQueryCanBeWrong(bbox, pointLat, pointLon)) {
- return null;
- } else {
- return rectContainsPointEnc(bbox, pointLat, pointLon);
- }
- }
- };
- } else if (random().nextBoolean()) {
-
- // generate a random bounding box
- GeoBoundingBox bbox = randomBBox();
-
- double centerLat = bbox.minLat + ((bbox.maxLat - bbox.minLat)/2.0);
- double centerLon = bbox.minLon + ((bbox.maxLon - bbox.minLon)/2.0);
-
- // radius (in meters) as a function of the random generated bbox
- final double radius = GeoDistanceUtils.vincentyDistance(centerLon, centerLat, centerLon, bbox.minLat);
- //final double radius = SloppyMath.haversin(centerLat, centerLon, bbox.minLat, centerLon)*1000;
- if (VERBOSE) {
- System.out.println("\t radius = " + radius);
- }
- // query using the centroid of the bounding box
- query = new GeoPointDistanceQuery(FIELD_NAME, centerLon, centerLat, radius);
-
- verifyHits = new VerifyHits() {
- @Override
- protected Boolean shouldMatch(double pointLat, double pointLon) {
- if (Double.isNaN(pointLat) || Double.isNaN(pointLon)) {
- return null;
- }
- if (radiusQueryCanBeWrong(centerLat, centerLon, pointLon, pointLat, radius)) {
- return null;
- } else {
- return distanceContainsPt(centerLon, centerLat, pointLon, pointLat, radius);
- }
- }
- };
-
- } else {
- GeoBoundingBox bbox = randomBBox();
-
- double[] pLats = new double[5];
- double[] pLons = new double[5];
- pLats[0] = bbox.minLat;
- pLons[0] = bbox.minLon;
- pLats[1] = bbox.maxLat;
- pLons[1] = bbox.minLon;
- pLats[2] = bbox.maxLat;
- pLons[2] = bbox.maxLon;
- pLats[3] = bbox.minLat;
- pLons[3] = bbox.maxLon;
- pLats[4] = bbox.minLat;
- pLons[4] = bbox.minLon;
- query = new GeoPointInPolygonQuery(FIELD_NAME, pLons, pLats);
-
- verifyHits = new VerifyHits() {
- @Override
- protected Boolean shouldMatch(double pointLat, double pointLon) {
- // morton encode & decode to compare apples to apples (that is, compare with same hash precision error
- // present in the index)
- long pointHash = GeoUtils.mortonHash(pointLon, pointLat);
- pointLon = GeoUtils.mortonUnhashLon(pointHash);
- pointLat = GeoUtils.mortonUnhashLat(pointHash);
-
- if (bboxQueryCanBeWrong(bbox, pointLat, pointLon)) {
- return null;
- } else {
- return rectContainsPointEnc(bbox, pointLat, pointLon);
- }
- }
- };
- }
-
- verifyHits.test(s, docIDToID, deleted, query, lats, lons);
- }
- }
- };
- thread.setName("T" + i);
- thread.start();
- threads.add(thread);
- }
-
- startingGun.countDown();
- for(Thread thread : threads) {
- thread.join();
- }
-
- IOUtils.close(r, dir);
- }
-
- private static abstract class VerifyHits {
-
- public void test(IndexSearcher s, NumericDocValues docIDToID, Set<Integer> deleted, Query query, double[] lats, double[] lons) throws Exception {
- int maxDoc = s.getIndexReader().maxDoc();
- final FixedBitSet hits = new FixedBitSet(maxDoc);
- s.search(query, new SimpleCollector() {
-
- private int docBase;
-
- @Override
- public boolean needsScores() {
- return false;
- }
-
- @Override
- protected void doSetNextReader(LeafReaderContext context) throws IOException {
- docBase = context.docBase;
- }
-
- @Override
- public void collect(int doc) {
- hits.set(docBase+doc);
- }
- });
-
- for(int docID=0;docID<maxDoc;docID++) {
- int id = (int) docIDToID.get(docID);
- Boolean expected;
- if (deleted.contains(id)) {
- expected = false;
- } else {
- expected = shouldMatch(lats[id], lons[id]);
- }
-
- // null means it's a borderline case which is allowed to be wrong:
- if (expected != null) {
-
- if (hits.get(docID) != expected) {
- System.out.println(Thread.currentThread().getName() + ": id=" + id +
- " docID=" + docID + " lat=" + lats[id] + " lon=" + lons[id] +
- " deleted?=" + deleted.contains(id) + " expected=" + expected + " but got " + hits.get(docID) +
- " query=" + query);
- fail("wrong hit");
- }
- }
- }
- }
-
- /** Return true if we definitely should match, false if we definitely
- * should not match, and null if it's a borderline case which might
- * go either way. */
- protected abstract Boolean shouldMatch(double lat, double lon);
- }
-
- private static boolean distanceContainsPt(double lonA, double latA, double lonB, double latB, final double radius) {
- final long hashedPtA = GeoUtils.mortonHash(lonA, latA);
- lonA = GeoUtils.mortonUnhashLon(hashedPtA);
- latA = GeoUtils.mortonUnhashLat(hashedPtA);
- final long hashedPtB = GeoUtils.mortonHash(lonB, latB);
- lonB = GeoUtils.mortonUnhashLon(hashedPtB);
- latB = GeoUtils.mortonUnhashLat(hashedPtB);
-
- return (SloppyMath.haversin(latA, lonA, latB, lonB)*1000.0 <= radius);
- }
-
- private static boolean rectContainsPointEnc(GeoBoundingBox bbox, double pointLat, double pointLon) {
- // We should never see a deleted doc here?
- assert Double.isNaN(pointLat) == false;
- return GeoUtils.bboxContains(pointLon, pointLat, bbox.minLon, bbox.minLat, bbox.maxLon, bbox.maxLat);
- }
-
- private static boolean radiusQueryCanBeWrong(double centerLat, double centerLon, double ptLon, double ptLat,
- final double radius) {
- final long hashedCntr = GeoUtils.mortonHash(centerLon, centerLat);
- centerLon = GeoUtils.mortonUnhashLon(hashedCntr);
- centerLat = GeoUtils.mortonUnhashLat(hashedCntr);
- final long hashedPt = GeoUtils.mortonHash(ptLon, ptLat);
- ptLon = GeoUtils.mortonUnhashLon(hashedPt);
- ptLat = GeoUtils.mortonUnhashLat(hashedPt);
-
- double ptDistance = SloppyMath.haversin(centerLat, centerLon, ptLat, ptLon)*1000.0;
- double delta = StrictMath.abs(ptDistance - radius);
-
- // if its within the distance error then it can be wrong
- return delta < DISTANCE_ERR;
- }
-
- private static boolean bboxQueryCanBeWrong(GeoBoundingBox bbox, double lat, double lon) {
- // we can tolerate variance at the GeoUtils.TOLERANCE decimal place
- final int tLon = (int)(lon/(GeoUtils.TOLERANCE-1));
- final int tLat = (int)(lat/(GeoUtils.TOLERANCE-1));
- final int tMinLon = (int)(bbox.minLon/(GeoUtils.TOLERANCE-1));
- final int tMinLat = (int)(bbox.minLat/(GeoUtils.TOLERANCE-1));
- final int tMaxLon = (int)(bbox.maxLon/(GeoUtils.TOLERANCE-1));
- final int tMaxLat = (int)(bbox.maxLat/(GeoUtils.TOLERANCE-1));
-
- return ((tMinLon - tLon) == 0 || (tMinLat - tLat) == 0
- || (tMaxLon - tLon) == 0 || (tMaxLat - tLat) == 0);
- }
-
- private static GeoBoundingBox randomBBox() {
- double lat0 = TestGeoUtils.randomLat();
- double lat1 = TestGeoUtils.randomLat();
- double lon0 = TestGeoUtils.randomLon();
- double lon1 = TestGeoUtils.randomLon();
-
- if (lat1 < lat0) {
- double x = lat0;
- lat0 = lat1;
- lat1 = x;
- }
-
- if (lon1 < lon0) {
- double x = lon0;
- lon0 = lon1;
- lon1 = x;
- }
-
- return new GeoBoundingBox(lon0, lon1, lat0, lat1);
- }
}
Modified: lucene/dev/branches/lucene6835/lucene/sandbox/src/test/org/apache/lucene/util/TestGeoUtils.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene6835/lucene/sandbox/src/test/org/apache/lucene/util/TestGeoUtils.java?rev=1721134&r1=1721133&r2=1721134&view=diff
==============================================================================
--- lucene/dev/branches/lucene6835/lucene/sandbox/src/test/org/apache/lucene/util/TestGeoUtils.java (original)
+++ lucene/dev/branches/lucene6835/lucene/sandbox/src/test/org/apache/lucene/util/TestGeoUtils.java Mon Dec 21 11:39:57 2015
@@ -17,12 +17,17 @@ package org.apache.lucene.util;
* limitations under the License.
*/
+import java.io.PrintWriter;
+import java.io.StringWriter;
import java.util.ArrayList;
import java.util.Collection;
+import java.util.HashSet;
import java.util.List;
+import java.util.Set;
import org.junit.BeforeClass;
-import org.junit.Test;
+
+import com.carrotsearch.randomizedtesting.generators.RandomInts;
/**
* Tests class for methods in GeoUtils
@@ -31,6 +36,9 @@ import org.junit.Test;
*/
public class TestGeoUtils extends LuceneTestCase {
+ private static final double LON_SCALE = (0x1L<<GeoUtils.BITS)/360.0D;
+ private static final double LAT_SCALE = (0x1L<<GeoUtils.BITS)/180.0D;
+
// Global bounding box we will "cover" in the random test; we have to make this "smallish" else the queries take very long:
private static double originLat;
private static double originLon;
@@ -54,7 +62,6 @@ public class TestGeoUtils extends Lucene
}
}
- @Test
public void testGeoHash() {
int numPoints = atLeast(100);
String randomGeoHashString;
@@ -63,8 +70,8 @@ public class TestGeoUtils extends Lucene
int randomLevel;
for (int i = 0; i < numPoints; ++i) {
// random point
- double lat = randomLatFullRange();
- double lon = randomLonFullRange();
+ double lat = randomLat(false);
+ double lon = randomLon(false);
// compute geohash straight from lat/lon and from morton encoded value to ensure they're the same
randomGeoHashString = GeoHashUtils.stringEncode(lon, lat, randomLevel = random().nextInt(12 - 1) + 1);
@@ -90,7 +97,6 @@ public class TestGeoUtils extends Lucene
* Pass condition: lat=42.6, lng=-5.6 should be encoded as "ezs42e44yx96",
* lat=57.64911 lng=10.40744 should be encoded as "u4pruydqqvj8"
*/
- @Test
public void testEncode() {
String hash = GeoHashUtils.stringEncode(-5.6, 42.6, 12);
assertEquals("ezs42e44yx96", hash);
@@ -103,7 +109,6 @@ public class TestGeoUtils extends Lucene
* Pass condition: lat=52.3738007, lng=4.8909347 should be encoded and then
* decoded within 0.00001 of the original value
*/
- @Test
public void testDecodePreciseLongitudeLatitude() {
final String geohash = GeoHashUtils.stringEncode(4.8909347, 52.3738007);
final long hash = GeoHashUtils.mortonEncode(geohash);
@@ -116,7 +121,6 @@ public class TestGeoUtils extends Lucene
* Pass condition: lat=84.6, lng=10.5 should be encoded and then decoded
* within 0.00001 of the original value
*/
- @Test
public void testDecodeImpreciseLongitudeLatitude() {
final String geohash = GeoHashUtils.stringEncode(10.5, 84.6);
@@ -126,7 +130,6 @@ public class TestGeoUtils extends Lucene
assertEquals(10.5, GeoUtils.mortonUnhashLon(hash), 0.00001D);
}
- @Test
public void testDecodeEncode() {
final String geoHash = "u173zq37x014";
assertEquals(geoHash, GeoHashUtils.stringEncode(4.8909347, 52.3738007));
@@ -139,7 +142,6 @@ public class TestGeoUtils extends Lucene
assertEquals(geoHash, GeoHashUtils.stringEncode(lon, lat));
}
- @Test
public void testNeighbors() {
String geohash = "gcpv";
List<String> expectedNeighbors = new ArrayList<>();
@@ -201,19 +203,335 @@ public class TestGeoUtils extends Lucene
assertEquals(expectedNeighbors, neighbors);
}
- public static double randomLatFullRange() {
- return (180d * random().nextDouble()) - 90d;
+ public void testClosestPointOnBBox() {
+ double[] result = new double[2];
+ GeoDistanceUtils.closestPointOnBBox(20, 30, 40, 50, 70, 70, result);
+ assertEquals(40.0, result[0], 0.0);
+ assertEquals(50.0, result[1], 0.0);
+
+ GeoDistanceUtils.closestPointOnBBox(-20, -20, 0, 0, 70, 70, result);
+ assertEquals(0.0, result[0], 0.0);
+ assertEquals(0.0, result[1], 0.0);
+ }
+
+ private static class Cell {
+ static int nextCellID;
+
+ final Cell parent;
+ final int cellID;
+ final double minLon, maxLon;
+ final double minLat, maxLat;
+ final int splitCount;
+
+ public Cell(Cell parent,
+ double minLon, double minLat,
+ double maxLon, double maxLat,
+ int splitCount) {
+ assert maxLon >= minLon;
+ assert maxLat >= minLat;
+ this.parent = parent;
+ this.minLon = minLon;
+ this.minLat = minLat;
+ this.maxLon = maxLon;
+ this.maxLat = maxLat;
+ this.cellID = nextCellID++;
+ this.splitCount = splitCount;
+ }
+
+ /** Returns true if the quantized point lies within this cell, inclusive on all bounds. */
+ public boolean contains(double lon, double lat) {
+ return lon >= minLon && lon <= maxLon && lat >= minLat && lat <= maxLat;
+ }
+
+ @Override
+ public String toString() {
+ return "cell=" + cellID + (parent == null ? "" : " parentCellID=" + parent.cellID) + " lon: " + minLon + " TO " + maxLon + ", lat: " + minLat + " TO " + maxLat + ", splits: " + splitCount;
+ }
+ }
+
+ public long scaleLon(final double val) {
+ return (long) ((val-GeoUtils.MIN_LON_INCL) * LON_SCALE);
}
- public static double randomLonFullRange() {
- return (360d * random().nextDouble()) - 180d;
+ public long scaleLat(final double val) {
+ return (long) ((val-GeoUtils.MIN_LAT_INCL) * LAT_SCALE);
}
- public static double randomLat() {
- return GeoUtils.normalizeLat(originLat + latRange * (random().nextDouble() - 0.5));
+ public double unscaleLon(final long val) {
+ return (val / LON_SCALE) + GeoUtils.MIN_LON_INCL;
}
- public static double randomLon() {
- return GeoUtils.normalizeLon(originLon + lonRange * (random().nextDouble() - 0.5));
+ public double unscaleLat(final long val) {
+ return (val / LAT_SCALE) + GeoUtils.MIN_LAT_INCL;
+ }
+
+ public double randomLat(boolean small) {
+ double result;
+ if (small) {
+ result = GeoUtils.normalizeLat(originLat + latRange * (random().nextDouble() - 0.5));
+ } else {
+ result = -90 + 180.0 * random().nextDouble();
+ }
+ return unscaleLat(scaleLat(result));
+ }
+
+ public double randomLon(boolean small) {
+ double result;
+ if (small) {
+ result = GeoUtils.normalizeLon(originLon + lonRange * (random().nextDouble() - 0.5));
+ } else {
+ result = -180 + 360.0 * random().nextDouble();
+ }
+ return unscaleLon(scaleLon(result));
+ }
+
+ private void findMatches(Set<Integer> hits, PrintWriter log, Cell root,
+ double centerLon, double centerLat, double radiusMeters,
+ double[] docLons, double[] docLats) {
+
+ if (VERBOSE) {
+ log.println(" root cell: " + root);
+ }
+
+ List<Cell> queue = new ArrayList<>();
+ queue.add(root);
+
+ int recurseDepth = RandomInts.randomIntBetween(random(), 5, 15);
+
+ while (queue.size() > 0) {
+ Cell cell = queue.get(queue.size()-1);
+ queue.remove(queue.size()-1);
+ if (VERBOSE) {
+ log.println(" cycle: " + cell + " queue.size()=" + queue.size());
+ }
+
+ if (random().nextInt(10) == 7 || cell.splitCount > recurseDepth) {
+ if (VERBOSE) {
+ log.println(" leaf");
+ }
+ // 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]);
+ if (distanceMeters <= radiusMeters) {
+ if (VERBOSE) {
+ log.println(" check doc=" + docID + ": match!");
+ }
+ hits.add(docID);
+ } else {
+ if (VERBOSE) {
+ log.println(" check doc=" + docID + ": no match");
+ }
+ }
+ }
+ }
+ } else {
+
+ if (GeoRelationUtils.rectWithinCircle(cell.minLon, cell.minLat, cell.maxLon, cell.maxLat, centerLon, centerLat, radiusMeters)) {
+ // Query circle fully contains this cell, just addAll:
+ if (VERBOSE) {
+ log.println(" circle fully contains cell: now addAll");
+ }
+ for(int docID=0;docID<docLons.length;docID++) {
+ if (cell.contains(docLons[docID], docLats[docID])) {
+ if (VERBOSE) {
+ log.println(" addAll doc=" + docID);
+ }
+ hits.add(docID);
+ }
+ }
+ continue;
+ } else if (GeoRelationUtils.rectWithin(root.minLon, root.minLat, root.maxLon, root.maxLat,
+ cell.minLon, cell.minLat, cell.maxLon, cell.maxLat)) {
+ // Fall through below to "recurse"
+ if (VERBOSE) {
+ log.println(" cell fully contains circle: keep splitting");
+ }
+ } else if (GeoRelationUtils.rectCrossesCircle(cell.minLon, cell.minLat, cell.maxLon, cell.maxLat,
+ centerLon, centerLat, radiusMeters)) {
+ // Fall through below to "recurse"
+ if (VERBOSE) {
+ log.println(" cell overlaps circle: keep splitting");
+ }
+ } else {
+ if (VERBOSE) {
+ log.println(" no overlap: drop this cell");
+ for(int docID=0;docID<docLons.length;docID++) {
+ if (cell.contains(docLons[docID], docLats[docID])) {
+ if (VERBOSE) {
+ log.println(" skip doc=" + docID);
+ }
+ }
+ }
+ }
+ continue;
+ }
+
+ // Randomly split:
+ if (random().nextBoolean()) {
+
+ // Split on lon:
+ double splitValue = cell.minLon + (cell.maxLon - cell.minLon) * random().nextDouble();
+ if (VERBOSE) {
+ log.println(" now split on lon=" + splitValue);
+ }
+ Cell cell1 = new Cell(cell,
+ cell.minLon, cell.minLat,
+ splitValue, cell.maxLat,
+ cell.splitCount+1);
+ Cell cell2 = new Cell(cell,
+ splitValue, cell.minLat,
+ cell.maxLon, cell.maxLat,
+ cell.splitCount+1);
+ if (VERBOSE) {
+ log.println(" split cell1: " + cell1);
+ log.println(" split cell2: " + cell2);
+ }
+ queue.add(cell1);
+ queue.add(cell2);
+ } else {
+
+ // Split on lat:
+ double splitValue = cell.minLat + (cell.maxLat - cell.minLat) * random().nextDouble();
+ if (VERBOSE) {
+ log.println(" now split on lat=" + splitValue);
+ }
+ Cell cell1 = new Cell(cell,
+ cell.minLon, cell.minLat,
+ cell.maxLon, splitValue,
+ cell.splitCount+1);
+ Cell cell2 = new Cell(cell,
+ cell.minLon, splitValue,
+ cell.maxLon, cell.maxLat,
+ cell.splitCount+1);
+ if (VERBOSE) {
+ log.println(" split cells:\n " + cell1 + "\n " + cell2);
+ }
+ queue.add(cell1);
+ queue.add(cell2);
+ }
+ }
+ }
+ }
+
+ /** Tests consistency of GeoUtils.rectWithinCircle, .rectCrossesCircle, .rectWithin and SloppyMath.haversine distance check */
+ public void testGeoRelations() throws Exception {
+
+ int numDocs = atLeast(1000);
+
+ boolean useSmallRanges = random().nextBoolean();
+
+ if (VERBOSE) {
+ System.out.println("TEST: " + numDocs + " docs useSmallRanges=" + useSmallRanges);
+ }
+
+ double[] docLons = new double[numDocs];
+ double[] docLats = new double[numDocs];
+ for(int docID=0;docID<numDocs;docID++) {
+ docLons[docID] = randomLon(useSmallRanges);
+ docLats[docID] = randomLat(useSmallRanges);
+ if (VERBOSE) {
+ System.out.println(" doc=" + docID + ": lon=" + docLons[docID] + " lat=" + docLats[docID]);
+ }
+ }
+
+ int iters = atLeast(10);
+
+ iters = atLeast(50);
+
+ for(int iter=0;iter<iters;iter++) {
+
+ Cell.nextCellID = 0;
+
+ double centerLon = randomLon(useSmallRanges);
+ double centerLat = randomLat(useSmallRanges);
+
+ // So the circle covers at most 50% of the earth's surface:
+
+ double radiusMeters;
+
+ // TODO: GeoUtils APIs are still buggy for large distances:
+ if (true || useSmallRanges) {
+ // Approx 3 degrees lon at the equator:
+ radiusMeters = random().nextDouble() * 333000;
+ } else {
+ radiusMeters = random().nextDouble() * GeoProjectionUtils.SEMIMAJOR_AXIS * Math.PI / 2.0;
+ }
+
+ StringWriter sw = new StringWriter();
+ PrintWriter log = new PrintWriter(sw, true);
+
+ if (VERBOSE) {
+ log.println("\nTEST: iter=" + iter + " radiusMeters=" + radiusMeters + " centerLon=" + centerLon + " centerLat=" + centerLat);
+ }
+
+ GeoRect bbox = GeoUtils.circleToBBox(centerLon, centerLat, radiusMeters);
+
+ Set<Integer> hits = new HashSet<>();
+
+ if (bbox.maxLon < bbox.minLon) {
+ // Crosses dateline
+ log.println(" circle crosses dateline; first left query");
+ double unwrappedLon = centerLon;
+ if (unwrappedLon > bbox.maxLon) {
+ // unwrap left
+ unwrappedLon += -360.0D;
+ }
+ findMatches(hits, log,
+ new Cell(null,
+ -180, bbox.minLat,
+ bbox.maxLon, bbox.maxLat,
+ 0),
+ unwrappedLon, centerLat, radiusMeters, docLons, docLats);
+ log.println(" circle crosses dateline; now right query");
+ if (unwrappedLon < bbox.maxLon) {
+ // unwrap right
+ unwrappedLon += 360.0D;
+ }
+ findMatches(hits, log,
+ new Cell(null,
+ bbox.minLon, bbox.minLat,
+ 180, bbox.maxLat,
+ 0),
+ unwrappedLon, centerLat, radiusMeters, docLons, docLats);
+ } else {
+ // Start with the root cell that fully contains the shape:
+ findMatches(hits, log,
+ new Cell(null,
+ bbox.minLon, bbox.minLat,
+ bbox.maxLon, bbox.maxLat,
+ 0),
+ centerLon, centerLat, radiusMeters,
+ docLons, docLats);
+ }
+
+ if (VERBOSE) {
+ log.println(" " + hits.size() + " hits");
+ }
+
+ int failCount = 0;
+
+ // Done matching, now verify:
+ for(int docID=0;docID<numDocs;docID++) {
+ double distanceMeters = GeoDistanceUtils.haversin(centerLat, centerLon, docLats[docID], docLons[docID]);
+ boolean expected = distanceMeters <= radiusMeters;
+
+ boolean actual = hits.contains(docID);
+ if (actual != expected) {
+ if (actual) {
+ log.println("doc=" + docID + " matched but should not on iteration " + iter);
+ } else {
+ log.println("doc=" + docID + " did not match but should on iteration " + iter);
+ }
+ log.println(" lon=" + docLons[docID] + " lat=" + docLats[docID] + " distanceMeters=" + distanceMeters + " vs radiusMeters=" + radiusMeters);
+ failCount++;
+ }
+ }
+
+ if (failCount != 0) {
+ System.out.print(sw.toString());
+ fail(failCount + " incorrect hits (see above)");
+ }
+ }
}
}
Modified: lucene/dev/branches/lucene6835/lucene/spatial/ivy.xml
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene6835/lucene/spatial/ivy.xml?rev=1721134&r1=1721133&r2=1721134&view=diff
==============================================================================
--- lucene/dev/branches/lucene6835/lucene/spatial/ivy.xml (original)
+++ lucene/dev/branches/lucene6835/lucene/spatial/ivy.xml Mon Dec 21 11:39:57 2015
@@ -23,8 +23,9 @@
<conf name="test" transitive="false"/>
</configurations>
<dependencies>
- <dependency org="com.spatial4j" name="spatial4j" rev="${/com.spatial4j/spatial4j}" conf="compile">
- <artifact name="spatial4j" ext="jar" />
+ <dependency org="com.spatial4j" name="spatial4j" rev="${/com.spatial4j/spatial4j}" conf="compile"/>
+
+ <dependency org="com.spatial4j" name="spatial4j" rev="${/com.spatial4j/spatial4j}" conf="test">
<artifact name="spatial4j" type="test" ext="jar" maven:classifier="tests" />
</dependency>