You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by nk...@apache.org on 2016/02/05 18:11:13 UTC
[32/34] lucene-solr git commit: LUCENE-7015: refactors lucene-spatial
module to a new lucene-spatial-extras module,
and refactors sandbox GeoPointField and queries to lucene-spatial module
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5b028349/lucene/sandbox/src/java/org/apache/lucene/util/GeoRelationUtils.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/util/GeoRelationUtils.java b/lucene/sandbox/src/java/org/apache/lucene/util/GeoRelationUtils.java
deleted file mode 100644
index 092b949..0000000
--- a/lucene/sandbox/src/java/org/apache/lucene/util/GeoRelationUtils.java
+++ /dev/null
@@ -1,497 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.lucene.util;
-
-/**
- * Reusable geo-relation utility methods
- */
-public class GeoRelationUtils {
-
- /**
- * Determine if a bbox (defined by minLon, minLat, maxLon, maxLat) contains the provided point (defined by lon, lat)
- * NOTE: this is a basic method that does not handle dateline or pole crossing. Unwrapping must be done before
- * calling this method.
- */
- public static boolean pointInRectPrecise(final double lon, final double lat, final double minLon,
- final double minLat, final double maxLon, final double maxLat) {
- return lon >= minLon && lon <= maxLon && lat >= minLat && lat <= maxLat;
- }
-
- /**
- * 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;
- }
-
- /////////////////////////
- // Rectangle relations
- /////////////////////////
-
- 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 the first (a) rectangle is wholly within another (b) 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) );
- }
-
- /////////////////////////
- // Polygon relations
- /////////////////////////
-
- /**
- * Convenience method for accurately computing whether a rectangle crosses a poly
- */
- public static boolean rectCrossesPolyPrecise(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;
- }
- return rectCrossesPoly(rMinX, rMinY, rMaxX, rMaxY, shapeX, shapeY);
- }
-
- /**
- * Compute whether a rectangle crosses a shape. (touching not allowed) Includes a flag for approximating the
- * relation.
- */
- public static boolean rectCrossesPolyApprox(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 int polyLength = shapeX.length-1;
- for (short p=0; p<polyLength; ++p) {
- if (lineCrossesRect(shapeX[p], shapeY[p], shapeX[p+1], shapeY[p+1], rMinX, rMinY, rMaxX, rMaxY) == true) {
- return true;
- }
- }
- return false;
- }
-
- /**
- * Accurately compute (within restrictions of cartesian decimal degrees) whether a rectangle crosses a polygon
- */
- private static boolean rectCrossesPoly(final double rMinX, final double rMinY, final double rMaxX,
- final double rMaxY, final double[] shapeX, final double[] shapeY) {
- 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]) - GeoUtils.TOLERANCE;
- x01 = StrictMath.max(bbox[b][0], bbox[b+1][0]) + GeoUtils.TOLERANCE;
- y00 = StrictMath.min(bbox[b][1], bbox[b+1][1]) - GeoUtils.TOLERANCE;
- y01 = StrictMath.max(bbox[b][1], bbox[b+1][1]) + GeoUtils.TOLERANCE;
- x10 = StrictMath.min(shapeX[p], shapeX[p+1]) - GeoUtils.TOLERANCE;
- x11 = StrictMath.max(shapeX[p], shapeX[p+1]) + GeoUtils.TOLERANCE;
- y10 = StrictMath.min(shapeY[p], shapeY[p+1]) - GeoUtils.TOLERANCE;
- y11 = StrictMath.max(shapeY[p], shapeY[p+1]) + GeoUtils.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;
- }
-
- private static boolean lineCrossesRect(double aX1, double aY1, double aX2, double aY2,
- final double rMinX, final double rMinY, final double rMaxX, final double rMaxY) {
- // short-circuit: if one point inside rect, other outside
- if (pointInRectPrecise(aX1, aY1, rMinX, rMinY, rMaxX, rMaxY) ?
- !pointInRectPrecise(aX2, aY2, rMinX, rMinY, rMaxX, rMaxY) : pointInRectPrecise(aX2, aY2, rMinX, rMinY, rMaxX, rMaxY)) {
- return true;
- }
-
- return lineCrossesLine(aX1, aY1, aX2, aY2, rMinX, rMinY, rMaxX, rMaxY)
- || lineCrossesLine(aX1, aY1, aX2, aY2, rMaxX, rMinY, rMinX, rMaxY);
- }
-
- private static boolean lineCrossesLine(final double aX1, final double aY1, final double aX2, final double aY2,
- final double bX1, final double bY1, final double bX2, final double bY2) {
- // determine if three points are ccw (right-hand rule) by computing the determinate
- final double aX2X1d = aX2 - aX1;
- final double aY2Y1d = aY2 - aY1;
- final double bX2X1d = bX2 - bX1;
- final double bY2Y1d = bY2 - bY1;
-
- final double t1B = aX2X1d * (bY2 - aY1) - aY2Y1d * (bX2 - aX1);
- final double test1 = (aX2X1d * (bY1 - aY1) - aY2Y1d * (bX1 - aX1)) * t1B;
- final double t2B = bX2X1d * (aY2 - bY1) - bY2Y1d * (aX2 - bX1);
- final double test2 = (bX2X1d * (aY1 - bY1) - bY2Y1d * (aX1 - bX1)) * t2B;
-
- if (test1 < 0 && test2 < 0) {
- return true;
- }
-
- if (test1 == 0 || test2 == 0) {
- // vertically collinear
- if (aX1 == aX2 || bX1 == bX2) {
- final double minAy = Math.min(aY1, aY2);
- final double maxAy = Math.max(aY1, aY2);
- final double minBy = Math.min(bY1, bY2);
- final double maxBy = Math.max(bY1, bY2);
-
- return !(minBy >= maxAy || maxBy <= minAy);
- }
- // horizontally collinear
- final double minAx = Math.min(aX1, aX2);
- final double maxAx = Math.max(aX1, aX2);
- final double minBx = Math.min(bX1, bX2);
- final double maxBx = Math.max(bX1, bX2);
-
- return !(minBx >= maxAx || maxBx <= minAx);
- }
- return false;
- }
-
- public static boolean rectWithinPolyPrecise(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 !(rectCrossesPolyPrecise(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));
- }
-
- /**
- * Computes whether a rectangle is within a given polygon (shared boundaries allowed)
- */
- public static boolean rectWithinPolyApprox(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) {
- // approximation: check if rectangle crosses poly (to handle concave/pacman polys), then check one of the corners
- // are contained
-
- // short-cut: if bounding boxes cross, rect is not within
- if (rectCrosses(rMinX, rMinY, rMaxX, rMaxY, sMinX, sMinY, sMaxX, sMaxY) == true) {
- return false;
- }
-
- return !(rectCrossesPolyApprox(rMinX, rMinY, rMaxX, rMaxY, shapeX, shapeY, sMinX, sMinY, sMaxX, sMaxY)
- || !pointInPolygon(shapeX, shapeY, rMinY, rMinX));
- }
-
- /////////////////////////
- // Circle relations
- /////////////////////////
-
- private static boolean rectAnyCornersInCircle(final double rMinX, final double rMinY, final double rMaxX,
- final double rMaxY, final double centerLon, final double centerLat,
- final double radiusMeters, final boolean approx) {
- if (approx == true) {
- return rectAnyCornersInCircleSloppy(rMinX, rMinY, rMaxX, rMaxY, centerLon, centerLat, radiusMeters);
- }
- double w = Math.abs(rMaxX - rMinX);
- if (w <= 90.0) {
- return GeoDistanceUtils.haversin(centerLat, centerLon, rMinY, rMinX) <= radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMaxY, rMinX) <= radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMaxY, rMaxX) <= radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMinY, rMaxX) <= radiusMeters;
- }
- // partition
- w /= 4;
- final double p1 = rMinX + w;
- final double p2 = p1 + w;
- final double p3 = p2 + w;
-
- return GeoDistanceUtils.haversin(centerLat, centerLon, rMinY, rMinX) <= radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMaxY, rMinX) <= radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMaxY, p1) <= radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMinY, p1) <= radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMinY, p2) <= radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMaxY, p2) <= radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMaxY, p3) <= radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMinY, p3) <= radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMaxY, rMaxX) <= radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMinY, rMaxX) <= radiusMeters;
- }
-
- private static boolean rectAnyCornersInCircleSloppy(final double rMinX, final double rMinY, final double rMaxX, final double rMaxY,
- final double centerLon, final double centerLat, final double radiusMeters) {
- return SloppyMath.haversin(centerLat, centerLon, rMinY, rMinX)*1000.0 <= radiusMeters
- || SloppyMath.haversin(centerLat, centerLon, rMaxY, rMinX)*1000.0 <= radiusMeters
- || SloppyMath.haversin(centerLat, centerLon, rMaxY, rMaxX)*1000.0 <= radiusMeters
- || SloppyMath.haversin(centerLat, centerLon, rMinY, rMaxX)*1000.0 <= radiusMeters;
- }
-
- /**
- * Compute whether any of the 4 corners of the rectangle (defined by min/max X/Y) are outside the circle (defined
- * by centerLon, centerLat, radiusMeters)
- *
- * Note: exotic rectangles at the poles (e.g., those whose lon/lat distance ratios greatly deviate from 1) can not
- * be determined by using distance alone. For this reason the approx flag may be set to false, in which case the
- * space will be further divided to more accurately compute whether the rectangle crosses the circle
- */
- private static boolean rectAnyCornersOutsideCircle(final double rMinX, final double rMinY, final double rMaxX,
- final double rMaxY, final double centerLon, final double centerLat,
- final double radiusMeters, final boolean approx) {
- if (approx == true) {
- return rectAnyCornersOutsideCircleSloppy(rMinX, rMinY, rMaxX, rMaxY, centerLon, centerLat, radiusMeters);
- }
- // if span is less than 70 degrees we can approximate using distance alone
- if (Math.abs(rMaxX - rMinX) <= 70.0) {
- return GeoDistanceUtils.haversin(centerLat, centerLon, rMinY, rMinX) > radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMaxY, rMinX) > radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMaxY, rMaxX) > radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMinY, rMaxX) > radiusMeters;
- }
- return rectCrossesOblateCircle(centerLon, centerLat, radiusMeters, rMinX, rMinY, rMaxX, rMaxY);
- }
-
- /**
- * Compute whether the rectangle (defined by min/max Lon/Lat) crosses a potentially oblate circle
- *
- * TODO benchmark for replacing existing rectCrossesCircle.
- */
- public static boolean rectCrossesOblateCircle(double centerLon, double centerLat, double radiusMeters, double rMinLon, double rMinLat, double rMaxLon, double rMaxLat) {
- double w = Math.abs(rMaxLon - rMinLon);
- final int segs = (int)Math.ceil(w / 45.0);
- w /= segs;
- short i = 1;
- double p1 = rMinLon;
- double maxLon, midLon;
- double[] pt = new double[2];
-
- do {
- maxLon = (i == segs) ? rMaxLon : p1 + w;
-
- final double d1, d2;
- // short-circuit if we find a corner outside the circle
- if ( (d1 = GeoDistanceUtils.haversin(centerLat, centerLon, rMinLat, p1)) > radiusMeters
- || (d2 = GeoDistanceUtils.haversin(centerLat, centerLon, rMinLat, maxLon)) > radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMaxLat, p1) > radiusMeters
- || GeoDistanceUtils.haversin(centerLat, centerLon, rMaxLat, maxLon) > radiusMeters) {
- return true;
- }
-
- // else we treat as an oblate circle by slicing the longitude space and checking the azimuthal range
- // OPTIMIZATION: this is only executed for latitude values "closeTo" the poles (e.g., 88.0 > lat < -88.0)
- if ( (rMaxLat > 88.0 || rMinLat < -88.0)
- && (pt = GeoProjectionUtils.pointFromLonLatBearingGreatCircle(p1, rMinLat,
- GeoProjectionUtils.bearingGreatCircle(p1, rMinLat, p1, rMaxLat), radiusMeters - d1, pt))[1] < rMinLat || pt[1] < rMaxLat
- || (pt = GeoProjectionUtils.pointFromLonLatBearingGreatCircle(maxLon, rMinLat,
- GeoProjectionUtils.bearingGreatCircle(maxLon, rMinLat, maxLon, rMaxLat), radiusMeters - d2, pt))[1] < rMinLat || pt[1] < rMaxLat
- || (pt = GeoProjectionUtils.pointFromLonLatBearingGreatCircle(maxLon, rMinLat,
- GeoProjectionUtils.bearingGreatCircle(maxLon, rMinLat, (midLon = p1 + 0.5*(maxLon - p1)), rMaxLat),
- radiusMeters - GeoDistanceUtils.haversin(centerLat, centerLon, rMinLat, midLon), pt))[1] < rMinLat
- || pt[1] < rMaxLat == false ) {
- return true;
- }
- p1 += w;
- } while (++i <= segs);
- return false;
- }
-
- private static boolean rectAnyCornersOutsideCircleSloppy(final double rMinX, final double rMinY, final double rMaxX, final double rMaxY,
- final double centerLon, final double centerLat, final double radiusMeters) {
- return SloppyMath.haversin(centerLat, centerLon, rMinY, rMinX)*1000.0 > radiusMeters
- || SloppyMath.haversin(centerLat, centerLon, rMaxY, rMinX)*1000.0 > radiusMeters
- || SloppyMath.haversin(centerLat, centerLon, rMaxY, rMaxX)*1000.0 > radiusMeters
- || SloppyMath.haversin(centerLat, centerLon, rMinY, rMaxX)*1000.0 > radiusMeters;
- }
-
- public static boolean rectWithinCircle(final double rMinX, final double rMinY, final double rMaxX, final double rMaxY,
- final double centerLon, final double centerLat, final double radiusMeters) {
- return rectWithinCircle(rMinX, rMinY, rMaxX, rMaxY, centerLon, centerLat, radiusMeters, false);
- }
-
- public static boolean rectWithinCircle(final double rMinX, final double rMinY, final double rMaxX, final double rMaxY,
- final double centerLon, final double centerLat, final double radiusMeters,
- final boolean approx) {
- return rectAnyCornersOutsideCircle(rMinX, rMinY, rMaxX, rMaxY, centerLon, centerLat, radiusMeters, approx) == false;
- }
-
- /**
- * Determine if a bbox (defined by minLon, minLat, maxLon, maxLat) contains the provided point (defined by lon, lat)
- * NOTE: this is basic method that does not handle dateline or pole crossing. Unwrapping must be done before
- * calling this method.
- */
- public static boolean rectCrossesCircle(final double rMinX, final double rMinY, final double rMaxX, final double rMaxY,
- final double centerLon, final double centerLat, final double radiusMeters) {
- return rectCrossesCircle(rMinX, rMinY, rMaxX, rMaxY, centerLon, centerLat, radiusMeters, false);
- }
-
- public static boolean rectCrossesCircle(final double rMinX, final double rMinY, final double rMaxX, final double rMaxY,
- final double centerLon, final double centerLat, final double radiusMeters,
- final boolean approx) {
- if (approx == true) {
- return rectAnyCornersInCircle(rMinX, rMinY, rMaxX, rMaxY, centerLon, centerLat, radiusMeters, approx)
- || isClosestPointOnRectWithinRange(rMinX, rMinY, rMaxX, rMaxY, centerLon, centerLat, radiusMeters, approx);
- }
-
- return (rectAnyCornersInCircle(rMinX, rMinY, rMaxX, rMaxY, centerLon, centerLat, radiusMeters, approx) &&
- rectAnyCornersOutsideCircle(rMinX, rMinY, rMaxX, rMaxY, centerLon, centerLat, radiusMeters, approx))
- || isClosestPointOnRectWithinRange(rMinX, rMinY, rMaxX, rMaxY, centerLon, centerLat, radiusMeters, approx);
- }
-
- private static boolean isClosestPointOnRectWithinRange(final double rMinX, final double rMinY, final double rMaxX, final double rMaxY,
- final double centerLon, final double centerLat, final double radiusMeters,
- final boolean approx) {
- double[] closestPt = {0, 0};
- GeoDistanceUtils.closestPointOnBBox(rMinX, rMinY, rMaxX, rMaxY, centerLon, centerLat, closestPt);
- boolean haverShortCut = GeoDistanceUtils.haversin(centerLat, centerLon, closestPt[1], closestPt[0]) <= radiusMeters;
- if (approx == true || haverShortCut == true) {
- return haverShortCut;
- }
- double lon1 = rMinX;
- double lon2 = rMaxX;
- double lat1 = rMinY;
- double lat2 = rMaxY;
- if (closestPt[0] == rMinX || closestPt[0] == rMaxX) {
- lon1 = closestPt[0];
- lon2 = lon1;
- } else if (closestPt[1] == rMinY || closestPt[1] == rMaxY) {
- lat1 = closestPt[1];
- lat2 = lat1;
- }
-
- return lineCrossesSphere(lon1, lat1, 0, lon2, lat2, 0, centerLon, centerLat, 0, radiusMeters);
- }
-
- /**
- * 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 radiusMeters search sphere radius (in meters)
- * @return whether the provided line segment is a secant of the
- */
- private static boolean lineCrossesSphere(double lon1, double lat1, double alt1, double lon2,
- double lat2, double alt2, double centerLon, double centerLat,
- double centerAlt, double radiusMeters) {
- // 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);
-
- // convert radius from arc radius to cartesian radius
- double[] oneEighty = GeoProjectionUtils.pointFromLonLatBearingGreatCircle(centerLon, centerLat, 180.0d, radiusMeters, new double[3]);
- GeoProjectionUtils.llaToECF(oneEighty[0], oneEighty[1], 0, oneEighty);
-
- radiusMeters = GeoDistanceUtils.linearDistance(oneEighty, cntr);// Math.sqrt(oneEighty[0]*cntr[0] + oneEighty[1]*cntr[1] + oneEighty[2]*cntr[2]);
-
- 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) - (radiusMeters*radiusMeters);
-
- double discrim = (b*b)-(4*a*c);
- if (discrim < 0) {
- return false;
- }
-
- discrim = StrictMath.sqrt(discrim);
- final double a2 = 2*a;
- final double t1 = (-b - discrim)/a2;
- final double t2 = (-b + discrim)/a2;
-
- if ( (t1 < 0 || t1 > 1) ) {
- return !(t2 < 0 || t2 > 1);
- }
-
- return true;
- }
-}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5b028349/lucene/sandbox/src/java/org/apache/lucene/util/GeoUtils.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/util/GeoUtils.java b/lucene/sandbox/src/java/org/apache/lucene/util/GeoUtils.java
deleted file mode 100644
index a2d0fd1..0000000
--- a/lucene/sandbox/src/java/org/apache/lucene/util/GeoUtils.java
+++ /dev/null
@@ -1,237 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-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 {
- 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. */
- public static final double MIN_LON_INCL = -180.0D;
-
- /** Maximum longitude value. */
- public static final double MAX_LON_INCL = 180.0D;
-
- /** Minimum latitude value. */
- public static final double MIN_LAT_INCL = -90.0D;
-
- /** Maximum latitude value. */
- public static final double MAX_LAT_INCL = 90.0D;
-
- // No instance:
- private GeoUtils() {
- }
-
- public static final Long mortonHash(final double lon, final double lat) {
- return BitUtil.interleave(scaleLon(lon), scaleLat(lat));
- }
-
- public static final double mortonUnhashLon(final long hash) {
- return unscaleLon(BitUtil.deinterleave(hash));
- }
-
- public static final double mortonUnhashLat(final long hash) {
- return unscaleLat(BitUtil.deinterleave(hash >>> 1));
- }
-
- private static final long scaleLon(final double val) {
- return (long) ((val-MIN_LON_INCL) * LON_SCALE);
- }
-
- private static final long scaleLat(final double val) {
- return (long) ((val-MIN_LAT_INCL) * LAT_SCALE);
- }
-
- private static final double unscaleLon(final long val) {
- return (val / LON_SCALE) + MIN_LON_INCL;
- }
-
- 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 delta = v1-v2;
- return Math.abs(delta) <= TOLERANCE ? 0 : delta;
- }
-
- /**
- * Puts longitude in range of -180 to +180.
- */
- public static double normalizeLon(double lon_deg) {
- if (lon_deg >= -180 && lon_deg <= 180) {
- return lon_deg; //common case, and avoids slight double precision shifting
- }
- double off = (lon_deg + 180) % 360;
- if (off < 0) {
- return 180 + off;
- } else if (off == 0 && lon_deg > 0) {
- return 180;
- } else {
- return -180 + off;
- }
- }
-
- /**
- * Puts latitude in range of -90 to 90.
- */
- public static double normalizeLat(double lat_deg) {
- if (lat_deg >= -90 && lat_deg <= 90) {
- return lat_deg; //common case, and avoids slight double precision shifting
- }
- double off = Math.abs((lat_deg + 90) % 360);
- return (off <= 180 ? off : 360-off) - 90;
- }
-
- public static String geoTermToString(long term) {
- StringBuilder s = new StringBuilder(64);
- final int numberOfLeadingZeros = Long.numberOfLeadingZeros(term);
- for (int i = 0; i < numberOfLeadingZeros; i++) {
- s.append('0');
- }
- if (term != 0) {
- s.append(Long.toBinaryString(term));
- }
- return s.toString();
- }
-
- /**
- * 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 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 radiusMeters) {
- double angle;
- // a little under-sampling (to limit the number of polygonal points): using archimedes estimation of pi
- final int sides = 25;
- ArrayList<double[]> geometry = new ArrayList();
- double[] lons = new double[sides];
- double[] lats = new double[sides];
-
- double[] pt = new double[2];
- final int sidesLen = sides-1;
- for (int i=0; i<sidesLen; ++i) {
- angle = (i*360/sides);
- pt = GeoProjectionUtils.pointFromLonLatBearingGreatCircle(lon, lat, angle, radiusMeters, pt);
- lons[i] = pt[0];
- lats[i] = pt[1];
- }
- // close the poly
- lons[sidesLen] = lons[0];
- lats[sidesLen] = lats[0];
- geometry.add(lons);
- geometry.add(lats);
-
- return geometry;
- }
-
- /**
- * Compute Bounding Box for a circle using WGS-84 parameters
- */
- 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;
- }
-
- return new GeoRect(TO_DEGREES * minLon, TO_DEGREES * maxLon, TO_DEGREES * minLat, TO_DEGREES * maxLat);
- }
-
- /**
- * Compute Bounding Box for a polygon using WGS-84 parameters
- */
- public static GeoRect polyToBBox(double[] polyLons, double[] polyLats) {
- if (polyLons.length != polyLats.length) {
- throw new IllegalArgumentException("polyLons and polyLats must be equal length");
- }
-
- double minLon = Double.POSITIVE_INFINITY;
- double maxLon = Double.NEGATIVE_INFINITY;
- double minLat = Double.POSITIVE_INFINITY;
- double maxLat = Double.NEGATIVE_INFINITY;
-
- 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);
- }
- // expand bounding box by TOLERANCE factor to handle round-off error
- return new GeoRect(Math.max(minLon - TOLERANCE, MIN_LON_INCL), Math.min(maxLon + TOLERANCE, MAX_LON_INCL),
- Math.max(minLat - TOLERANCE, MIN_LAT_INCL), Math.min(maxLat + TOLERANCE, MAX_LAT_INCL));
- }
-
- /**
- * 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;
- }
-}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5b028349/lucene/sandbox/src/java/org/apache/lucene/util/package.html
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/util/package.html b/lucene/sandbox/src/java/org/apache/lucene/util/package.html
deleted file mode 100644
index 9a8856c..0000000
--- a/lucene/sandbox/src/java/org/apache/lucene/util/package.html
+++ /dev/null
@@ -1,28 +0,0 @@
-<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
-<!--
- Licensed to the Apache Software Foundation (ASF) under one or more
- contributor license agreements. See the NOTICE file distributed with
- this work for additional information regarding copyright ownership.
- The ASF licenses this file to You under the Apache License, Version 2.0
- (the "License"); you may not use this file except in compliance with
- the License. You may obtain a copy of the License at
-
- http://www.apache.org/licenses/LICENSE-2.0
-
- Unless required by applicable law or agreed to in writing, software
- distributed under the License is distributed on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- See the License for the specific language governing permissions and
- limitations under the License.
--->
-
-<!-- not a package-info.java, because we already defined this package in core/ -->
-
-<html>
-<head>
- <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
-</head>
-<body>
-This package contains utility APIs, currently for geospatial searching.
-</body>
-</html>
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5b028349/lucene/sandbox/src/test/org/apache/lucene/search/TestGeoPointQuery.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/search/TestGeoPointQuery.java b/lucene/sandbox/src/test/org/apache/lucene/search/TestGeoPointQuery.java
deleted file mode 100644
index a91cbd6..0000000
--- a/lucene/sandbox/src/test/org/apache/lucene/search/TestGeoPointQuery.java
+++ /dev/null
@@ -1,386 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.lucene.search;
-
-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.StringField;
-import org.apache.lucene.index.IndexReader;
-import org.apache.lucene.index.RandomIndexWriter;
-import org.apache.lucene.store.Directory;
-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.SloppyMath;
-import org.apache.lucene.util.TestUtil;
-import org.junit.AfterClass;
-import org.junit.BeforeClass;
-
-import static org.apache.lucene.util.GeoDistanceUtils.DISTANCE_PCT_ERR;
-
-/**
- * Unit testing for basic GeoPoint query logic
- *
- * @lucene.experimental
- */
-
-public class TestGeoPointQuery extends BaseGeoPointTestCase {
-
- private static Directory directory = null;
- private static IndexReader reader = null;
- private static IndexSearcher searcher = null;
-
- @Override
- protected boolean forceSmall() {
- return false;
- }
-
- @Override
- protected void addPointToDoc(String field, Document doc, double lat, double lon) {
- doc.add(new GeoPointField(field, lon, lat, Field.Store.NO));
- }
-
- @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 {
- directory = newDirectory();
-
- RandomIndexWriter writer = new RandomIndexWriter(random(), directory,
- newIndexWriterConfig(new MockAnalyzer(random()))
- .setMaxBufferedDocs(TestUtil.nextInt(random(), 100, 1000))
- .setMergePolicy(newLogMergePolicy()));
-
- // create some simple geo points
- final FieldType storedPoint = new FieldType(GeoPointField.TYPE_STORED);
- // this is a simple systematic test
- GeoPointField[] pts = new GeoPointField[] {
- new GeoPointField(FIELD_NAME, -96.774, 32.763420, storedPoint),
- new GeoPointField(FIELD_NAME, -96.7759895324707, 32.7559529921407, storedPoint),
- new GeoPointField(FIELD_NAME, -96.77701950073242, 32.77866942010977, storedPoint),
- new GeoPointField(FIELD_NAME, -96.7706036567688, 32.7756745755423, storedPoint),
- new GeoPointField(FIELD_NAME, -139.73458170890808, 27.703618681345585, storedPoint),
- 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, -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, -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),
- new GeoPointField(FIELD_NAME, -179.5, -44.5, storedPoint)};
-
- for (GeoPointField p : pts) {
- Document doc = new Document();
- doc.add(p);
- writer.addDocument(doc);
- }
-
- // add explicit multi-valued docs
- for (int i=0; i<pts.length; i+=2) {
- Document doc = new Document();
- doc.add(pts[i]);
- doc.add(pts[i+1]);
- 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();
- }
-
- @AfterClass
- public static void afterClass() throws Exception {
- searcher = null;
- reader.close();
- reader = null;
- directory.close();
- directory = null;
- }
-
- private TopDocs bboxQuery(double minLon, double minLat, double maxLon, double maxLat, int limit) throws Exception {
- GeoPointInBBoxQuery q = new GeoPointInBBoxQuery(FIELD_NAME, minLon, minLat, maxLon, maxLat);
- return searcher.search(q, limit);
- }
-
- private TopDocs polygonQuery(double[] lon, double[] lat, int limit) throws Exception {
- GeoPointInPolygonQuery q = new GeoPointInPolygonQuery(FIELD_NAME, lon, lat);
- return searcher.search(q, limit);
- }
-
- private TopDocs geoDistanceQuery(double lon, double lat, double radius, int limit) throws Exception {
- GeoPointDistanceQuery q = new GeoPointDistanceQuery(FIELD_NAME, lon, lat, radius);
- return searcher.search(q, limit);
- }
-
- @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.pointInRectPrecise(pointLon, pointLat, rect.minLon, rect.minLat, rect.maxLon, rect.maxLat);
- } else {
- // Rect crosses dateline:
- return GeoRelationUtils.pointInRectPrecise(pointLon, pointLat, -180.0, rect.minLat, rect.maxLon, rect.maxLat)
- || GeoRelationUtils.pointInRectPrecise(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);
- }
-
- 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},
- new double[]{33.073130, 32.9942669, 32.938386, 33.0374494,
- 33.1369762, 33.1162747, 33.073130, 33.073130}, 5);
- assertEquals("GeoPolygonQuery failed", 2, td.totalHits);
- }
-
- public void testPacManPolyQuery() throws Exception {
- // pacman
- double[] px = {0, 10, 10, 0, -8, -10, -8, 0, 10, 10, 0};
- double[] py = {0, 5, 9, 10, 9, 0, -9, -10, -9, -5, 0};
-
- // shape bbox
- double xMinA = -10;
- double xMaxA = 10;
- double yMinA = -10;
- double yMaxA = 10;
-
- // candidate crosses cell
- double xMin = 2;//-5;
- double xMax = 11;//0.000001;
- double yMin = -1;//0;
- double yMax = 1;//5;
-
- // test cell crossing poly
- assertTrue(GeoRelationUtils.rectCrossesPolyApprox(xMin, yMin, xMax, yMax, px, py, xMinA, yMinA, xMaxA, yMaxA));
- assertFalse(GeoRelationUtils.rectCrossesPolyApprox(-5, 0, 0.000001, 5, px, py, xMin, yMin, xMax, yMax));
- assertTrue(GeoRelationUtils.rectWithinPolyApprox(-5, 0, -2, 5, px, py, xMin, yMin, xMax, yMax));
- }
-
- public void testBBoxCrossDateline() throws Exception {
- TopDocs td = bboxQuery(179.0, -45.0, -179.0, -44.0, 20);
- assertEquals("BBoxCrossDateline query failed", 2, td.totalHits);
- }
-
- public void testWholeMap() throws Exception {
- 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);
- td = polygonQuery(new double[] {GeoUtils.MIN_LON_INCL, GeoUtils.MIN_LON_INCL, GeoUtils.MAX_LON_INCL, GeoUtils.MAX_LON_INCL, GeoUtils.MIN_LON_INCL},
- new double[] {GeoUtils.MIN_LAT_INCL, GeoUtils.MAX_LAT_INCL, GeoUtils.MAX_LAT_INCL, GeoUtils.MIN_LAT_INCL, GeoUtils.MIN_LAT_INCL}, 20);
- assertEquals("testWholeMap failed", 24, td.totalHits);
- }
-
- public void smallTest() throws Exception {
- TopDocs td = geoDistanceQuery(-73.998776, 40.720611, 1, 20);
- assertEquals("smallTest failed", 2, td.totalHits);
- }
-
- public void testInvalidBBox() throws Exception {
- try {
- bboxQuery(179.0, -92.0, 181.0, -91.0, 20);
- } catch(Exception e) {
- return;
- }
- throw new Exception("GeoBoundingBox should not accept invalid lat/lon");
- }
-
- public void testGeoDistanceQuery() throws Exception {
- TopDocs td = geoDistanceQuery(-96.4538113027811, 32.94823588839368, 6000, 20);
- assertEquals("GeoDistanceQuery failed", 2, td.totalHits);
- }
-
- /** 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
- */
- public void testGeoDistanceQueryHuge() throws Exception {
- TopDocs td = geoDistanceQuery(-96.4538113027811, 32.94823588839368, 6000000, 20);
- assertEquals("GeoDistanceQuery failed", 16, td.totalHits);
- }
-
- public void testGeoDistanceQueryCrossDateline() throws Exception {
- TopDocs td = geoDistanceQuery(-179.9538113027811, 32.94823588839368, 120000, 20);
- assertEquals("GeoDistanceQuery failed", 3, td.totalHits);
- }
-
- public void testInvalidGeoDistanceQuery() throws Exception {
- try {
- geoDistanceQuery(181.0, 92.0, 120000, 20);
- } catch (Exception e) {
- return;
- }
- throw new Exception("GeoDistanceQuery should not accept invalid lat/lon as origin");
- }
-
- public void testMaxDistanceRangeQuery() throws Exception {
- TopDocs td = geoDistanceRangeQuery(0.0, 0.0, 10, 20000000, 20);
- assertEquals("GeoDistanceRangeQuery failed", 24, td.totalHits);
- }
-
- 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);
- }
-
- public void testEncodeDecode() throws Exception {
- int iters = atLeast(10000);
- boolean small = random().nextBoolean();
- for(int iter=0;iter<iters;iter++) {
- double lat = randomLat(small);
- double lon = randomLon(small);
-
- long enc = GeoUtils.mortonHash(lon, lat);
- double latEnc = GeoUtils.mortonUnhashLat(enc);
- double lonEnc = GeoUtils.mortonUnhashLon(enc);
-
- assertEquals("lat=" + lat + " latEnc=" + latEnc + " diff=" + (lat - latEnc), lat, latEnc, GeoUtils.TOLERANCE);
- assertEquals("lon=" + lon + " lonEnc=" + lonEnc + " diff=" + (lon - lonEnc), lon, lonEnc, GeoUtils.TOLERANCE);
- }
- }
-
- public void testScaleUnscaleIsStable() throws Exception {
- int iters = atLeast(1000);
- boolean small = random().nextBoolean();
- for(int iter=0;iter<iters;iter++) {
- double lat = randomLat(small);
- double lon = randomLon(small);
-
- long enc = GeoUtils.mortonHash(lon, lat);
- double latEnc = GeoUtils.mortonUnhashLat(enc);
- double lonEnc = GeoUtils.mortonUnhashLon(enc);
-
- long enc2 = GeoUtils.mortonHash(lon, lat);
- double latEnc2 = GeoUtils.mortonUnhashLat(enc2);
- double lonEnc2 = GeoUtils.mortonUnhashLon(enc2);
- assertEquals(latEnc, latEnc2, 0.0);
- assertEquals(lonEnc, lonEnc2, 0.0);
- }
- }
-}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5b028349/lucene/sandbox/src/test/org/apache/lucene/search/TestLatLonPointQueries.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/search/TestLatLonPointQueries.java b/lucene/sandbox/src/test/org/apache/lucene/search/TestLatLonPointQueries.java
index e898f1c..a1afb99 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/search/TestLatLonPointQueries.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/search/TestLatLonPointQueries.java
@@ -18,9 +18,9 @@ package org.apache.lucene.search;
import org.apache.lucene.document.LatLonPoint;
import org.apache.lucene.document.Document;
-import org.apache.lucene.util.BaseGeoPointTestCase;
-import org.apache.lucene.util.GeoDistanceUtils;
-import org.apache.lucene.util.GeoRect;
+import org.apache.lucene.spatial.util.BaseGeoPointTestCase;
+import org.apache.lucene.spatial.util.GeoBoundingBox;
+import org.apache.lucene.spatial.util.GeoDistanceUtils;
public class TestLatLonPointQueries extends BaseGeoPointTestCase {
// todo deconflict GeoPoint and BKD encoding methods and error tolerance
@@ -32,7 +32,7 @@ public class TestLatLonPointQueries extends BaseGeoPointTestCase {
}
@Override
- protected Query newRectQuery(String field, GeoRect rect) {
+ protected Query newRectQuery(String field, GeoBoundingBox rect) {
return new PointInRectQuery(field, rect.minLat, rect.maxLat, rect.minLon, rect.maxLon);
}
@@ -53,7 +53,7 @@ public class TestLatLonPointQueries extends BaseGeoPointTestCase {
}
@Override
- protected Boolean rectContainsPoint(GeoRect rect, double pointLat, double pointLon) {
+ protected Boolean rectContainsPoint(GeoBoundingBox rect, double pointLat, double pointLon) {
assert Double.isNaN(pointLat) == false;
@@ -94,7 +94,7 @@ public class TestLatLonPointQueries extends BaseGeoPointTestCase {
}
@Override
- protected Boolean polyRectContainsPoint(GeoRect rect, double pointLat, double pointLon) {
+ protected Boolean polyRectContainsPoint(GeoBoundingBox rect, double pointLat, double pointLon) {
// TODO write better random polygon tests
return rectContainsPoint(rect, pointLat, pointLon);
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5b028349/lucene/sandbox/src/test/org/apache/lucene/util/BaseGeoPointTestCase.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/util/BaseGeoPointTestCase.java b/lucene/sandbox/src/test/org/apache/lucene/util/BaseGeoPointTestCase.java
deleted file mode 100644
index 5a469db..0000000
--- a/lucene/sandbox/src/test/org/apache/lucene/util/BaseGeoPointTestCase.java
+++ /dev/null
@@ -1,764 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.lucene.util;
-
-import java.io.IOException;
-import java.text.DecimalFormat;
-import java.text.DecimalFormatSymbols;
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.HashSet;
-import java.util.List;
-import java.util.Locale;
-import java.util.Set;
-import java.util.concurrent.CountDownLatch;
-import java.util.concurrent.atomic.AtomicBoolean;
-
-import org.apache.lucene.document.Document;
-import org.apache.lucene.document.Field;
-import org.apache.lucene.document.NumericDocValuesField;
-import org.apache.lucene.index.DirectoryReader;
-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.search.IndexSearcher;
-import org.apache.lucene.search.Query;
-import org.apache.lucene.search.SimpleCollector;
-import org.apache.lucene.store.Directory;
-import org.apache.lucene.store.MockDirectoryWrapper;
-import org.junit.BeforeClass;
-
-// TODO: cutover TestGeoUtils too?
-
-public abstract class BaseGeoPointTestCase extends LuceneTestCase {
-
- protected static final String FIELD_NAME = "point";
-
- private static final double LON_SCALE = (0x1L<<GeoUtils.BITS)/360.0D;
- private static final double LAT_SCALE = (0x1L<<GeoUtils.BITS)/180.0D;
-
- private static double originLat;
- private static double originLon;
- private static double lonRange;
- private static double latRange;
-
- @BeforeClass
- public static void beforeClassBase() throws Exception {
- // Between 1.0 and 3.0:
- lonRange = 2 * (random().nextDouble() + 0.5);
- latRange = 2 * (random().nextDouble() + 0.5);
-
- originLon = GeoUtils.normalizeLon(GeoUtils.MIN_LON_INCL + lonRange + (GeoUtils.MAX_LON_INCL - GeoUtils.MIN_LON_INCL - 2 * lonRange) * random().nextDouble());
- originLat = GeoUtils.normalizeLat(GeoUtils.MIN_LAT_INCL + latRange + (GeoUtils.MAX_LAT_INCL - GeoUtils.MIN_LAT_INCL - 2 * latRange) * random().nextDouble());
- }
-
- /** Return true when testing on a non-small region may be too slow (GeoPoint*Query) */
- protected boolean forceSmall() {
- return false;
- }
-
- // A particularly tricky adversary for BKD tree:
- public void testSamePointManyTimes() throws Exception {
-
- // For GeoPointQuery, only run this test nightly:
- assumeTrue("GeoPoint*Query is too slow otherwise", TEST_NIGHTLY || forceSmall() == false);
-
- int numPoints = atLeast(1000);
- boolean small = random().nextBoolean();
-
- // Every doc has 2 points:
- double theLat = randomLat(small);
- double theLon = randomLon(small);
-
- double[] lats = new double[numPoints];
- Arrays.fill(lats, theLat);
-
- double[] lons = new double[numPoints];
- Arrays.fill(lons, theLon);
-
- verify(small, lats, lons);
- }
-
- public void testAllLatEqual() throws Exception {
-
- // For GeoPointQuery, only run this test nightly:
- assumeTrue("GeoPoint*Query is too slow otherwise", TEST_NIGHTLY || forceSmall() == false);
-
- int numPoints = atLeast(10000);
- boolean small = forceSmall() || random().nextBoolean();
- double lat = randomLat(small);
- 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 == 14 && haveRealDoc) {
- int oldDocID;
- while (true) {
- oldDocID = random().nextInt(docID);
- if (Double.isNaN(lats[oldDocID]) == false) {
- break;
- }
- }
-
- // Fully identical point:
- lons[docID] = lons[oldDocID];
- if (VERBOSE) {
- System.out.println(" doc=" + docID + " lat=" + lat + " lon=" + lons[docID] + " (same lat/lon as doc=" + oldDocID + ")");
- }
- } else {
- lons[docID] = randomLon(small);
- haveRealDoc = true;
- if (VERBOSE) {
- System.out.println(" doc=" + docID + " lat=" + lat + " lon=" + lons[docID]);
- }
- }
- lats[docID] = lat;
- }
-
- verify(small, lats, lons);
- }
-
- public void testAllLonEqual() throws Exception {
-
- // For GeoPointQuery, only run this test nightly:
- assumeTrue("GeoPoint*Query is too slow otherwise", TEST_NIGHTLY || forceSmall() == false);
-
- int numPoints = atLeast(10000);
- boolean small = forceSmall() || random().nextBoolean();
- double theLon = randomLon(small);
- double[] lats = new double[numPoints];
- double[] lons = new double[numPoints];
-
- boolean haveRealDoc = false;
-
- //System.out.println("theLon=" + theLon);
-
- 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 == 14 && haveRealDoc) {
- int oldDocID;
- while (true) {
- oldDocID = random().nextInt(docID);
- if (Double.isNaN(lats[oldDocID]) == false) {
- break;
- }
- }
-
- // Fully identical point:
- lats[docID] = lats[oldDocID];
- if (VERBOSE) {
- System.out.println(" doc=" + docID + " lat=" + lats[docID] + " lon=" + theLon + " (same lat/lon as doc=" + oldDocID + ")");
- }
- } else {
- lats[docID] = randomLat(small);
- haveRealDoc = true;
- if (VERBOSE) {
- System.out.println(" doc=" + docID + " lat=" + lats[docID] + " lon=" + theLon);
- }
- }
- lons[docID] = theLon;
- }
-
- verify(small, lats, lons);
- }
-
- public void testMultiValued() throws Exception {
-
- // For GeoPointQuery, only run this test nightly:
- assumeTrue("GeoPoint*Query is too slow otherwise", TEST_NIGHTLY || forceSmall() == false);
-
- int numPoints = atLeast(10000);
- // Every doc has 2 points:
- double[] lats = new double[2*numPoints];
- double[] lons = new double[2*numPoints];
- Directory dir = newDirectory();
- noVirusChecker(dir);
- IndexWriterConfig iwc = newIndexWriterConfig();
- initIndexWriterConfig(FIELD_NAME, iwc);
-
- // We rely on docID order:
- iwc.setMergePolicy(newLogMergePolicy());
- RandomIndexWriter w = new RandomIndexWriter(random(), dir, iwc);
-
- boolean small = random().nextBoolean();
-
- for (int id=0;id<numPoints;id++) {
- Document doc = new Document();
- lats[2*id] = randomLat(small);
- lons[2*id] = randomLon(small);
- doc.add(newStringField("id", ""+id, Field.Store.YES));
- addPointToDoc(FIELD_NAME, doc, lats[2*id], lons[2*id]);
- lats[2*id+1] = randomLat(small);
- lons[2*id+1] = randomLon(small);
- addPointToDoc(FIELD_NAME, doc, lats[2*id+1], lons[2*id+1]);
-
- if (VERBOSE) {
- System.out.println("id=" + id);
- System.out.println(" lat=" + lats[2*id] + " lon=" + lons[2*id]);
- System.out.println(" lat=" + lats[2*id+1] + " lon=" + lons[2*id+1]);
- }
- w.addDocument(doc);
- }
-
- // TODO: share w/ verify; just need parallel array of the expected ids
- if (random().nextBoolean()) {
- w.forceMerge(1);
- }
- IndexReader r = w.getReader();
- w.close();
-
- // We can't wrap with "exotic" readers because the BKD query must see the BKDDVFormat:
- IndexSearcher s = newSearcher(r, false);
-
- int iters = atLeast(75);
- for (int iter=0;iter<iters;iter++) {
- GeoRect rect = randomRect(small, small == false);
-
- if (VERBOSE) {
- System.out.println("\nTEST: iter=" + iter + " rect=" + rect);
- }
-
- Query query = newRectQuery(FIELD_NAME, rect);
-
- final FixedBitSet hits = new FixedBitSet(r.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);
- }
- });
-
- boolean fail = false;
-
- for(int docID=0;docID<lats.length/2;docID++) {
- double latDoc1 = lats[2*docID];
- double lonDoc1 = lons[2*docID];
- double latDoc2 = lats[2*docID+1];
- double lonDoc2 = lons[2*docID+1];
-
- Boolean result1 = rectContainsPoint(rect, latDoc1, lonDoc1);
- if (result1 == null) {
- // borderline case: cannot test
- continue;
- }
-
- Boolean result2 = rectContainsPoint(rect, latDoc2, lonDoc2);
- if (result2 == null) {
- // borderline case: cannot test
- continue;
- }
-
- boolean expected = result1 == Boolean.TRUE || result2 == Boolean.TRUE;
-
- if (hits.get(docID) != expected) {
- String id = s.doc(docID).get("id");
- if (expected) {
- System.out.println(Thread.currentThread().getName() + ": id=" + id + " docID=" + docID + " should match but did not");
- } else {
- System.out.println(Thread.currentThread().getName() + ": id=" + id + " docID=" + docID + " should not match but did");
- }
- System.out.println(" rect=" + rect);
- System.out.println(" lat=" + latDoc1 + " lon=" + lonDoc1 + "\n lat=" + latDoc2 + " lon=" + lonDoc2);
- System.out.println(" result1=" + result1 + " result2=" + result2);
- fail = true;
- }
- }
-
- if (fail) {
- fail("some hits were wrong");
- }
- }
- r.close();
- dir.close();
- }
-
- public void testRandomTiny() throws Exception {
- // Make sure single-leaf-node case is OK:
- doTestRandom(10);
- }
-
- public void testRandomMedium() throws Exception {
- doTestRandom(10000);
- }
-
- @Nightly
- public void testRandomBig() throws Exception {
- assumeFalse("Direct codec can OOME on this test", TestUtil.getDocValuesFormat(FIELD_NAME).equals("Direct"));
- assumeFalse("Memory codec can OOME on this test", TestUtil.getDocValuesFormat(FIELD_NAME).equals("Memory"));
- 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 small = random().nextBoolean();
-
- boolean haveRealDoc = false;
-
- for (int id=0;id<numPoints;id++) {
- int x = random().nextInt(20);
- if (x == 17) {
- // Some docs don't have a point:
- lats[id] = Double.NaN;
- if (VERBOSE) {
- System.out.println(" id=" + id + " is missing");
- }
- continue;
- }
-
- if (id > 0 && x < 3 && haveRealDoc) {
- int oldID;
- while (true) {
- oldID = random().nextInt(id);
- if (Double.isNaN(lats[oldID]) == false) {
- break;
- }
- }
-
- if (x == 0) {
- // Identical lat to old point
- lats[id] = lats[oldID];
- lons[id] = randomLon(small);
- if (VERBOSE) {
- System.out.println(" id=" + id + " lat=" + lats[id] + " lon=" + lons[id] + " (same lat as doc=" + oldID + ")");
- }
- } else if (x == 1) {
- // Identical lon to old point
- lats[id] = randomLat(small);
- lons[id] = lons[oldID];
- if (VERBOSE) {
- System.out.println(" id=" + id + " lat=" + lats[id] + " lon=" + lons[id] + " (same lon as doc=" + oldID + ")");
- }
- } else {
- assert x == 2;
- // Fully identical point:
- lats[id] = lats[oldID];
- lons[id] = lons[oldID];
- if (VERBOSE) {
- System.out.println(" id=" + id + " lat=" + lats[id] + " lon=" + lons[id] + " (same lat/lon as doc=" + oldID + ")");
- }
- }
- } else {
- lats[id] = randomLat(small);
- lons[id] = randomLon(small);
- haveRealDoc = true;
- if (VERBOSE) {
- System.out.println(" id=" + id + " lat=" + lats[id] + " lon=" + lons[id]);
- }
- }
- }
-
- verify(small, lats, lons);
- }
-
- 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 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 result;
- }
-
- protected GeoRect randomRect(boolean small, boolean canCrossDateLine) {
- double lat0 = randomLat(small);
- double lat1 = randomLat(small);
- double lon0 = randomLon(small);
- double lon1 = randomLon(small);
-
- if (lat1 < lat0) {
- double x = lat0;
- lat0 = lat1;
- lat1 = x;
- }
-
- if (canCrossDateLine == false && lon1 < lon0) {
- double x = lon0;
- lon0 = lon1;
- lon1 = x;
- }
-
- return new GeoRect(lon0, lon1, lat0, lat1);
- }
-
- protected void initIndexWriterConfig(String field, IndexWriterConfig iwc) {
- }
-
- protected abstract void addPointToDoc(String field, Document doc, double lat, double lon);
-
- protected abstract Query newRectQuery(String field, GeoRect bbox);
-
- protected abstract Query newDistanceQuery(String field, double centerLat, double centerLon, double radiusMeters);
-
- protected abstract Query newDistanceRangeQuery(String field, double centerLat, double centerLon, double minRadiusMeters, double radiusMeters);
-
- protected abstract Query newPolygonQuery(String field, double[] lats, double[] lons);
-
- /** Returns null if it's borderline case */
- protected abstract Boolean rectContainsPoint(GeoRect rect, double pointLat, double pointLon);
-
- /** Returns null if it's borderline case */
- protected abstract Boolean polyRectContainsPoint(GeoRect rect, double pointLat, double pointLon);
-
- /** Returns null if it's borderline case */
- protected abstract Boolean circleContainsPoint(double centerLat, double centerLon, double radiusMeters, double pointLat, double pointLon);
-
- protected abstract Boolean distanceRangeContainsPoint(double centerLat, double centerLon, double minRadiusMeters, double radiusMeters, double pointLat, double pointLon);
-
- private static abstract class VerifyHits {
-
- public void test(AtomicBoolean failed, boolean small, 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);
- }
- });
-
- boolean fail = false;
-
- for(int docID=0;docID<maxDoc;docID++) {
- int id = (int) docIDToID.get(docID);
- Boolean expected;
- if (deleted.contains(id)) {
- expected = false;
- } else if (Double.isNaN(lats[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 && hits.get(docID) != expected) {
- if (expected) {
- System.out.println(Thread.currentThread().getName() + ": id=" + id + " should match but did not");
- } else {
- System.out.println(Thread.currentThread().getName() + ": id=" + id + " should not match but did");
- }
- System.out.println(" small=" + small + " query=" + query +
- " docID=" + docID + "\n lat=" + lats[id] + " lon=" + lons[id] +
- "\n deleted?=" + deleted.contains(id));
- if (Double.isNaN(lats[id]) == false) {
- describe(docID, lats[id], lons[id]);
- }
- fail = true;
- }
- }
-
- if (fail) {
- failed.set(true);
- fail("some hits were wrong");
- }
- }
-
- /** 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);
-
- protected abstract void describe(int docID, double lat, double lon);
- }
-
- protected void verify(boolean small, double[] lats, double[] lons) throws Exception {
- IndexWriterConfig iwc = newIndexWriterConfig();
- // Else we can get O(N^2) merging:
- int mbd = iwc.getMaxBufferedDocs();
- if (mbd != -1 && mbd < lats.length/100) {
- iwc.setMaxBufferedDocs(lats.length/100);
- }
- Directory dir;
- if (lats.length > 100000) {
- dir = newFSDirectory(createTempDir(getClass().getSimpleName()));
- } else {
- dir = newDirectory();
- }
- noVirusChecker(dir);
-
- 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) {
- addPointToDoc(FIELD_NAME, doc, lats[id], lons[id]);
- }
- 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);
- }
- final IndexReader r = DirectoryReader.open(w);
- w.close();
-
- // We can't wrap with "exotic" readers because the BKD query must see the BKDDVFormat:
- IndexSearcher s = newSearcher(r, false);
-
- // Make sure queries are thread safe:
- int numThreads = TestUtil.nextInt(random(), 2, 5);
-
- List<Thread> threads = new ArrayList<>();
- final int iters = atLeast(75);
-
- final CountDownLatch startingGun = new CountDownLatch(1);
- final AtomicBoolean failed = new AtomicBoolean();
-
- for(int i=0;i<numThreads;i++) {
- Thread thread = new Thread() {
- @Override
- public void run() {
- try {
- _run();
- } catch (Exception e) {
- failed.set(true);
- throw new RuntimeException(e);
- }
- }
-
- private void _run() throws Exception {
- startingGun.await();
-
- NumericDocValues docIDToID = MultiDocValues.getNumericValues(r, "id");
-
- for (int iter=0;iter<iters && failed.get() == false;iter++) {
-
- if (VERBOSE) {
- System.out.println("\nTEST: iter=" + iter + " s=" + s);
- }
- Query query;
- VerifyHits verifyHits;
-
- if (random().nextBoolean()) {
- // Rect: don't allow dateline crossing when testing small:
- final GeoRect rect = randomRect(small, small == false);
-
- query = newRectQuery(FIELD_NAME, rect);
-
- verifyHits = new VerifyHits() {
- @Override
- protected Boolean shouldMatch(double pointLat, double pointLon) {
- return rectContainsPoint(rect, pointLat, pointLon);
- }
- @Override
- protected void describe(int docID, double lat, double lon) {
- }
- };
-
- } else if (random().nextBoolean()) {
- // Distance
- final boolean rangeQuery = random().nextBoolean();
- final double centerLat = randomLat(small);
- final double centerLon = randomLon(small);
-
- double radiusMeters;
- double minRadiusMeters;
-
- if (small) {
- // Approx 3 degrees lon at the equator:
- radiusMeters = random().nextDouble() * 333000 + 1.0;
- } else {
- // So the query can cover at most 50% of the earth's surface:
- radiusMeters = random().nextDouble() * GeoProjectionUtils.SEMIMAJOR_AXIS * Math.PI / 2.0 + 1.0;
- }
-
- // generate a random minimum radius between 1% and 95% the max radius
- minRadiusMeters = (0.01 + 0.94 * random().nextDouble()) * radiusMeters;
-
- if (VERBOSE) {
- final DecimalFormat df = new DecimalFormat("#,###.00", DecimalFormatSymbols.getInstance(Locale.ENGLISH));
- System.out.println(" radiusMeters = " + df.format(radiusMeters)
- + ((rangeQuery == true) ? " minRadiusMeters = " + df.format(minRadiusMeters) : ""));
- }
-
- try {
- if (rangeQuery == true) {
- query = newDistanceRangeQuery(FIELD_NAME, centerLat, centerLon, minRadiusMeters, radiusMeters);
- } else {
- query = newDistanceQuery(FIELD_NAME, centerLat, centerLon, radiusMeters);
- }
- } catch (IllegalArgumentException e) {
- if (e.getMessage().contains("exceeds maxRadius")) {
- continue;
- }
- throw e;
- }
-
- verifyHits = new VerifyHits() {
- @Override
- protected Boolean shouldMatch(double pointLat, double pointLon) {
- if (rangeQuery == false) {
- return circleContainsPoint(centerLat, centerLon, radiusMeters, pointLat, pointLon);
- } else {
- return distanceRangeContainsPoint(centerLat, centerLon, minRadiusMeters, radiusMeters, pointLat, pointLon);
- }
- }
-
- @Override
- protected void describe(int docID, double pointLat, double pointLon) {
- double distanceKM = SloppyMath.haversin(centerLat, centerLon, pointLat, pointLon);
- System.out.println(" docID=" + docID + " centerLon=" + centerLon + " centerLat=" + centerLat
- + " pointLon=" + pointLon + " pointLat=" + pointLat + " distanceMeters=" + (distanceKM * 1000)
- + " vs" + ((rangeQuery == true) ? " minRadiusMeters=" + minRadiusMeters : "") + " radiusMeters=" + radiusMeters);
- }
- };
-
- // TODO: get poly query working with dateline crossing too (how?)!
- } else {
-
- // TODO: poly query can't handle dateline crossing yet:
- final GeoRect bbox = randomRect(small, false);
-
- // Polygon
- double[] lats = new double[5];
- double[] lons = new double[5];
- lats[0] = bbox.minLat;
- lons[0] = bbox.minLon;
- lats[1] = bbox.maxLat;
- lons[1] = bbox.minLon;
- lats[2] = bbox.maxLat;
- lons[2] = bbox.maxLon;
- lats[3] = bbox.minLat;
- lons[3] = bbox.maxLon;
- lats[4] = bbox.minLat;
- lons[4] = bbox.minLon;
- query = newPolygonQuery(FIELD_NAME, lats, lons);
-
- verifyHits = new VerifyHits() {
- @Override
- protected Boolean shouldMatch(double pointLat, double pointLon) {
- return polyRectContainsPoint(bbox, pointLat, pointLon);
- }
-
- @Override
- protected void describe(int docID, double lat, double lon) {
- }
- };
- }
-
- if (query != null) {
-
- if (VERBOSE) {
- System.out.println(" query=" + query);
- }
-
- verifyHits.test(failed, small, 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);
- assertFalse(failed.get());
- }
-
- protected Directory noVirusChecker(Directory dir) {
- if (dir instanceof MockDirectoryWrapper) {
- ((MockDirectoryWrapper) dir).setEnableVirusScanner(false);
- }
- return dir;
- }
-}