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 2015/10/22 16:35:51 UTC
svn commit: r1710027 [1/2] - in /lucene/dev/branches/branch_5x/lucene:
core/src/java/org/apache/lucene/util/
sandbox/src/java/org/apache/lucene/bkdtree/
sandbox/src/java/org/apache/lucene/document/
sandbox/src/java/org/apache/lucene/search/ sandbox/src...
Author: nknize
Date: Thu Oct 22 14:35:50 2015
New Revision: 1710027
URL: http://svn.apache.org/viewvc?rev=1710027&view=rev
Log:
LUCENE-6780: Improves GeoPointDistanceQuery accuracy with large radius. Improves testing rigor to GeoPointField
Added:
lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoRect.java (with props)
lucene/dev/branches/branch_5x/lucene/sandbox/src/test/org/apache/lucene/util/BaseGeoPointTestCase.java (with props)
Removed:
lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoBoundingBox.java
Modified:
lucene/dev/branches/branch_5x/lucene/core/src/java/org/apache/lucene/util/SloppyMath.java
lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointInBBoxQuery.java
lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointInPolygonQuery.java
lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeReader.java
lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/bkdtree/OfflineLatLonWriter.java
lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/document/GeoPointField.java
lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceQuery.java
lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceQueryImpl.java
lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceRangeQuery.java
lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInBBoxQueryImpl.java
lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInPolygonQuery.java
lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointTermsEnum.java
lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoDistanceUtils.java
lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoHashUtils.java
lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoProjectionUtils.java
lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoUtils.java
lucene/dev/branches/branch_5x/lucene/sandbox/src/test/org/apache/lucene/bkdtree/TestBKDTree.java
lucene/dev/branches/branch_5x/lucene/sandbox/src/test/org/apache/lucene/search/TestGeoPointQuery.java
lucene/dev/branches/branch_5x/lucene/sandbox/src/test/org/apache/lucene/util/TestGeoUtils.java
Modified: lucene/dev/branches/branch_5x/lucene/core/src/java/org/apache/lucene/util/SloppyMath.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/core/src/java/org/apache/lucene/util/SloppyMath.java?rev=1710027&r1=1710026&r2=1710027&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/core/src/java/org/apache/lucene/util/SloppyMath.java (original)
+++ lucene/dev/branches/branch_5x/lucene/core/src/java/org/apache/lucene/util/SloppyMath.java Thu Oct 22 14:35:50 2015
@@ -33,8 +33,10 @@ package org.apache.lucene.util;
public class SloppyMath {
/**
- * Returns the distance in kilometers between two points
- * specified in decimal degrees (latitude/longitude).
+ * Returns the Haversine distance in kilometers between two points
+ * specified in decimal degrees (latitude/longitude). This works correctly
+ * even if the dateline is between the two points.
+ *
* @param lat1 Latitude of the first point.
* @param lon1 Longitude of the first point.
* @param lat2 Latitude of the second point.
Modified: lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointInBBoxQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointInBBoxQuery.java?rev=1710027&r1=1710026&r2=1710027&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointInBBoxQuery.java (original)
+++ lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointInBBoxQuery.java Thu Oct 22 14:35:50 2015
@@ -51,7 +51,7 @@ public class BKDPointInBBoxQuery extends
final double minLon;
final double maxLon;
- /** Matches all points >= minLon, minLat (inclusive) and < maxLon, maxLat (exclusive). */
+ /** Matches all points >= minLon, minLat (inclusive) and < maxLon, maxLat (exclusive). */
public BKDPointInBBoxQuery(String field, double minLat, double maxLat, double minLon, double maxLon) {
this.field = field;
if (BKDTreeWriter.validLat(minLat) == false) {
Modified: lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointInPolygonQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointInPolygonQuery.java?rev=1710027&r1=1710026&r2=1710027&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointInPolygonQuery.java (original)
+++ lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointInPolygonQuery.java Thu Oct 22 14:35:50 2015
@@ -124,7 +124,7 @@ public class BKDPointInPolygonQuery exte
}
BKDTreeSortedNumericDocValues treeDV = (BKDTreeSortedNumericDocValues) sdv;
BKDTreeReader tree = treeDV.getBKDTreeReader();
-
+
DocIdSet result = tree.intersect(minLat, maxLat, minLon, maxLon,
new BKDTreeReader.LatLonFilter() {
@Override
@@ -200,7 +200,6 @@ public class BKDPointInPolygonQuery exte
.append(polyLats[i])
.append("] ");
}
- sb.append(ToStringUtils.boost(getBoost()));
return sb.toString();
}
}
Modified: lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeReader.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeReader.java?rev=1710027&r1=1710026&r2=1710027&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeReader.java (original)
+++ lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeReader.java Thu Oct 22 14:35:50 2015
@@ -34,7 +34,7 @@ import java.util.Collections;
* @lucene.experimental */
final class BKDTreeReader implements Accountable {
- final private int[] splitValues;
+ final private int[] splitValues;
final private int leafNodeOffset;
final private long[] leafBlockFPs;
final int maxDoc;
@@ -156,7 +156,7 @@ final class BKDTreeReader implements Acc
return 0;
}
state.in.seek(fp);
-
+
//System.out.println(" seek to leafFP=" + fp);
// How many points are stored in this leaf cell:
int count = state.in.readVInt();
@@ -349,7 +349,7 @@ final class BKDTreeReader implements Acc
@Override
public long ramBytesUsed() {
- return splitValues.length * RamUsageEstimator.NUM_BYTES_INT +
+ return splitValues.length * RamUsageEstimator.NUM_BYTES_INT +
leafBlockFPs.length * RamUsageEstimator.NUM_BYTES_LONG;
}
Modified: lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/bkdtree/OfflineLatLonWriter.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/bkdtree/OfflineLatLonWriter.java?rev=1710027&r1=1710026&r2=1710027&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/bkdtree/OfflineLatLonWriter.java (original)
+++ lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/bkdtree/OfflineLatLonWriter.java Thu Oct 22 14:35:50 2015
@@ -42,7 +42,7 @@ final class OfflineLatLonWriter implemen
out = new OutputStreamDataOutput(new BufferedOutputStream(Files.newOutputStream(tempFile)));
this.count = count;
}
-
+
@Override
public void append(int latEnc, int lonEnc, long ord, int docID) throws IOException {
out.writeInt(latEnc);
Modified: lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/document/GeoPointField.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/document/GeoPointField.java?rev=1710027&r1=1710026&r2=1710027&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/document/GeoPointField.java (original)
+++ lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/document/GeoPointField.java Thu Oct 22 14:35:50 2015
@@ -106,4 +106,24 @@ public final class GeoPointField extends
}
fieldsData = GeoUtils.mortonHash(lon, lat);
}
+
+ public double getLon() {
+ return GeoUtils.mortonUnhashLon((long) fieldsData);
+ }
+
+ public double getLat() {
+ return GeoUtils.mortonUnhashLat((long) fieldsData);
+ }
+
+ @Override
+ public String toString() {
+ if (fieldsData == null) {
+ return null;
+ }
+ StringBuilder sb = new StringBuilder();
+ sb.append(GeoUtils.mortonUnhashLon((long) fieldsData));
+ sb.append(',');
+ sb.append(GeoUtils.mortonUnhashLat((long) fieldsData));
+ return sb.toString();
+ }
}
Modified: lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceQuery.java?rev=1710027&r1=1710026&r2=1710027&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceQuery.java (original)
+++ lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceQuery.java Thu Oct 22 14:35:50 2015
@@ -20,40 +20,47 @@ package org.apache.lucene.search;
import java.io.IOException;
import org.apache.lucene.index.IndexReader;
-import org.apache.lucene.util.GeoProjectionUtils;
+import org.apache.lucene.util.GeoRect;
import org.apache.lucene.util.GeoUtils;
+import org.apache.lucene.util.SloppyMath;
/** Implements a simple point distance query on a GeoPoint field. This is based on
* {@link org.apache.lucene.search.GeoPointInBBoxQuery} and is implemented using a two phase approach. First,
* like {@code GeoPointInBBoxQueryImpl} candidate terms are queried using the numeric ranges based on
* the morton codes of the min and max lat/lon pairs that intersect the boundary of the point-radius
- * circle (see {@link org.apache.lucene.util.GeoUtils#lineCrossesSphere}. Terms
+ * circle. Terms
* passing this initial filter are then passed to a secondary {@code postFilter} method that verifies whether the
* decoded lat/lon point fall within the specified query distance (see {@link org.apache.lucene.util.SloppyMath#haversin}.
* All morton value comparisons are subject to the same precision tolerance defined in
* {@value org.apache.lucene.util.GeoUtils#TOLERANCE} and distance comparisons are subject to the accuracy of the
* haversine formula (from R.W. Sinnott, "Virtues of the Haversine", Sky and Telescope, vol. 68, no. 2, 1984, p. 159)
*
- *
- * Note: This query currently uses haversine which is a sloppy distance calculation (see above reference). For large
+ * <p>Note: This query currently uses haversine which is a sloppy distance calculation (see above reference). For large
* queries one can expect upwards of 400m error. Vincenty shrinks this to ~40m error but pays a penalty for computing
* using the spheroid
*
- * @lucene.experimental
- */
+ * @lucene.experimental */
public class GeoPointDistanceQuery extends GeoPointInBBoxQuery {
protected final double centerLon;
protected final double centerLat;
- protected final double radius;
+ protected final double radiusMeters;
/** NOTE: radius is in meters. */
- public GeoPointDistanceQuery(final String field, final double centerLon, final double centerLat, final double radius) {
- this(field, computeBBox(centerLon, centerLat, radius), centerLon, centerLat, radius);
+ public GeoPointDistanceQuery(final String field, final double centerLon, final double centerLat, final double radiusMeters) {
+ this(field, GeoUtils.circleToBBox(centerLon, centerLat, radiusMeters), centerLon, centerLat, radiusMeters);
}
- private GeoPointDistanceQuery(final String field, GeoBoundingBox bbox, final double centerLon,
- final double centerLat, final double radius) {
+ private GeoPointDistanceQuery(final String field, GeoRect bbox, final double centerLon,
+ final double centerLat, final double radiusMeters) {
super(field, bbox.minLon, bbox.minLat, bbox.maxLon, bbox.maxLat);
+ {
+ // check longitudinal overlap (limits radius)
+ final double maxRadius = SloppyMath.haversin(centerLat, centerLon, centerLat, (180.0 + centerLon) % 360)*1000.0;
+ if (radiusMeters > maxRadius) {
+ throw new IllegalArgumentException("radiusMeters " + radiusMeters + " exceeds maxRadius [" + maxRadius
+ + "] at location [" + centerLon + " " + centerLat + "]");
+ }
+ }
if (GeoUtils.isValidLon(centerLon) == false) {
throw new IllegalArgumentException("invalid centerLon " + centerLon);
@@ -63,9 +70,13 @@ public class GeoPointDistanceQuery exten
throw new IllegalArgumentException("invalid centerLat " + centerLat);
}
+ if (radiusMeters <= 0.0) {
+ throw new IllegalArgumentException("invalid radiusMeters " + radiusMeters);
+ }
+
this.centerLon = centerLon;
this.centerLat = centerLat;
- this.radius = radius;
+ this.radiusMeters = radiusMeters;
}
@Override
@@ -74,27 +85,17 @@ public class GeoPointDistanceQuery exten
return super.rewrite(reader);
}
if (maxLon < minLon) {
- BooleanQuery.Builder bq = new BooleanQuery.Builder();
+ BooleanQuery.Builder bqb = new BooleanQuery.Builder();
- GeoPointDistanceQueryImpl left = new GeoPointDistanceQueryImpl(field, this, new GeoBoundingBox(-180.0D, maxLon,
+ GeoPointDistanceQueryImpl left = new GeoPointDistanceQueryImpl(field, this, new GeoRect(GeoUtils.MIN_LON_INCL, maxLon,
minLat, maxLat));
- bq.add(new BooleanClause(left, BooleanClause.Occur.SHOULD));
- GeoPointDistanceQueryImpl right = new GeoPointDistanceQueryImpl(field, this, new GeoBoundingBox(minLon, 180.0D,
+ bqb.add(new BooleanClause(left, BooleanClause.Occur.SHOULD));
+ GeoPointDistanceQueryImpl right = new GeoPointDistanceQueryImpl(field, this, new GeoRect(minLon, GeoUtils.MAX_LON_INCL,
minLat, maxLat));
- bq.add(new BooleanClause(right, BooleanClause.Occur.SHOULD));
- return bq.build();
+ bqb.add(new BooleanClause(right, BooleanClause.Occur.SHOULD));
+ return bqb.build();
}
- return new GeoPointDistanceQueryImpl(field, this, new GeoBoundingBox(this.minLon, this.maxLon, this.minLat, this.maxLat));
- }
-
- static GeoBoundingBox computeBBox(final double centerLon, final double centerLat, final double radius) {
- double[] t = GeoProjectionUtils.pointFromLonLatBearing(centerLon, centerLat, 0, radius, null);
- double[] r = GeoProjectionUtils.pointFromLonLatBearing(centerLon, centerLat, 90, radius, null);
- double[] b = GeoProjectionUtils.pointFromLonLatBearing(centerLon, centerLat, 180, radius, null);
- double[] l = GeoProjectionUtils.pointFromLonLatBearing(centerLon, centerLat, 270, radius, null);
-
- return new GeoBoundingBox(GeoUtils.normalizeLon(l[0]), GeoUtils.normalizeLon(r[0]), GeoUtils.normalizeLat(b[1]),
- GeoUtils.normalizeLat(t[1]));
+ return new GeoPointDistanceQueryImpl(field, this, new GeoRect(this.minLon, this.maxLon, this.minLat, this.maxLat));
}
@Override
@@ -107,7 +108,7 @@ public class GeoPointDistanceQuery exten
if (Double.compare(that.centerLat, centerLat) != 0) return false;
if (Double.compare(that.centerLon, centerLon) != 0) return false;
- if (Double.compare(that.radius, radius) != 0) return false;
+ if (Double.compare(that.radiusMeters, radiusMeters) != 0) return false;
return true;
}
@@ -120,7 +121,7 @@ public class GeoPointDistanceQuery exten
result = 31 * result + (int) (temp ^ (temp >>> 32));
temp = Double.doubleToLongBits(centerLat);
result = 31 * result + (int) (temp ^ (temp >>> 32));
- temp = Double.doubleToLongBits(radius);
+ temp = Double.doubleToLongBits(radiusMeters);
result = 31 * result + (int) (temp ^ (temp >>> 32));
return result;
}
@@ -141,17 +142,8 @@ public class GeoPointDistanceQuery exten
.append(centerLat)
.append(']')
.append(" Distance: ")
- .append(radius)
- .append(" m")
- .append(" Lower Left: [")
- .append(minLon)
- .append(',')
- .append(minLat)
- .append(']')
- .append(" Upper Right: [")
- .append(maxLon)
- .append(',')
- .append(maxLat)
+ .append(radiusMeters)
+ .append(" meters")
.append("]")
.toString();
}
@@ -164,7 +156,7 @@ public class GeoPointDistanceQuery exten
return this.centerLat;
}
- public double getRadius() {
- return this.radius;
+ public double getRadiusMeters() {
+ return this.radiusMeters;
}
}
Modified: lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceQueryImpl.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceQueryImpl.java?rev=1710027&r1=1710026&r2=1710027&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceQueryImpl.java (original)
+++ lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceQueryImpl.java Thu Oct 22 14:35:50 2015
@@ -19,9 +19,11 @@ package org.apache.lucene.search;
import java.io.IOException;
+import org.apache.lucene.document.GeoPointField;
import org.apache.lucene.index.Terms;
import org.apache.lucene.index.TermsEnum;
import org.apache.lucene.util.AttributeSource;
+import org.apache.lucene.util.GeoRect;
import org.apache.lucene.util.GeoUtils;
import org.apache.lucene.util.SloppyMath;
@@ -32,7 +34,7 @@ import org.apache.lucene.util.SloppyMath
final class GeoPointDistanceQueryImpl extends GeoPointInBBoxQueryImpl {
private final GeoPointDistanceQuery query;
- GeoPointDistanceQueryImpl(final String field, final GeoPointDistanceQuery q, final GeoBoundingBox bbox) {
+ GeoPointDistanceQueryImpl(final String field, final GeoPointDistanceQuery q, final GeoRect bbox) {
super(field, bbox.minLon, bbox.minLat, bbox.maxLon, bbox.maxLat);
query = q;
}
@@ -53,14 +55,31 @@ final class GeoPointDistanceQueryImpl ex
super(tenum, minLon, minLat, maxLon, maxLat);
}
+ /**
+ * Computes the maximum shift for the given pointDistanceQuery. This prevents unnecessary depth traversal
+ * given the size of the distance query.
+ */
+ @Override
+ protected short computeMaxShift() {
+ final short shiftFactor;
+
+ if (query.radiusMeters > 1000000) {
+ shiftFactor = 5;
+ } else {
+ shiftFactor = 4;
+ }
+
+ return (short)(GeoPointField.PRECISION_STEP * shiftFactor);
+ }
+
@Override
protected boolean cellCrosses(final double minLon, final double minLat, final double maxLon, final double maxLat) {
- return GeoUtils.rectCrossesCircle(minLon, minLat, maxLon, maxLat, query.centerLon, query.centerLat, query.radius);
+ return GeoUtils.rectCrossesCircle(minLon, minLat, maxLon, maxLat, query.centerLon, query.centerLat, query.radiusMeters);
}
@Override
protected boolean cellWithin(final double minLon, final double minLat, final double maxLon, final double maxLat) {
- return GeoUtils.rectWithinCircle(minLon, minLat, maxLon, maxLat, query.centerLon, query.centerLat, query.radius);
+ return GeoUtils.rectWithinCircle(minLon, minLat, maxLon, maxLat, query.centerLon, query.centerLat, query.radiusMeters);
}
@Override
@@ -77,7 +96,7 @@ final class GeoPointDistanceQueryImpl ex
*/
@Override
protected boolean postFilter(final double lon, final double lat) {
- return (SloppyMath.haversin(query.centerLat, query.centerLon, lat, lon) * 1000.0 <= query.radius);
+ return (SloppyMath.haversin(query.centerLat, query.centerLon, lat, lon) * 1000.0 <= query.radiusMeters);
}
}
@@ -101,7 +120,7 @@ final class GeoPointDistanceQueryImpl ex
return result;
}
- public double getRadius() {
- return query.getRadius();
+ public double getRadiusMeters() {
+ return query.getRadiusMeters();
}
}
Modified: lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceRangeQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceRangeQuery.java?rev=1710027&r1=1710026&r2=1710027&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceRangeQuery.java (original)
+++ lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceRangeQuery.java Thu Oct 22 14:35:50 2015
@@ -18,25 +18,23 @@ package org.apache.lucene.search;
*/
import java.io.IOException;
-import java.util.List;
import org.apache.lucene.index.IndexReader;
-import org.apache.lucene.util.GeoProjectionUtils;
/** Implements a point distance range query on a GeoPoint field. This is based on
* {@code org.apache.lucene.search.GeoPointDistanceQuery} and is implemented using a
* {@code org.apache.lucene.search.BooleanClause.MUST_NOT} clause to exclude any points that fall within
- * minRadius from the provided point.
+ * minRadiusMeters from the provided point.
*
* @lucene.experimental
*/
public final class GeoPointDistanceRangeQuery extends GeoPointDistanceQuery {
- protected final double minRadius;
+ protected final double minRadiusMeters;
public GeoPointDistanceRangeQuery(final String field, final double centerLon, final double centerLat,
- final double minRadius, final double maxRadius) {
+ final double minRadiusMeters, final double maxRadius) {
super(field, centerLon, centerLat, maxRadius);
- this.minRadius = minRadius;
+ this.minRadiusMeters = minRadiusMeters;
}
@Override
@@ -45,7 +43,7 @@ public final class GeoPointDistanceRange
return super.rewrite(reader);
}
Query q = super.rewrite(reader);
- if (minRadius == 0.0) {
+ if (minRadiusMeters == 0.0) {
return q;
}
@@ -53,13 +51,8 @@ public final class GeoPointDistanceRange
BooleanQuery.Builder bqb = new BooleanQuery.Builder();
// create a new exclusion query
- GeoPointDistanceQuery exclude = new GeoPointDistanceQuery(field, centerLon, centerLat, minRadius);
- // full map search
- if (radius >= GeoProjectionUtils.SEMIMINOR_AXIS) {
- bqb.add(new BooleanClause(new GeoPointInBBoxQuery(this.field, -180.0, -90.0, 180.0, 90.0), BooleanClause.Occur.MUST));
- } else {
- bqb.add(new BooleanClause(q, BooleanClause.Occur.MUST));
- }
+ GeoPointDistanceQuery exclude = new GeoPointDistanceQuery(field, centerLon, centerLat, minRadiusMeters);
+ bqb.add(new BooleanClause(q, BooleanClause.Occur.MUST));
bqb.add(new BooleanClause(exclude, BooleanClause.Occur.MUST_NOT));
return bqb.build();
@@ -81,10 +74,10 @@ public final class GeoPointDistanceRange
.append(centerLat)
.append(']')
.append(" From Distance: ")
- .append(minRadius)
+ .append(minRadiusMeters)
.append(" m")
.append(" To Distance: ")
- .append(radius)
+ .append(radiusMeters)
.append(" m")
.append(" Lower Left: [")
.append(minLon)
@@ -100,10 +93,10 @@ public final class GeoPointDistanceRange
}
public double getMinRadiusMeters() {
- return this.minRadius;
+ return this.minRadiusMeters;
}
public double getMaxRadiusMeters() {
- return this.radius;
+ return this.radiusMeters;
}
}
Modified: lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInBBoxQueryImpl.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInBBoxQueryImpl.java?rev=1710027&r1=1710026&r2=1710027&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInBBoxQueryImpl.java (original)
+++ lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInBBoxQueryImpl.java Thu Oct 22 14:35:50 2015
@@ -19,11 +19,12 @@ package org.apache.lucene.search;
import java.io.IOException;
+import org.apache.lucene.document.GeoPointField;
import org.apache.lucene.index.Terms;
import org.apache.lucene.index.TermsEnum;
import org.apache.lucene.util.AttributeSource;
import org.apache.lucene.util.GeoUtils;
-import org.apache.lucene.util.ToStringUtils;
+import org.apache.lucene.util.SloppyMath;
/** Package private implementation for the public facing GeoPointInBBoxQuery delegate class.
*
@@ -59,6 +60,23 @@ class GeoPointInBBoxQueryImpl extends Ge
super(tenum, minLon, minLat, maxLon, maxLat);
}
+ @Override
+ protected short computeMaxShift() {
+ final short shiftFactor;
+
+ // compute diagonal radius
+ double midLon = (minLon + maxLon) * 0.5;
+ double midLat = (minLat + maxLat) * 0.5;
+
+ if (SloppyMath.haversin(minLat, minLon, midLat, midLon)*1000 > 1000000) {
+ shiftFactor = 5;
+ } else {
+ shiftFactor = 4;
+ }
+
+ return (short)(GeoPointField.PRECISION_STEP * shiftFactor);
+ }
+
/**
* Determine whether the quad-cell crosses the shape
*/
Modified: lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInPolygonQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInPolygonQuery.java?rev=1710027&r1=1710026&r2=1710027&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInPolygonQuery.java (original)
+++ lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInPolygonQuery.java Thu Oct 22 14:35:50 2015
@@ -17,14 +17,14 @@ package org.apache.lucene.search;
* limitations under the License.
*/
+import java.io.IOException;
+import java.util.Arrays;
+
import org.apache.lucene.index.Terms;
import org.apache.lucene.index.TermsEnum;
import org.apache.lucene.util.AttributeSource;
+import org.apache.lucene.util.GeoRect;
import org.apache.lucene.util.GeoUtils;
-import org.apache.lucene.util.ToStringUtils;
-
-import java.io.IOException;
-import java.util.Arrays;
/** Implements a simple point in polygon query on a GeoPoint field. This is based on
* {@code GeoPointInBBoxQueryImpl} and is implemented using a
@@ -36,14 +36,14 @@ import java.util.Arrays;
* term is passed to the final point in polygon check. All value comparisons are subject
* to the same precision tolerance defined in {@value org.apache.lucene.util.GeoUtils#TOLERANCE}
*
- * NOTES:
+ * <p>NOTES:
* 1. The polygon coordinates need to be in either clockwise or counter-clockwise order.
* 2. The polygon must not be self-crossing, otherwise the query may result in unexpected behavior
* 3. All latitude/longitude values must be in decimal degrees.
* 4. Complex computational geometry (e.g., dateline wrapping, polygon with holes) is not supported
* 5. For more advanced GeoSpatial indexing and query operations see spatial module
*
- * @lucene.experimental
+ * @lucene.experimental
*/
public final class GeoPointInPolygonQuery extends GeoPointInBBoxQueryImpl {
// polygon position arrays - this avoids the use of any objects or
@@ -60,7 +60,7 @@ public final class GeoPointInPolygonQuer
}
/** Common constructor, used only internally. */
- private GeoPointInPolygonQuery(final String field, GeoBoundingBox bbox, final double[] polyLons, final double[] polyLats) {
+ private GeoPointInPolygonQuery(final String field, GeoRect bbox, final double[] polyLons, final double[] polyLats) {
super(field, bbox.minLon, bbox.minLat, bbox.maxLon, bbox.maxLat);
if (polyLats.length != polyLons.length) {
throw new IllegalArgumentException("polyLats and polyLons must be equal length");
@@ -183,7 +183,7 @@ public final class GeoPointInPolygonQuer
}
}
- private static GeoBoundingBox computeBBox(double[] polyLons, double[] polyLats) {
+ private static GeoRect computeBBox(double[] polyLons, double[] polyLats) {
if (polyLons.length != polyLats.length) {
throw new IllegalArgumentException("polyLons and polyLats must be equal length");
}
@@ -206,7 +206,7 @@ public final class GeoPointInPolygonQuer
maxLat = Math.max(polyLats[i], maxLat);
}
- return new GeoBoundingBox(minLon, maxLon, minLat, maxLat);
+ return new GeoRect(minLon, maxLon, minLat, maxLat);
}
/**
Modified: lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointTermsEnum.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointTermsEnum.java?rev=1710027&r1=1710026&r2=1710027&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointTermsEnum.java (original)
+++ lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointTermsEnum.java Thu Oct 22 14:35:50 2015
@@ -48,9 +48,7 @@ abstract class GeoPointTermsEnum extends
private final List<Range> rangeBounds = new LinkedList<>();
// detail level should be a factor of PRECISION_STEP limiting the depth of recursion (and number of ranges)
- // in this case a factor of 4 brings the detail level to ~0.002/0.001 degrees lon/lat respectively (or ~222m/111m)
- private static final short MAX_SHIFT = GeoPointField.PRECISION_STEP * 4;
- protected static final short DETAIL_LEVEL = ((GeoUtils.BITS<<1)-MAX_SHIFT)/2;
+ protected final short DETAIL_LEVEL;
GeoPointTermsEnum(final TermsEnum tenum, final double minLon, final double minLat,
final double maxLon, final double maxLat) {
@@ -61,6 +59,7 @@ abstract class GeoPointTermsEnum extends
this.minLat = GeoUtils.mortonUnhashLat(rectMinHash);
this.maxLon = GeoUtils.mortonUnhashLon(rectMaxHash);
this.maxLat = GeoUtils.mortonUnhashLat(rectMaxHash);
+ DETAIL_LEVEL = (short)(((GeoUtils.BITS<<1)-computeMaxShift())/2);
computeRange(0L, (short) (((GeoUtils.BITS) << 1) - 1));
Collections.sort(rangeBounds);
@@ -103,12 +102,23 @@ abstract class GeoPointTermsEnum extends
// if cell is within and a factor of the precision step, or it crosses the edge of the shape add the range
final boolean within = res % GeoPointField.PRECISION_STEP == 0 && cellWithin(minLon, minLat, maxLon, maxLat);
if (within || (level == DETAIL_LEVEL && cellIntersectsShape(minLon, minLat, maxLon, maxLat))) {
- rangeBounds.add(new Range(start, res, !within));
+ final short nextRes = (short)(res-1);
+ if (nextRes % GeoPointField.PRECISION_STEP == 0) {
+ rangeBounds.add(new Range(start, nextRes, !within));
+ rangeBounds.add(new Range(start|(1L<<nextRes), nextRes, !within));
+ } else {
+ rangeBounds.add(new Range(start, res, !within));
+ }
} else if (level < DETAIL_LEVEL && cellIntersectsMBR(minLon, minLat, maxLon, maxLat)) {
computeRange(start, (short) (res - 1));
}
}
+ protected short computeMaxShift() {
+ // in this case a factor of 4 brings the detail level to ~0.002/0.001 degrees lon/lat respectively (or ~222m/111m)
+ return GeoPointField.PRECISION_STEP * 4;
+ }
+
/**
* Determine whether the quad-cell crosses the shape
*/
Modified: lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoDistanceUtils.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoDistanceUtils.java?rev=1710027&r1=1710026&r2=1710027&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoDistanceUtils.java (original)
+++ lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoDistanceUtils.java Thu Oct 22 14:35:50 2015
@@ -110,6 +110,46 @@ public class GeoDistanceUtils {
}
/**
+ * Finds the closest point within a rectangle (defined by rMinX, rMinY, rMaxX, rMaxY) to the given (lon, lat) point
+ * the result is provided in closestPt. When the point is outside the rectangle, the closest point is on an edge
+ * or corner of the rectangle; else, the closest point is the point itself.
+ */
+ public static void closestPointOnBBox(final double rMinX, final double rMinY, final double rMaxX, final double rMaxY,
+ final double lon, final double lat, double[] closestPt) {
+ assert closestPt != null && closestPt.length == 2;
+
+ closestPt[0] = 0;
+ closestPt[1] = 0;
+
+ boolean xSet = true;
+ boolean ySet = true;
+
+ if (lon > rMaxX) {
+ closestPt[0] = rMaxX;
+ } else if (lon < rMinX) {
+ closestPt[0] = rMinX;
+ } else {
+ xSet = false;
+ }
+
+ if (lat > rMaxY) {
+ closestPt[1] = rMaxY;
+ } else if (lat < rMinY) {
+ closestPt[1] = rMinY;
+ } else {
+ ySet = false;
+ }
+
+ if (closestPt[0] == 0 && xSet == false) {
+ closestPt[0] = lon;
+ }
+
+ if (closestPt[1] == 0 && ySet == false) {
+ closestPt[1] = lat;
+ }
+ }
+
+ /**
* Compute the inverse haversine to determine distance in degrees longitude for provided distance in meters
* @param lat latitude to compute delta degrees lon
* @param distance distance in meters to convert to degrees lon
Modified: lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoHashUtils.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoHashUtils.java?rev=1710027&r1=1710026&r2=1710027&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoHashUtils.java (original)
+++ lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoHashUtils.java Thu Oct 22 14:35:50 2015
@@ -64,6 +64,25 @@ public class GeoHashUtils {
}
/**
+ * Encode an existing geohash long to the provided precision
+ */
+ public static long longEncode(long geohash, int level) {
+ final short precision = (short)(geohash & 15);
+ if (precision == level) {
+ return geohash;
+ } else if (precision > level) {
+ return ((geohash >>> (((precision - level) * 5) + 4)) << 4) | level;
+ }
+ return ((geohash >>> 4) << (((level - precision) * 5) + 4) | level);
+ }
+
+ public static long fromMorton(long morton, int level) {
+ long mFlipped = BitUtil.flipFlop(morton);
+ mFlipped >>>= (((GeoHashUtils.PRECISION - level) * 5) + MORTON_OFFSET);
+ return (mFlipped << 4) | level;
+ }
+
+ /**
* Encode to a geohash string from the geohash based long format
*/
public static final String stringEncode(long geoHashLong) {
@@ -71,7 +90,7 @@ public class GeoHashUtils {
geoHashLong >>>= 4;
char[] chars = new char[level];
do {
- chars[--level] = BASE_32[(int)(geoHashLong&31L)];
+ chars[--level] = BASE_32[(int) (geoHashLong&31L)];
geoHashLong>>>=5;
} while(level > 0);
@@ -89,19 +108,10 @@ public class GeoHashUtils {
* Encode to a level specific geohash string from full resolution longitude, latitude
*/
public static final String stringEncode(final double lon, final double lat, final int level) {
- // bit twiddle to geohash (since geohash is a swapped (lon/lat) encoding)
- final long hashedVal = BitUtil.flipFlop(GeoUtils.mortonHash(lon, lat));
+ // convert to geohashlong
+ final long ghLong = fromMorton(GeoUtils.mortonHash(lon, lat), level);
+ return stringEncode(ghLong);
- StringBuilder geoHash = new StringBuilder();
- short precision = 0;
- final short msf = (GeoUtils.BITS<<1)-5;
- long mask = 31L<<msf;
- do {
- geoHash.append(BASE_32[(int)((mask & hashedVal)>>>(msf-(precision*5)))]);
- // next 5 bits
- mask >>>= 5;
- } while (++precision < level);
- return geoHash.toString();
}
/**
@@ -151,7 +161,7 @@ public class GeoHashUtils {
final int level = (int)(geoHashLong&15);
final short odd = (short)(level & 1);
- return BitUtil.flipFlop((geoHashLong >>> 4) << odd) << (((12 - level) * 5) + (MORTON_OFFSET - odd));
+ return BitUtil.flipFlop(((geoHashLong >>> 4) << odd) << (((12 - level) * 5) + (MORTON_OFFSET - odd)));
}
private static final char encode(int x, int y) {
Modified: lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoProjectionUtils.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoProjectionUtils.java?rev=1710027&r1=1710026&r2=1710027&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoProjectionUtils.java (original)
+++ lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoProjectionUtils.java Thu Oct 22 14:35:50 2015
@@ -31,6 +31,10 @@ public class GeoProjectionUtils {
static final double PI_OVER_2 = StrictMath.PI / 2.0D;
static final double SEMIMAJOR_AXIS2 = SEMIMAJOR_AXIS * SEMIMAJOR_AXIS;
static final double SEMIMINOR_AXIS2 = SEMIMINOR_AXIS * SEMIMINOR_AXIS;
+ public static final double MIN_LON_RADIANS = StrictMath.toRadians(GeoUtils.MIN_LON_INCL);
+ public static final double MIN_LAT_RADIANS = StrictMath.toRadians(GeoUtils.MIN_LAT_INCL);
+ public static final double MAX_LON_RADIANS = StrictMath.toRadians(GeoUtils.MAX_LON_INCL);
+ public static final double MAX_LAT_RADIANS = StrictMath.toRadians(GeoUtils.MAX_LAT_INCL);
/**
* Converts from geocentric earth-centered earth-fixed to geodesic lat/lon/alt
@@ -375,8 +379,8 @@ public class GeoProjectionUtils {
final double lam = lambda - (1-c) * FLATTENING * sinAlpha *
(sigma + c * sinSigma * (cos2SigmaM + c * cosSigma * (-1 + 2* cos2SigmaM*cos2SigmaM)));
- pt[0] = lon + StrictMath.toDegrees(lam);
- pt[1] = StrictMath.toDegrees(lat2);
+ pt[0] = GeoUtils.normalizeLon(lon + StrictMath.toDegrees(lam));
+ pt[1] = GeoUtils.normalizeLat(StrictMath.toDegrees(lat2));
return pt;
}
Added: lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoRect.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoRect.java?rev=1710027&view=auto
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoRect.java (added)
+++ lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoRect.java Thu Oct 22 14:35:50 2015
@@ -0,0 +1,67 @@
+package org.apache.lucene.util;
+
+/*
+ * 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.
+ */
+
+/** Represents a lat/lon rectangle. */
+public class GeoRect {
+ public final double minLon;
+ public final double maxLon;
+ public final double minLat;
+ public final double maxLat;
+
+ public GeoRect(double minLon, double maxLon, double minLat, double maxLat) {
+ if (GeoUtils.isValidLon(minLon) == false) {
+ throw new IllegalArgumentException("invalid minLon " + minLon);
+ }
+ if (GeoUtils.isValidLon(maxLon) == false) {
+ throw new IllegalArgumentException("invalid maxLon " + maxLon);
+ }
+ if (GeoUtils.isValidLat(minLat) == false) {
+ throw new IllegalArgumentException("invalid minLat " + minLat);
+ }
+ if (GeoUtils.isValidLat(maxLat) == false) {
+ throw new IllegalArgumentException("invalid maxLat " + maxLat);
+ }
+ this.minLon = minLon;
+ this.maxLon = maxLon;
+ this.minLat = minLat;
+ this.maxLat = maxLat;
+ assert maxLat >= minLat;
+
+ // NOTE: cannot assert maxLon >= minLon since this rect could cross the dateline
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder b = new StringBuilder();
+ b.append("GeoRect(lon=");
+ b.append(minLon);
+ b.append(" TO ");
+ b.append(maxLon);
+ if (maxLon < minLon) {
+ b.append(" (crosses dateline!)");
+ }
+ b.append(" lat=");
+ b.append(minLat);
+ b.append(" TO ");
+ b.append(maxLat);
+ b.append(")");
+
+ return b.toString();
+ }
+}
Modified: lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoUtils.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoUtils.java?rev=1710027&r1=1710026&r2=1710027&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoUtils.java (original)
+++ lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoUtils.java Thu Oct 22 14:35:50 2015
@@ -25,11 +25,9 @@ import java.util.ArrayList;
* @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. */
@@ -61,24 +59,24 @@ public final class GeoUtils {
}
private static long scaleLon(final double val) {
- return (long) ((val-MIN_LON) * LON_SCALE);
+ return (long) ((val-MIN_LON_INCL) * LON_SCALE);
}
private static long scaleLat(final double val) {
- return (long) ((val-MIN_LAT) * LAT_SCALE);
+ return (long) ((val-MIN_LAT_INCL) * LAT_SCALE);
}
private static double unscaleLon(final long val) {
- return (val / LON_SCALE) + MIN_LON;
+ return (val / LON_SCALE) + MIN_LON_INCL;
}
private static double unscaleLat(final long val) {
- return (val / LAT_SCALE) + MIN_LAT;
+ return (val / LAT_SCALE) + MIN_LAT_INCL;
}
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,8 +107,13 @@ 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) {
+ /**
+ * 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 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);
}
@@ -161,7 +164,7 @@ public final class GeoUtils {
}
/**
- * Computes whether a rectangle is wholly within another rectangle (shared boundaries allowed)
+ * 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) {
@@ -248,11 +251,11 @@ public final class GeoUtils {
*
* @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 +267,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.pointFromLonLatBearing(lon, lat, angle, radiusMeters, pt);
lons[i] = pt[0];
lats[i] = pt[1];
}
@@ -291,47 +294,79 @@ public final class GeoUtils {
}
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);
+ 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;
}
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);
+ 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 radius) {
- return !(rectAnyCornersOutsideCircle(rMinX, rMinY, rMaxX, rMaxY, centerLon, centerLat, radius));
+ final double centerLon, final double centerLat, final double radiusMeters) {
+ return rectAnyCornersOutsideCircle(rMinX, rMinY, rMaxX, rMaxY, centerLon, centerLat, radiusMeters) == false;
}
/**
- * Computes whether a rectangle crosses a circle
+ * 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 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);
+ final double centerLon, final double centerLat, final double radiusMeters) {
+ return rectAnyCornersInCircle(rMinX, rMinY, rMaxX, rMaxY, centerLon, centerLat, radiusMeters)
+ || isClosestPointOnRectWithinRange(rMinX, rMinY, rMaxX, rMaxY, centerLon, centerLat, radiusMeters);
+ }
+
+ 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) {
+ double[] closestPt = {0, 0};
+ GeoDistanceUtils.closestPointOnBBox(rMinX, rMinY, rMaxX, rMaxY, centerLon, centerLat, closestPt);
+ return SloppyMath.haversin(centerLat, centerLon, closestPt[1], closestPt[0])*1000.0 <= radiusMeters;
}
- 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);
+ /**
+ * 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 = StrictMath.toRadians(centerLat);
+ final double radLon = StrictMath.toRadians(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 = StrictMath.asin(StrictMath.sin(radDistance) / StrictMath.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(StrictMath.toDegrees(minLon), StrictMath.toDegrees(maxLon),
+ StrictMath.toDegrees(minLat), StrictMath.toDegrees(maxLat));
}
+ /*
/**
* Computes whether or a 3dimensional line segment intersects or crosses a sphere
*
@@ -344,12 +379,13 @@ public final class GeoUtils {
* @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)
+ * @param radiusMeters search sphere radius (in meters)
* @return whether the provided line segment is a secant of the
- */
+ * /
+ // NOTE: not used for 2d at the moment. used for 3d w/ altitude (we can keep or add back)
private static boolean lineCrossesSphere(double lon1, double lat1, double alt1, double lon2,
double lat2, double alt2, double centerLon, double centerLat,
- double centerAlt, double radius) {
+ 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);
@@ -364,7 +400,7 @@ public final class GeoUtils {
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);
+ final double c = (fX*fX + fY*fY + fZ*fZ) - (radiusMeters*radiusMeters);
double discrim = (b*b)-(4*a*c);
if (discrim < 0) {
@@ -382,6 +418,7 @@ public final class GeoUtils {
return true;
}
+ */
public static boolean isValidLat(double lat) {
return Double.isNaN(lat) == false && lat >= MIN_LAT_INCL && lat <= MAX_LAT_INCL;
Modified: lucene/dev/branches/branch_5x/lucene/sandbox/src/test/org/apache/lucene/bkdtree/TestBKDTree.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/sandbox/src/test/org/apache/lucene/bkdtree/TestBKDTree.java?rev=1710027&r1=1710026&r2=1710027&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/sandbox/src/test/org/apache/lucene/bkdtree/TestBKDTree.java (original)
+++ lucene/dev/branches/branch_5x/lucene/sandbox/src/test/org/apache/lucene/bkdtree/TestBKDTree.java Thu Oct 22 14:35:50 2015
@@ -21,580 +21,133 @@ import org.apache.lucene.codecs.Codec;
import org.apache.lucene.codecs.DocValuesFormat;
import org.apache.lucene.codecs.lucene53.Lucene53Codec;
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.search.TopDocs;
import org.apache.lucene.store.Directory;
+import org.apache.lucene.store.MockDirectoryWrapper;
import org.apache.lucene.util.Accountable;
import org.apache.lucene.util.Accountables;
-import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.BaseGeoPointTestCase;
+import org.apache.lucene.util.GeoRect;
import org.apache.lucene.util.IOUtils;
-import org.apache.lucene.util.LuceneTestCase.Nightly;
-import org.apache.lucene.util.LuceneTestCase;
+import org.apache.lucene.util.SloppyMath;
import org.apache.lucene.util.TestUtil;
-import org.junit.BeforeClass;
-import java.io.IOException;
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.HashSet;
-import java.util.List;
-import java.util.Set;
-import java.util.concurrent.CountDownLatch;
-import java.util.concurrent.atomic.AtomicBoolean;
-
-public class TestBKDTree extends LuceneTestCase {
-
- private static boolean smallBBox;
-
- @BeforeClass
- public static void beforeClass() {
- smallBBox = random().nextBoolean();
- }
-
- public void testAllLatEqual() throws Exception {
- int numPoints = atLeast(10000);
- double lat = randomLat();
- 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();
- haveRealDoc = true;
- if (VERBOSE) {
- System.out.println(" doc=" + docID + " lat=" + lat + " lon=" + lons[docID]);
- }
- }
- lats[docID] = lat;
- }
-
- verify(lats, lons);
- }
-
- public void testAllLonEqual() throws Exception {
- int numPoints = atLeast(10000);
- double theLon = randomLon();
- 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();
- haveRealDoc = true;
- if (VERBOSE) {
- System.out.println(" doc=" + docID + " lat=" + lats[docID] + " lon=" + theLon);
- }
- }
- lons[docID] = theLon;
- }
-
- verify(lats, lons);
- }
-
- public void testMultiValued() throws Exception {
- int numPoints = atLeast(10000);
- // Every doc has 2 points:
- double[] lats = new double[2*numPoints];
- double[] lons = new double[2*numPoints];
- Directory dir = newDirectory();
- IndexWriterConfig iwc = newIndexWriterConfig();
- // We rely on docID order:
- iwc.setMergePolicy(newLogMergePolicy());
- Codec codec = TestUtil.alwaysDocValuesFormat(getDocValuesFormat());
- iwc.setCodec(codec);
- RandomIndexWriter w = new RandomIndexWriter(random(), dir, iwc);
+// TODO: can test framework assert we don't leak temp files?
- for (int docID=0;docID<numPoints;docID++) {
- Document doc = new Document();
- lats[2*docID] = randomLat();
- lons[2*docID] = randomLon();
- doc.add(new BKDPointField("point", lats[2*docID], lons[2*docID]));
- lats[2*docID+1] = randomLat();
- lons[2*docID+1] = randomLon();
- doc.add(new BKDPointField("point", lats[2*docID+1], lons[2*docID+1]));
- w.addDocument(doc);
- }
-
- 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(100);
- for (int iter=0;iter<iters;iter++) {
- double lat0 = randomLat();
- double lat1 = randomLat();
- double lon0 = randomLon();
- double lon1 = randomLon();
-
- if (lat1 < lat0) {
- double x = lat0;
- lat0 = lat1;
- lat1 = x;
- }
-
- if (lon1 < lon0) {
- double x = lon0;
- lon0 = lon1;
- lon1 = x;
- }
-
- if (VERBOSE) {
- System.out.println("\nTEST: iter=" + iter + " lat=" + lat0 + " TO " + lat1 + " lon=" + lon0 + " TO " + lon1);
- }
-
- Query query = new BKDPointInBBoxQuery("point", lat0, lat1, lon0, lon1);
+public class TestBKDTree extends BaseGeoPointTestCase {
- 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);
- }
- });
-
- 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 expected = rectContainsPointEnc(lat0, lat1, lon0, lon1, latDoc1, lonDoc1) ||
- rectContainsPointEnc(lat0, lat1, lon0, lon1, latDoc2, lonDoc2);
-
- if (hits.get(docID) != expected) {
- fail("docID=" + docID + " latDoc1=" + latDoc1 + " lonDoc1=" + lonDoc1 + " latDoc2=" + latDoc2 + " lonDoc2=" + lonDoc2 + " expected " + expected + " but got: " + hits.get(docID));
- }
- }
- }
- r.close();
- dir.close();
+ @Override
+ protected void addPointToDoc(String field, Document doc, double lat, double lon) {
+ doc.add(new BKDPointField(field, lat, lon));
}
- // A particularly tricky adversary:
- public void testSamePointManyTimes() throws Exception {
- int numPoints = atLeast(1000);
-
- // Every doc has 2 points:
- double theLat = randomLat();
- double theLon = randomLon();
-
- double[] lats = new double[numPoints];
- Arrays.fill(lats, theLat);
-
- double[] lons = new double[numPoints];
- Arrays.fill(lons, theLon);
-
- verify(lats, lons);
+ @Override
+ protected Query newBBoxQuery(String field, GeoRect rect) {
+ return new BKDPointInBBoxQuery(field, rect.minLat, rect.maxLat, rect.minLon, rect.maxLon);
}
- public void testRandomTiny() throws Exception {
- // Make sure single-leaf-node case is OK:
- doTestRandom(10);
+ @Override
+ protected Query newDistanceQuery(String field, double centerLat, double centerLon, double radiusMeters) {
+ // return new BKDDistanceQuery(field, centerLat, centerLon, radiusMeters);
+ return null;
}
- public void testRandomMedium() throws Exception {
- doTestRandom(10000);
+ @Override
+ protected Query newDistanceRangeQuery(String field, double centerLat, double centerLon, double minRadiusMeters, double radiusMeters) {
+ return null;
}
- @Nightly
- public void testRandomBig() throws Exception {
- doTestRandom(200000);
+ @Override
+ protected Query newPolygonQuery(String field, double[] lats, double[] lons) {
+ return new BKDPointInPolygonQuery(FIELD_NAME, lats, lons);
}
- 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] = 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] = 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] = randomLat();
- lons[docID] = randomLon();
- haveRealDoc = true;
- if (VERBOSE) {
- System.out.println(" doc=" + docID + " lat=" + lats[docID] + " lon=" + lons[docID]);
- }
- }
- }
-
- verify(lats, lons);
- }
-
- private static final double TOLERANCE = 1e-7;
-
- private static void verify(final double[] lats, final 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);
- }
+ @Override
+ protected void initIndexWriterConfig(final String fieldName, IndexWriterConfig iwc) {
final DocValuesFormat dvFormat = getDocValuesFormat();
Codec codec = new Lucene53Codec() {
- @Override
- public DocValuesFormat getDocValuesFormatForField(String field) {
- if (field.equals("point")) {
- return dvFormat;
- } else {
- return super.getDocValuesFormatForField(field);
- }
- }
- };
- iwc.setCodec(codec);
- Directory dir;
- if (lats.length > 100000) {
- dir = newFSDirectory(createTempDir("TestBKDTree"));
- } else {
- dir = newDirectory();
- }
- final 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) {
- doc.add(new BKDPointField("point", 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);
+ @Override
+ public DocValuesFormat getDocValuesFormatForField(String field) {
+ if (field.equals(fieldName)) {
+ return dvFormat;
+ } else {
+ return super.getDocValuesFormatForField(field);
}
}
- }
- if (random().nextBoolean()) {
- w.forceMerge(1);
- }
- final IndexReader r = DirectoryReader.open(w, true);
- w.close();
-
- // We can't wrap with "exotic" readers because the BKD query must see the BKDDVFormat:
- final IndexSearcher s = newSearcher(r, false);
+ };
+ iwc.setCodec(codec);
+ }
- int numThreads = TestUtil.nextInt(random(), 2, 5);
+ @Override
+ protected Boolean rectContainsPoint(GeoRect rect, double pointLat, double pointLon) {
- List<Thread> threads = new ArrayList<>();
- final int iters = atLeast(100);
+ assert Double.isNaN(pointLat) == false;
- 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++) {
- double lat0 = randomLat();
- double lat1 = randomLat();
- double lon0 = randomLon();
- double lon1 = randomLon();
-
- if (lat1 < lat0) {
- double x = lat0;
- lat0 = lat1;
- lat1 = x;
- }
-
- boolean crossesDateLine;
- if (lon1 < lon0) {
- if (random().nextBoolean()) {
- double x = lon0;
- lon0 = lon1;
- lon1 = x;
- crossesDateLine = false;
- } else {
- crossesDateLine = true;
- }
- } else {
- crossesDateLine = false;
- }
-
- if (VERBOSE) {
- System.out.println("\nTEST: iter=" + iter + " lat=" + lat0 + " TO " + lat1 + " lon=" + lon0 + " TO " + lon1 + " crossesDateLine=" + crossesDateLine);
- }
-
- Query query;
- // TODO: get poly query working with dateline crossing too (how?)!
- if (crossesDateLine || random().nextBoolean()) {
- query = new BKDPointInBBoxQuery("point", lat0, lat1, lon0, lon1);
- } else {
- double[] lats = new double[5];
- double[] lons = new double[5];
- lats[0] = lat0;
- lons[0] = lon0;
- lats[1] = lat1;
- lons[1] = lon0;
- lats[2] = lat1;
- lons[2] = lon1;
- lats[3] = lat0;
- lons[3] = lon1;
- lats[4] = lat0;
- lons[4] = lon0;
- query = new BKDPointInPolygonQuery("point", lats, lons);
- }
-
- if (VERBOSE) {
- System.out.println(" using query: " + query);
- }
-
- 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);
- }
- });
-
- if (VERBOSE) {
- System.out.println(" hitCount: " + hits.cardinality());
- }
-
- for(int docID=0;docID<r.maxDoc();docID++) {
- int id = (int) docIDToID.get(docID);
- boolean expected = deleted.contains(id) == false && rectContainsPointEnc(lat0, lat1, lon0, lon1, lats[id], lons[id]);
- if (hits.get(docID) != expected) {
- if (query instanceof BKDPointInPolygonQuery &&
- (Math.abs(lat0-lats[id]) < TOLERANCE ||
- Math.abs(lat1-lats[id]) < TOLERANCE ||
- Math.abs(lon0-lons[id]) < TOLERANCE ||
- Math.abs(lon1-lons[id]) < TOLERANCE)) {
- // The poly check quantizes slightly differently, so we allow for boundary cases to disagree
- } else {
- // We do exact quantized comparison so the bbox query should never disagree:
- fail(Thread.currentThread().getName() + ": iter=" + iter + " id=" + id + " docID=" + docID + " lat=" + lats[id] + " lon=" + lons[id] + " (bbox: lat=" + lat0 + " TO " + lat1 + " lon=" + lon0 + " TO " + lon1 + ") expected " + expected + " but got: " + hits.get(docID) + " deleted?=" + deleted.contains(id) + " query=" + query + " crossesDateLine=" + crossesDateLine);
- }
- }
- }
- }
- }
- };
- thread.setName("T" + i);
- thread.start();
- threads.add(thread);
- }
- startingGun.countDown();
- for(Thread thread : threads) {
- thread.join();
- }
- IOUtils.close(r, dir);
- }
+ int rectLatMinEnc = BKDTreeWriter.encodeLat(rect.minLat);
+ int rectLatMaxEnc = BKDTreeWriter.encodeLat(rect.maxLat);
+ int rectLonMinEnc = BKDTreeWriter.encodeLon(rect.minLon);
+ int rectLonMaxEnc = BKDTreeWriter.encodeLon(rect.maxLon);
- private static boolean rectContainsPointEnc(double rectLatMin, double rectLatMax,
- double rectLonMin, double rectLonMax,
- double pointLat, double pointLon) {
- if (Double.isNaN(pointLat)) {
- return false;
- }
- int rectLatMinEnc = BKDTreeWriter.encodeLat(rectLatMin);
- int rectLatMaxEnc = BKDTreeWriter.encodeLat(rectLatMax);
- int rectLonMinEnc = BKDTreeWriter.encodeLon(rectLonMin);
- int rectLonMaxEnc = BKDTreeWriter.encodeLon(rectLonMax);
int pointLatEnc = BKDTreeWriter.encodeLat(pointLat);
int pointLonEnc = BKDTreeWriter.encodeLon(pointLon);
- if (rectLonMin < rectLonMax) {
+ if (rect.minLon < rect.maxLon) {
return pointLatEnc >= rectLatMinEnc &&
- pointLatEnc < rectLatMaxEnc &&
- pointLonEnc >= rectLonMinEnc &&
- pointLonEnc < rectLonMaxEnc;
+ pointLatEnc < rectLatMaxEnc &&
+ pointLonEnc >= rectLonMinEnc &&
+ pointLonEnc < rectLonMaxEnc;
} else {
// Rect crosses dateline:
return pointLatEnc >= rectLatMinEnc &&
- pointLatEnc < rectLatMaxEnc &&
- (pointLonEnc >= rectLonMinEnc ||
- pointLonEnc < rectLonMaxEnc);
+ pointLatEnc < rectLatMaxEnc &&
+ (pointLonEnc >= rectLonMinEnc ||
+ pointLonEnc < rectLonMaxEnc);
}
}
- private static double randomLat() {
- if (smallBBox) {
- return 2.0 * (random().nextDouble()-0.5);
+ private static final double POLY_TOLERANCE = 1e-7;
+
+ @Override
+ protected Boolean polyRectContainsPoint(GeoRect rect, double pointLat, double pointLon) {
+ if (Math.abs(rect.minLat-pointLat) < POLY_TOLERANCE ||
+ Math.abs(rect.maxLat-pointLat) < POLY_TOLERANCE ||
+ Math.abs(rect.minLon-pointLon) < POLY_TOLERANCE ||
+ Math.abs(rect.maxLon-pointLon) < POLY_TOLERANCE) {
+ // The poly check quantizes slightly differently, so we allow for boundary cases to disagree
+ return null;
} else {
- return -90 + 180.0 * random().nextDouble();
+ return rectContainsPoint(rect, pointLat, pointLon);
}
}
- private static double randomLon() {
- if (smallBBox) {
- return 2.0 * (random().nextDouble()-0.5);
- } else {
- return -180 + 360.0 * random().nextDouble();
- }
+ @Override
+ protected Boolean circleContainsPoint(double centerLat, double centerLon, double radiusMeters, double pointLat, double pointLon) {
+ double distanceKM = SloppyMath.haversin(centerLat, centerLon, pointLat, pointLon);
+ boolean result = distanceKM*1000.0 <= radiusMeters;
+ //System.out.println(" shouldMatch? centerLon=" + centerLon + " centerLat=" + centerLat + " pointLon=" + pointLon + " pointLat=" + pointLat + " result=" + result + " distanceMeters=" + (distanceKM * 1000));
+ return result;
+ }
+
+ @Override
+ protected Boolean distanceRangeContainsPoint(double centerLat, double centerLon, double minRadiusMeters, double radiusMeters, double pointLat, double pointLon) {
+ final double d = SloppyMath.haversin(centerLat, centerLon, pointLat, pointLon)*1000.0;
+ return d >= minRadiusMeters && d <= radiusMeters;
}
public void testEncodeDecode() throws Exception {
int iters = atLeast(10000);
+ boolean small = random().nextBoolean();
for(int iter=0;iter<iters;iter++) {
- double lat = randomLat();
+ double lat = randomLat(small);
double latQuantized = BKDTreeWriter.decodeLat(BKDTreeWriter.encodeLat(lat));
assertEquals(lat, latQuantized, BKDTreeWriter.TOLERANCE);
- double lon = randomLon();
+ double lon = randomLon(small);
double lonQuantized = BKDTreeWriter.decodeLon(BKDTreeWriter.encodeLon(lon));
assertEquals(lon, lonQuantized, BKDTreeWriter.TOLERANCE);
}
@@ -609,20 +162,19 @@ public class TestBKDTree extends LuceneT
}
public void testAccountableHasDelegate() throws Exception {
- Directory dir = newDirectory();
+ Directory dir = getDirectory();
IndexWriterConfig iwc = newIndexWriterConfig();
- Codec codec = TestUtil.alwaysDocValuesFormat(getDocValuesFormat());
- iwc.setCodec(codec);
+ iwc.setCodec(TestUtil.alwaysDocValuesFormat(getDocValuesFormat()));
RandomIndexWriter w = new RandomIndexWriter(random(), dir, iwc);
Document doc = new Document();
- doc.add(new BKDPointField("field", -18.2861, 147.7));
+ doc.add(new BKDPointField(FIELD_NAME, -18.2861, 147.7));
w.addDocument(doc);
IndexReader r = w.getReader();
// We can't wrap with "exotic" readers because the BKD query must see the BKDDVFormat:
IndexSearcher s = newSearcher(r, false);
// Need to run a query so the DV field is really loaded:
- TopDocs hits = s.search(new BKDPointInBBoxQuery("field", -30, 0, 140, 150), 1);
+ TopDocs hits = s.search(new BKDPointInBBoxQuery(FIELD_NAME, -30, 0, 140, 150), 1);
assertEquals(1, hits.totalHits);
assertTrue(Accountables.toString((Accountable) r.leaves().get(0).reader()).contains("delegate"));
IOUtils.close(r, w, dir);
@@ -631,6 +183,20 @@ public class TestBKDTree extends LuceneT
private static DocValuesFormat getDocValuesFormat() {
int maxPointsInLeaf = TestUtil.nextInt(random(), 16, 2048);
int maxPointsSortInHeap = TestUtil.nextInt(random(), maxPointsInLeaf, 1024*1024);
+ if (VERBOSE) {
+ System.out.println(" BKD params: maxPointsInLeaf=" + maxPointsInLeaf + " maxPointsSortInHeap=" + maxPointsSortInHeap);
+ }
return new BKDTreeDocValuesFormat(maxPointsInLeaf, maxPointsSortInHeap);
}
+
+ private static Directory noVirusChecker(Directory dir) {
+ if (dir instanceof MockDirectoryWrapper) {
+ ((MockDirectoryWrapper) dir).setEnableVirusScanner(false);
+ }
+ return dir;
+ }
+
+ private static Directory getDirectory() {
+ return noVirusChecker(newDirectory());
+ }
}