You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by mi...@apache.org on 2015/07/18 03:05:26 UTC
svn commit: r1691660 - in /lucene/dev/branches/branch_5x: ./ lucene/
lucene/sandbox/ lucene/sandbox/src/java/org/apache/lucene/document/
lucene/sandbox/src/java/org/apache/lucene/search/
lucene/sandbox/src/java/org/apache/lucene/util/ lucene/sandbox/sr...
Author: mikemccand
Date: Sat Jul 18 01:05:25 2015
New Revision: 1691660
URL: http://svn.apache.org/r1691660
Log:
LUCENE-6547: add GeoPointDistanceQuery and fix GeoPointInBBoxQuery to handle dateline crossing
Added:
lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceQuery.java
- copied, changed from r1691659, lucene/dev/trunk/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
- copied unchanged from r1691659, lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceQueryImpl.java
lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInBBoxQueryImpl.java
- copied unchanged from r1691659, lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInBBoxQueryImpl.java
lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointTermQuery.java
- copied unchanged from r1691659, lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointTermQuery.java
lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoDistanceUtils.java
- copied unchanged from r1691659, lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/util/GeoDistanceUtils.java
lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoProjectionUtils.java
- copied unchanged from r1691659, lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/util/GeoProjectionUtils.java
Modified:
lucene/dev/branches/branch_5x/ (props changed)
lucene/dev/branches/branch_5x/lucene/ (props changed)
lucene/dev/branches/branch_5x/lucene/CHANGES.txt (contents, props changed)
lucene/dev/branches/branch_5x/lucene/sandbox/ (props changed)
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/GeoPointInBBoxQuery.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/GeoUtils.java
lucene/dev/branches/branch_5x/lucene/sandbox/src/test/org/apache/lucene/search/TestGeoPointQuery.java
Modified: lucene/dev/branches/branch_5x/lucene/CHANGES.txt
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/CHANGES.txt?rev=1691660&r1=1691659&r2=1691660&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/CHANGES.txt (original)
+++ lucene/dev/branches/branch_5x/lucene/CHANGES.txt Sat Jul 18 01:05:25 2015
@@ -95,6 +95,10 @@ New Features
* LUCENE-6659: Remove IndexWriter's unnecessary hard limit on max concurrency
(Robert Muir, Mike McCandless)
+* LUCENE-6547: Add GeoPointDistanceQuery, matching all points within
+ the specified distance from the center point. Fix
+ GeoPointInBBoxQuery to handle dateline crossing.
+
API Changes
* LUCENE-6508: Simplify Lock api, there is now just
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=1691660&r1=1691659&r2=1691660&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 Sat Jul 18 01:05:25 2015
@@ -32,7 +32,8 @@ import org.apache.lucene.util.GeoUtils;
* </pre>
*
* <p>To perform simple geospatial queries against a <code>GeoPointField</code>,
- * see {@link org.apache.lucene.search.GeoPointInBBoxQuery} or {@link org.apache.lucene.search.GeoPointInPolygonQuery}
+ * see {@link org.apache.lucene.search.GeoPointInBBoxQuery}, {@link org.apache.lucene.search.GeoPointInPolygonQuery},
+ * or {@link org.apache.lucene.search.GeoPointDistanceQuery}
*
* NOTE: This indexes only high precision encoded terms which may result in visiting a high number
* of terms for large queries. See LUCENE-6481 for a future improvement.
Copied: lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceQuery.java (from r1691659, lucene/dev/trunk/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?p2=lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceQuery.java&p1=lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointDistanceQuery.java&r1=1691659&r2=1691660&rev=1691660&view=diff
==============================================================================
--- lucene/dev/trunk/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 Sat Jul 18 01:05:25 2015
@@ -72,17 +72,17 @@ public final class GeoPointDistanceQuery
@Override
public Query rewrite(IndexReader reader) {
if (maxLon < minLon) {
- BooleanQuery.Builder bqb = new BooleanQuery.Builder();
+ BooleanQuery bq = new BooleanQuery();
GeoPointDistanceQueryImpl left = new GeoPointDistanceQueryImpl(field, this, new GeoBoundingBox(-180.0D, maxLon,
minLat, maxLat));
left.setBoost(getBoost());
- bqb.add(new BooleanClause(left, BooleanClause.Occur.SHOULD));
+ bq.add(new BooleanClause(left, BooleanClause.Occur.SHOULD));
GeoPointDistanceQueryImpl right = new GeoPointDistanceQueryImpl(field, this, new GeoBoundingBox(minLon, 180.0D,
minLat, maxLat));
right.setBoost(getBoost());
- bqb.add(new BooleanClause(right, BooleanClause.Occur.SHOULD));
- return bqb.build();
+ bq.add(new BooleanClause(right, BooleanClause.Occur.SHOULD));
+ return bq;
}
return new GeoPointDistanceQueryImpl(field, this, new GeoBoundingBox(this.minLon, this.maxLon, this.minLat, this.maxLat));
}
Modified: lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInBBoxQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInBBoxQuery.java?rev=1691660&r1=1691659&r2=1691660&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInBBoxQuery.java (original)
+++ lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInBBoxQuery.java Sat Jul 18 01:05:25 2015
@@ -17,12 +17,7 @@ package org.apache.lucene.search;
* limitations under the License.
*/
-import java.io.IOException;
-
-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.index.IndexReader;
import org.apache.lucene.util.ToStringUtils;
/** Implements a simple bounding box query on a GeoPoint field. This is inspired by
@@ -44,57 +39,65 @@ import org.apache.lucene.util.ToStringUt
*
* @lucene.experimental
*/
-public class GeoPointInBBoxQuery extends MultiTermQuery {
- // simple bounding box optimization - no objects used to avoid dependencies
+public class GeoPointInBBoxQuery extends Query {
+ protected final String field;
protected final double minLon;
protected final double minLat;
protected final double maxLon;
protected final double maxLat;
- /**
- * Constructs a new GeoBBoxQuery that will match encoded GeoPoint terms that fall within or on the boundary
- * of the bounding box defined by the input parameters
- * @param field the field name
- * @param minLon lower longitude (x) value of the bounding box
- * @param minLat lower latitude (y) value of the bounding box
- * @param maxLon upper longitude (x) value of the bounding box
- * @param maxLat upper latitude (y) value of the bounding box
- */
public GeoPointInBBoxQuery(final String field, final double minLon, final double minLat, final double maxLon, final double maxLat) {
- super(field);
- 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.field = field;
this.minLon = minLon;
this.minLat = minLat;
this.maxLon = maxLon;
this.maxLat = maxLat;
}
- @Override @SuppressWarnings("unchecked")
- protected TermsEnum getTermsEnum(final Terms terms, AttributeSource atts) throws IOException {
- final Long min = GeoUtils.mortonHash(minLon, minLat);
- final Long max = Math.abs(GeoUtils.mortonHash(maxLon, maxLat));
- if (min != null && max != null && min.compareTo(max) > 0) {
- return TermsEnum.EMPTY;
+ @Override
+ public Query rewrite(IndexReader reader) {
+ if (maxLon < minLon) {
+ BooleanQuery bq = new BooleanQuery();
+
+ GeoPointInBBoxQueryImpl left = new GeoPointInBBoxQueryImpl(field, -180.0D, minLat, maxLon, maxLat);
+ left.setBoost(getBoost());
+ bq.add(new BooleanClause(left, BooleanClause.Occur.SHOULD));
+ GeoPointInBBoxQueryImpl right = new GeoPointInBBoxQueryImpl(field, minLon, minLat, 180.0D, maxLat);
+ right.setBoost(getBoost());
+ bq.add(new BooleanClause(right, BooleanClause.Occur.SHOULD));
+ return bq;
+ }
+ return new GeoPointInBBoxQueryImpl(field, minLon, minLat, maxLon, maxLat);
+ }
+
+ @Override
+ public String toString(String field) {
+ final StringBuilder sb = new StringBuilder();
+ sb.append(getClass().getSimpleName());
+ sb.append(':');
+ if (!this.field.equals(field)) {
+ sb.append(" field=");
+ sb.append(this.field);
+ sb.append(':');
}
- return new GeoPointTermsEnum(terms.iterator(), atts, minLon, minLat, maxLon, maxLat);
+ return sb.append(" Lower Left: [")
+ .append(minLon)
+ .append(',')
+ .append(minLat)
+ .append(']')
+ .append(" Upper Right: [")
+ .append(maxLon)
+ .append(',')
+ .append(maxLat)
+ .append("]")
+ .append(ToStringUtils.boost(getBoost()))
+ .toString();
}
@Override
- @SuppressWarnings({"unchecked","rawtypes"})
public boolean equals(Object o) {
if (this == o) return true;
- if (o == null || getClass() != o.getClass()) return false;
+ if (!(o instanceof GeoPointInBBoxQuery)) return false;
if (!super.equals(o)) return false;
GeoPointInBBoxQuery that = (GeoPointInBBoxQuery) o;
@@ -103,6 +106,7 @@ public class GeoPointInBBoxQuery extends
if (Double.compare(that.maxLon, maxLon) != 0) return false;
if (Double.compare(that.minLat, minLat) != 0) return false;
if (Double.compare(that.minLon, minLon) != 0) return false;
+ if (!field.equals(that.field)) return false;
return true;
}
@@ -111,6 +115,7 @@ public class GeoPointInBBoxQuery extends
public int hashCode() {
int result = super.hashCode();
long temp;
+ result = 31 * result + field.hashCode();
temp = Double.doubleToLongBits(minLon);
result = 31 * result + (int) (temp ^ (temp >>> 32));
temp = Double.doubleToLongBits(minLat);
@@ -122,27 +127,23 @@ public class GeoPointInBBoxQuery extends
return result;
}
- @Override
- public String toString(String field) {
- final StringBuilder sb = new StringBuilder();
- sb.append(getClass().getSimpleName());
- sb.append(':');
- if (!getField().equals(field)) {
- sb.append(" field=");
- sb.append(getField());
- sb.append(':');
- }
- return sb.append(" Lower Left: [")
- .append(minLon)
- .append(',')
- .append(minLat)
- .append(']')
- .append(" Upper Right: [")
- .append(maxLon)
- .append(',')
- .append(maxLat)
- .append("]")
- .append(ToStringUtils.boost(getBoost()))
- .toString();
+ public final String getField() {
+ return this.field;
+ }
+
+ public final double getMinLon() {
+ return this.minLon;
+ }
+
+ public final double getMinLat() {
+ return this.minLat;
+ }
+
+ public final double getMaxLon() {
+ return this.maxLon;
+ }
+
+ public final double getMaxLat() {
+ return this.maxLat;
}
}
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=1691660&r1=1691659&r2=1691660&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 Sat Jul 18 01:05:25 2015
@@ -29,8 +29,8 @@ import java.io.IOException;
import java.util.Arrays;
/** Implements a simple point in polygon query on a GeoPoint field. This is based on
- * {@link GeoPointInBBoxQuery} and is implemented using a
- * three phase approach. First, like {@link GeoPointInBBoxQuery}
+ * {@code GeoPointInBBoxQueryImpl} and is implemented using a
+ * three phase approach. First, like {@code GeoPointInBBoxQueryImpl}
* candidate terms are queried using a numeric range based on the morton codes
* of the min and max lat/lon pairs. Terms passing this initial filter are passed
* to a secondary filter that verifies whether the decoded lat/lon point falls within
@@ -47,7 +47,7 @@ import java.util.Arrays;
*
* @lucene.experimental
*/
-public final class GeoPointInPolygonQuery extends GeoPointInBBoxQuery {
+public final class GeoPointInPolygonQuery extends GeoPointInBBoxQueryImpl {
// polygon position arrays - this avoids the use of any objects or
// or geo library dependencies
private final double[] x;
@@ -61,27 +61,6 @@ public final class GeoPointInPolygonQuer
this(field, computeBBox(polyLons, polyLats), polyLons, polyLats);
}
- /**
- * Expert: constructs a new GeoPolygonQuery that will match encoded {@link org.apache.lucene.document.GeoPointField} terms
- * that fall within or on the boundary of the polygon defined by the input parameters. This constructor requires a
- * precomputed bounding box. As an alternative, {@link #GeoPointInPolygonQuery(String,double[],double[])} can
- * be used to compute the bounding box during construction
- *
- * @param field the field name
- * @param minLon lower longitude (x) value of the bounding box optimizer
- * @param minLat lower latitude (y) value of the bounding box optimizer
- * @param maxLon upper longitude (x) value of the bounding box optimizer
- * @param maxLat upper latitude (y) value of the bounding box optimizer
- * @param polyLons array containing all longitude values for the polygon
- * @param polyLats array containing all latitude values for the polygon
- */
- public GeoPointInPolygonQuery(final String field, final double minLon, final double minLat, final double maxLon,
- final double maxLat, final double[] polyLons, final double[] polyLats) {
- // TODO: should we remove this? It's dangerous .. app could accidentally provide too-small bbox?
- // we should at least verify that bbox does in fact fully contain the poly?
- this(field, new GeoBoundingBox(minLon, maxLon, minLat, maxLat), polyLons, polyLats);
- }
-
/** Common constructor, used only internally. */
private GeoPointInPolygonQuery(final String field, GeoBoundingBox bbox, final double[] polyLons, final double[] polyLats) {
super(field, bbox.minLon, bbox.minLat, bbox.maxLon, bbox.maxLat);
@@ -112,16 +91,16 @@ public final class GeoPointInPolygonQuer
@Override @SuppressWarnings("unchecked")
protected TermsEnum getTermsEnum(final Terms terms, AttributeSource atts) throws IOException {
- final Long min = GeoUtils.mortonHash(minLon, minLat);
- final Long max = Math.abs(GeoUtils.mortonHash(maxLon, maxLat));
- if (min != null && max != null && min.compareTo(max) > 0) {
- return TermsEnum.EMPTY;
- }
- return new GeoPolygonTermsEnum(terms.iterator(), atts, minLon, minLat, maxLon, maxLat);
+ return new GeoPolygonTermsEnum(terms.iterator(), this.minLon, this.minLat, this.maxLon, this.maxLat);
}
@Override
- public final boolean equals(Object o) {
+ public void setRewriteMethod(RewriteMethod method) {
+ throw new UnsupportedOperationException("cannot change rewrite method");
+ }
+
+ @Override
+ public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
if (!super.equals(o)) return false;
@@ -135,7 +114,7 @@ public final class GeoPointInPolygonQuer
}
@Override
- public final int hashCode() {
+ public int hashCode() {
int result = super.hashCode();
result = 31 * result + (x != null ? Arrays.hashCode(x) : 0);
result = 31 * result + (y != null ? Arrays.hashCode(y) : 0);
@@ -167,10 +146,14 @@ public final class GeoPointInPolygonQuer
return sb.toString();
}
+ /**
+ * Custom {@link org.apache.lucene.index.TermsEnum} that computes morton hash ranges based on the defined edges of
+ * the provided polygon.
+ */
private final class GeoPolygonTermsEnum extends GeoPointTermsEnum {
- GeoPolygonTermsEnum(final TermsEnum tenum, AttributeSource atts, final double minLon, final double minLat,
+ GeoPolygonTermsEnum(final TermsEnum tenum, final double minLon, final double minLat,
final double maxLon, final double maxLat) {
- super(tenum, atts, minLon, minLat, maxLon, maxLat);
+ super(tenum, minLon, minLat, maxLon, maxLat);
}
@Override
@@ -202,7 +185,7 @@ public final class GeoPointInPolygonQuer
* @return match status
*/
@Override
- protected final AcceptStatus accept(BytesRef term) {
+ protected AcceptStatus accept(BytesRef term) {
// first filter by bounding box
AcceptStatus status = super.accept(term);
assert status != AcceptStatus.YES_AND_SEEK;
@@ -247,4 +230,20 @@ public final class GeoPointInPolygonQuer
return new GeoBoundingBox(minLon, maxLon, minLat, maxLat);
}
+
+ /**
+ * API utility method for returning the array of longitudinal values for this GeoPolygon
+ * The returned array is not a copy so do not change it!
+ */
+ public double[] getLons() {
+ return this.x;
+ }
+
+ /**
+ * API utility method for returning the array of latitudinal values for this GeoPolygon
+ * The returned array is not a copy so do not change it!
+ */
+ public double[] getLats() {
+ return this.y;
+ }
}
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=1691660&r1=1691659&r2=1691660&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 Sat Jul 18 01:05:25 2015
@@ -21,14 +21,9 @@ import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
-import org.apache.lucene.analysis.tokenattributes.TermToBytesRefAttribute;
import org.apache.lucene.document.GeoPointField;
import org.apache.lucene.index.FilteredTermsEnum;
import org.apache.lucene.index.TermsEnum;
-import org.apache.lucene.util.Attribute;
-import org.apache.lucene.util.AttributeImpl;
-import org.apache.lucene.util.AttributeReflector;
-import org.apache.lucene.util.AttributeSource;
import org.apache.lucene.util.BytesRef;
import org.apache.lucene.util.BytesRefBuilder;
import org.apache.lucene.util.GeoUtils;
@@ -47,13 +42,11 @@ class GeoPointTermsEnum extends Filtered
private Range currentRange;
private BytesRef currentLowerBound, currentUpperBound;
- private final ComputedRangesAttribute rangesAtt;
+ private final List<Range> rangeBounds = new LinkedList<>();
- private final LinkedList<Range> rangeBounds;
+ protected static final short DETAIL_LEVEL = 16;
- private static final short DETAIL_LEVEL = 16;
-
- GeoPointTermsEnum(final TermsEnum tenum, AttributeSource atts, final double minLon, final double minLat,
+ GeoPointTermsEnum(final TermsEnum tenum, final double minLon, final double minLat,
final double maxLon, final double maxLat) {
super(tenum);
final long rectMinHash = GeoUtils.mortonHash(minLon, minLat);
@@ -63,13 +56,8 @@ class GeoPointTermsEnum extends Filtered
this.maxLon = GeoUtils.mortonUnhashLon(rectMaxHash);
this.maxLat = GeoUtils.mortonUnhashLat(rectMaxHash);
- this.rangesAtt = atts.addAttribute(ComputedRangesAttribute.class);
- this.rangeBounds = rangesAtt.ranges();
-
- if (rangeBounds.isEmpty()) {
- computeRange(0L, (short) (((GeoUtils.BITS) << 1) - 1));
- Collections.sort(rangeBounds);
- }
+ computeRange(0L, (short) (((GeoUtils.BITS) << 1) - 1));
+ Collections.sort(rangeBounds);
}
/**
@@ -100,9 +88,7 @@ class GeoPointTermsEnum extends Filtered
final short level = (short)(62-res>>>1);
- // if cell is within and a factor of the precision step, add the range
- // if cell cellCrosses
-
+ // 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 && cellCrosses(minLon, minLat, maxLon, maxLat))) {
rangeBounds.add(new Range(start, end, res, level, !within));
@@ -124,7 +110,7 @@ class GeoPointTermsEnum extends Filtered
}
private void nextRange() {
- currentRange = rangeBounds.removeFirst();
+ currentRange = rangeBounds.remove(0);
currentLowerBound = currentRange.lower;
assert currentUpperBound == null || currentUpperBound.compareTo(currentRange.lower) <= 0 :
"The current upper bound must be <= the new lower bound";
@@ -169,11 +155,13 @@ class GeoPointTermsEnum extends Filtered
protected AcceptStatus accept(BytesRef term) {
// validate value is in range
while (currentUpperBound == null || term.compareTo(currentUpperBound) > 0) {
- if (rangeBounds.isEmpty())
+ if (rangeBounds.isEmpty()) {
return AcceptStatus.END;
+ }
// peek next sub-range, only seek if the current term is smaller than next lower bound
- if (term.compareTo(rangeBounds.getFirst().lower) < 0)
+ if (term.compareTo(rangeBounds.get(0).lower) < 0) {
return AcceptStatus.NO_AND_SEEK;
+ }
// step forward to next range without seeking, as next lower range bound is less or equal current term
nextRange();
}
@@ -190,62 +178,10 @@ class GeoPointTermsEnum extends Filtered
return AcceptStatus.YES;
}
- public static interface ComputedRangesAttribute extends Attribute {
- public LinkedList<Range> ranges();
- }
-
- @SuppressWarnings({"unchecked","rawtypes"})
- public static final class ComputedRangesAttributeImpl extends AttributeImpl implements ComputedRangesAttribute {
- public final LinkedList<Range> rangeBounds = new LinkedList();
-
- @Override
- public LinkedList<Range> ranges() {
- return rangeBounds;
- }
-
- @Override
- public void clear() {
- rangeBounds.clear();
- }
-
- @Override
- public int hashCode() {
- return rangeBounds.hashCode();
- }
-
- @Override
- public boolean equals(Object other) {
- if (this == other)
- return true;
- if (!(other instanceof ComputedRangesAttributeImpl))
- return false;
- return rangeBounds.equals(((ComputedRangesAttributeImpl)other).rangeBounds);
- }
-
- @Override
- public void copyTo(AttributeImpl target) {
- final List<Range> targetRanges = ((ComputedRangesAttribute)target).ranges();
- targetRanges.clear();
- targetRanges.addAll(rangeBounds);
- }
-
- @Override
- public AttributeImpl clone() {
- ComputedRangesAttributeImpl c = (ComputedRangesAttributeImpl) super.clone();;
- copyTo(c);
- return c;
- }
-
- @Override
- public void reflectWith(AttributeReflector reflector) {
- reflector.reflect(ComputedRangesAttribute.class, "rangeBounds", rangeBounds);
- }
- }
-
/**
* Internal class to represent a range along the space filling curve
*/
- private final class Range implements Comparable<Range> {
+ protected final class Range implements Comparable<Range> {
final BytesRef lower;
final BytesRef upper;
final short level;
@@ -263,7 +199,7 @@ class GeoPointTermsEnum extends Filtered
}
@Override
- public final int compareTo(Range other) {
+ public int compareTo(Range other) {
return this.lower.compareTo(other.lower);
}
}
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=1691660&r1=1691659&r2=1691660&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 Sat Jul 18 01:05:25 2015
@@ -17,21 +17,14 @@ package org.apache.lucene.util;
* limitations under the License.
*/
+import java.util.ArrayList;
+
/**
* Basic reusable geo-spatial utility methods
*
* @lucene.experimental
*/
public final class GeoUtils {
- // WGS84 earth-ellipsoid major (a) minor (b) radius, (f) flattening and eccentricity (e)
- private static final double SEMIMAJOR_AXIS = 6_378_137; // [m]
- private static final double FLATTENING = 1.0/298.257223563;
- private static final double SEMIMINOR_AXIS = SEMIMAJOR_AXIS * (1.0 - FLATTENING); //6_356_752.31420; // [m]
- private static final double ECCENTRICITY = StrictMath.sqrt((2.0 - FLATTENING) * FLATTENING);
- private static final double PI_OVER_2 = StrictMath.PI / 2.0D;
- private static final double SEMIMAJOR_AXIS2 = SEMIMAJOR_AXIS * SEMIMINOR_AXIS;
- private static final double SEMIMINOR_AXIS2 = SEMIMINOR_AXIS * SEMIMINOR_AXIS;
-
private static final short MIN_LON = -180;
private static final short MIN_LAT = -90;
public static final short BITS = 31;
@@ -55,15 +48,15 @@ public final class GeoUtils {
private GeoUtils() {
}
- public static final Long mortonHash(final double lon, final double lat) {
+ public static Long mortonHash(final double lon, final double lat) {
return BitUtil.interleave(scaleLon(lon), scaleLat(lat));
}
- public static final double mortonUnhashLon(final long hash) {
+ public static double mortonUnhashLon(final long hash) {
return unscaleLon(BitUtil.deinterleave(hash));
}
- public static final double mortonUnhashLat(final long hash) {
+ public static double mortonUnhashLat(final long hash) {
return unscaleLat(BitUtil.deinterleave(hash >>> 1));
}
@@ -83,124 +76,43 @@ public final class GeoUtils {
return (val / LAT_SCALE) + MIN_LAT;
}
- public static final double compare(final double v1, final double v2) {
+ public static double compare(final double v1, final double v2) {
final double compare = v1-v2;
return Math.abs(compare) <= TOLERANCE ? 0 : compare;
}
- public static final boolean bboxContains(final double lon, final double lat, final double minLon,
- final double minLat, final double maxLon, final double maxLat) {
- return (compare(lon, minLon) >= 0 && compare(lon, maxLon) <= 0
- && compare(lat, minLat) >= 0 && compare(lat, maxLat) <= 0);
- }
-
/**
- * Converts from geodesic lon lat alt to geocentric earth-centered earth-fixed
- * @param lon geodesic longitude
- * @param lat geodesic latitude
- * @param alt geodesic altitude
- * @param ecf reusable earth-centered earth-fixed result
- * @return either a new ecef array or the reusable ecf parameter
- */
- public static final double[] llaToECF(double lon, double lat, double alt, double[] ecf) {
- lon = StrictMath.toRadians(lon);
- lat = StrictMath.toRadians(lat);
-
- final double sl = StrictMath.sin(lat);
- final double s2 = sl*sl;
- final double cl = StrictMath.cos(lat);
- final double ge2 = (SEMIMAJOR_AXIS2 - SEMIMINOR_AXIS2)/(SEMIMAJOR_AXIS2);
-
- if (ecf == null)
- ecf = new double[3];
-
- if (lat < -PI_OVER_2 && lat > -1.001D * PI_OVER_2) {
- lat = -PI_OVER_2;
- } else if (lat > PI_OVER_2 && lat < 1.001D * PI_OVER_2) {
- lat = PI_OVER_2;
+ * 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
}
- assert ((lat >= -PI_OVER_2) || (lat <= PI_OVER_2));
-
- if (lon > StrictMath.PI) {
- lon -= (2*StrictMath.PI);
+ 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;
}
-
- final double rn = SEMIMAJOR_AXIS / StrictMath.sqrt(1.0D - ge2 * s2);
- ecf[0] = (rn+alt) * cl * StrictMath.cos(lon);
- ecf[1] = (rn+alt) * cl * StrictMath.sin(lon);
- ecf[2] = ((rn*(1.0-ge2))+alt)*sl;
-
- return ecf;
}
/**
- * Converts from geocentric earth-centered earth-fixed to geodesic lat/lon/alt
- * @param x Cartesian x coordinate
- * @param y Cartesian y coordinate
- * @param z Cartesian z coordinate
- * @param lla 0: longitude 1: latitude: 2: altitude
- * @return double array as 0: longitude 1: latitude 2: altitude
- */
- public static final double[] ecfToLLA(final double x, final double y, final double z, double[] lla) {
- boolean atPole = false;
- final double ad_c = 1.0026000D;
- final double e2 = (SEMIMAJOR_AXIS2 - SEMIMINOR_AXIS2)/(SEMIMAJOR_AXIS2);
- final double ep2 = (SEMIMAJOR_AXIS2 - SEMIMINOR_AXIS2)/(SEMIMINOR_AXIS2);
- final double cos67P5 = 0.38268343236508977D;
-
- if (lla == null)
- lla = new double[3];
-
- if (x != 0.0) {
- lla[0] = StrictMath.atan2(y,x);
- } else {
- if (y > 0) {
- lla[0] = PI_OVER_2;
- } else if (y < 0) {
- lla[0] = -PI_OVER_2;
- } else {
- atPole = true;
- lla[0] = 0.0D;
- if (z > 0.0) {
- lla[1] = PI_OVER_2;
- } else if (z < 0.0) {
- lla[1] = -PI_OVER_2;
- } else {
- lla[1] = PI_OVER_2;
- lla[2] = -SEMIMINOR_AXIS;
- return lla;
- }
- }
- }
-
- final double w2 = x*x + y*y;
- final double w = StrictMath.sqrt(w2);
- final double t0 = z * ad_c;
- final double s0 = StrictMath.sqrt(t0 * t0 + w2);
- final double sinB0 = t0 / s0;
- final double cosB0 = w / s0;
- final double sin3B0 = sinB0 * sinB0 * sinB0;
- final double t1 = z + SEMIMINOR_AXIS * ep2 * sin3B0;
- final double sum = w - SEMIMAJOR_AXIS * e2 * cosB0 * cosB0 * cosB0;
- final double s1 = StrictMath.sqrt(t1 * t1 + sum * sum);
- final double sinP1 = t1 / s1;
- final double cosP1 = sum / s1;
- final double rn = SEMIMAJOR_AXIS / StrictMath.sqrt(1.0D - e2 * sinP1 * sinP1);
-
- if (cosP1 >= cos67P5) {
- lla[2] = w / cosP1 - rn;
- } else if (cosP1 <= -cos67P5) {
- lla[2] = w / -cosP1 - rn;
- } else {
- lla[2] = z / sinP1 + rn * (e2 - 1.0);
- }
- if (!atPole) {
- lla[1] = StrictMath.atan(sinP1/cosP1);
+ * 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
}
- lla[0] = StrictMath.toDegrees(lla[0]);
- lla[1] = StrictMath.toDegrees(lla[1]);
+ double off = Math.abs((lat_deg + 90) % 360);
+ return (off <= 180 ? off : 360-off) - 90;
+ }
- return lla;
+ public static final boolean bboxContains(final double lon, final double lat, final double minLon,
+ final double minLat, final double maxLon, final double maxLat) {
+ return (compare(lon, minLon) >= 0 && compare(lon, maxLon) <= 0
+ && compare(lat, minLat) >= 0 && compare(lat, maxLat) <= 0);
}
/**
@@ -236,8 +148,9 @@ public final class GeoUtils {
for (int i = 0; i < numberOfLeadingZeros; i++) {
s.append('0');
}
- if (term != 0)
+ if (term != 0) {
s.append(Long.toBinaryString(term));
+ }
return s.toString();
}
@@ -280,13 +193,14 @@ public final class GeoUtils {
/**
* Computes whether a rectangle crosses a shape. (touching not allowed)
*/
- public static final boolean rectCrossesPoly(final double rMinX, final double rMinY, final double rMaxX,
- final double rMaxY, final double[] shapeX, final double[] shapeY,
- final double sMinX, final double sMinY, final double sMaxX,
- final double sMaxY) {
+ public static boolean rectCrossesPoly(final double rMinX, final double rMinY, final double rMaxX,
+ final double rMaxY, final double[] shapeX, final double[] shapeY,
+ final double sMinX, final double sMinY, final double sMaxX,
+ final double sMaxY) {
// short-circuit: if the bounding boxes are disjoint then the shape does not cross
- if (rectDisjoint(rMinX, rMinY, rMaxX, rMaxY, sMinX, sMinY, sMaxX, sMaxY))
+ if (rectDisjoint(rMinX, rMinY, rMaxX, rMaxY, sMinX, sMinY, sMaxX, sMaxY)) {
return false;
+ }
final double[][] bbox = new double[][] { {rMinX, rMinY}, {rMaxX, rMinY}, {rMaxX, rMaxY}, {rMinX, rMaxY}, {rMinX, rMinY} };
final int polyLength = shapeX.length-1;
@@ -320,8 +234,9 @@ public final class GeoUtils {
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))
+ 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
@@ -329,6 +244,40 @@ public final class GeoUtils {
}
/**
+ * Converts a given circle (defined as a point/radius) to an approximated line-segment polygon
+ *
+ * @param lon longitudinal center of circle (in degrees)
+ * @param lat latitudinal center of circle (in degrees)
+ * @param radius distance radius of circle (in meters)
+ * @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) {
+ 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.pointFromLonLatBearing(lon, lat, angle, radius, 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;
+ }
+
+ /**
* Computes whether a rectangle is within a given polygon (shared boundaries allowed)
*/
public static boolean rectWithinPoly(final double rMinX, final double rMinY, final double rMaxX, final double rMaxY,
@@ -341,6 +290,83 @@ public final class GeoUtils {
!pointInPolygon(shapeX, shapeY, rMaxY, rMaxX) || !pointInPolygon(shapeX, shapeY, rMaxY, rMinX));
}
+ private static boolean rectAnyCornersInCirlce( final double rMinX, final double rMinY, final double rMaxX, final double rMaxY,
+ final double centerLon, final double centerLat, final double radius) {
+ return (SloppyMath.haversin(centerLat, centerLon, rMinY, rMinX)*1000.0 > radius
+ || SloppyMath.haversin(centerLat, centerLon, rMaxY, rMinX)*1000.0 > radius
+ || SloppyMath.haversin(centerLat, centerLon, rMaxY, rMaxX)*1000.0 > radius
+ || SloppyMath.haversin(centerLat, centerLon, rMinY, rMaxX)*1000.0 > radius);
+ }
+
+ public static boolean rectWithinCircle(final double rMinX, final double rMinY, final double rMaxX, final double rMaxY,
+ final double centerLon, final double centerLat, final double radius) {
+ return !(rectAnyCornersInCirlce(rMinX, rMinY, rMaxX, rMaxY, centerLon, centerLat, radius));
+ }
+
+ /**
+ * Computes whether a rectangle crosses a circle
+ */
+ public static boolean rectCrossesCircle(final double rMinX, final double rMinY, final double rMaxX, final double rMaxY,
+ final double centerLon, final double centerLat, final double radius) {
+
+ return rectAnyCornersInCirlce(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);
+ }
+
+ /**
+ * Computes whether or a 3dimensional line segment intersects or crosses a sphere
+ *
+ * @param lon1 longitudinal location of the line segment start point (in degrees)
+ * @param lat1 latitudinal location of the line segment start point (in degrees)
+ * @param alt1 altitude of the line segment start point (in degrees)
+ * @param lon2 longitudinal location of the line segment end point (in degrees)
+ * @param lat2 latitudinal location of the line segment end point (in degrees)
+ * @param alt2 altitude of the line segment end point (in degrees)
+ * @param centerLon longitudinal location of center search point (in degrees)
+ * @param centerLat latitudinal location of center search point (in degrees)
+ * @param centerAlt altitude of the center point (in meters)
+ * @param radius search sphere radius (in meters)
+ * @return whether the provided line segment is a secant of the
+ */
+ private static boolean lineCrossesSphere(double lon1, double lat1, double alt1, double lon2,
+ double lat2, double alt2, double centerLon, double centerLat,
+ double centerAlt, double radius) {
+ // convert to cartesian 3d (in meters)
+ double[] ecf1 = GeoProjectionUtils.llaToECF(lon1, lat1, alt1, null);
+ double[] ecf2 = GeoProjectionUtils.llaToECF(lon2, lat2, alt2, null);
+ double[] cntr = GeoProjectionUtils.llaToECF(centerLon, centerLat, centerAlt, null);
+
+ final double dX = ecf2[0] - ecf1[0];
+ final double dY = ecf2[1] - ecf1[1];
+ final double dZ = ecf2[2] - ecf1[2];
+ final double fX = ecf1[0] - cntr[0];
+ final double fY = ecf1[1] - cntr[1];
+ final double fZ = ecf1[2] - cntr[2];
+
+ final double a = dX*dX + dY*dY + dZ*dZ;
+ final double b = 2 * (fX*dX + fY*dY + fZ*dZ);
+ final double c = (fX*fX + fY*fY + fZ*fZ) - (radius*radius);
+
+ double discrim = (b*b)-(4*a*c);
+ if (discrim < 0) {
+ return false;
+ }
+
+ 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;
+ }
+
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/search/TestGeoPointQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/sandbox/src/test/org/apache/lucene/search/TestGeoPointQuery.java?rev=1691660&r1=1691659&r2=1691660&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/sandbox/src/test/org/apache/lucene/search/TestGeoPointQuery.java (original)
+++ lucene/dev/branches/branch_5x/lucene/sandbox/src/test/org/apache/lucene/search/TestGeoPointQuery.java Sat Jul 18 01:05:25 2015
@@ -44,6 +44,7 @@ import org.apache.lucene.util.FixedBitSe
import org.apache.lucene.util.GeoUtils;
import org.apache.lucene.util.IOUtils;
import org.apache.lucene.util.LuceneTestCase;
+import org.apache.lucene.util.SloppyMath;
import org.apache.lucene.util.TestUtil;
import org.junit.AfterClass;
import org.junit.BeforeClass;
@@ -61,10 +62,15 @@ public class TestGeoPointQuery extends L
private static final String FIELD_NAME = "geoField";
+ // error threshold for point-distance queries (in meters)
+ private static final int DISTANCE_ERR = 700;
+
// Global bounding box we will "cover" in the random test; we have to make this "smallish" else the queries take very long:
private static double originLat;
private static double originLon;
- private static double range;
+// private static double range;
+ private static double lonRange;
+ private static double latRange;
@BeforeClass
public static void beforeClass() throws Exception {
@@ -74,11 +80,21 @@ public class TestGeoPointQuery extends L
// number of ranges that can be created in degenerate cases.
// Between 1.0 and 3.0:
- range = 2*(random().nextDouble() + 0.5);
- originLon = GeoUtils.MIN_LON_INCL + range + (GeoUtils.MAX_LON_INCL - GeoUtils.MIN_LON_INCL - 2*range) * random().nextDouble();
- originLat = GeoUtils.MIN_LAT_INCL + range + (GeoUtils.MAX_LAT_INCL - GeoUtils.MIN_LAT_INCL - 2*range) * random().nextDouble();
+// range = 2*(random().nextDouble() + 0.5);
+ // Between 1.0 and 90.0
+ //lonRange = 1.0 + (90.0 - 1.0) * random().nextDouble();
+ //latRange = 1.0 + (45.0 - 1.0) * random().nextDouble();
+
+ // Between 1.0 and 3.0:
+ lonRange = 2*(random().nextDouble() + 0.5);
+ latRange = 2*(random().nextDouble() + 0.5);
+
+ originLon = GeoUtils.MIN_LON_INCL + lonRange + (GeoUtils.MAX_LON_INCL - GeoUtils.MIN_LON_INCL - 2*lonRange) * random().nextDouble();
+ originLon = GeoUtils.normalizeLon(originLon);
+ originLat = GeoUtils.MIN_LAT_INCL + latRange + (GeoUtils.MAX_LAT_INCL - GeoUtils.MIN_LAT_INCL - 2*latRange) * random().nextDouble();
+ originLat = GeoUtils.normalizeLat(originLat);
if (VERBOSE) {
- System.out.println("TEST: originLon=" + originLon + " originLat=" + originLat + " range=" + range);
+ System.out.println("TEST: originLon=" + originLon + " lonRange= " + lonRange + " originLat=" + originLat + " latRange=" + latRange);
}
RandomIndexWriter writer = new RandomIndexWriter(random(), directory,
newIndexWriterConfig(new MockAnalyzer(random()))
@@ -99,7 +115,10 @@ public class TestGeoPointQuery extends L
new GeoPointField(FIELD_NAME, -83.99724648980559, 58.29438379542874, storedPoint),
new GeoPointField(FIELD_NAME, -26.779373834241003, 33.541429799076354, storedPoint),
new GeoPointField(FIELD_NAME, -77.35379276106497, 26.774024500421728, storedPoint),
- new GeoPointField(FIELD_NAME, -14.796283808944777, -62.455081198245665, storedPoint)};
+ new GeoPointField(FIELD_NAME, -14.796283808944777, -62.455081198245665, storedPoint),
+ new GeoPointField(FIELD_NAME, -178.8538113027811, 32.94823588839368, storedPoint),
+ new GeoPointField(FIELD_NAME, 178.8538113027811, 32.94823588839368, storedPoint),
+ new GeoPointField(FIELD_NAME, -179.5, -44.5, storedPoint)};
for (GeoPointField p : pts) {
Document doc = new Document();
@@ -130,6 +149,11 @@ public class TestGeoPointQuery extends L
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);
+ }
+
@Test
public void testBBoxQuery() throws Exception {
TopDocs td = bboxQuery(-96.7772, 32.778650, -96.77690000, 32.778950, 5);
@@ -138,11 +162,11 @@ public class TestGeoPointQuery extends L
@Test
public void testPolyQuery() throws Exception {
- TopDocs td = polygonQuery( new double[] {-96.7682647, -96.8280029, -96.6288757, -96.4929199,
- -96.6041564, -96.7449188, -96.76826477, -96.7682647},
- new double[] { 33.073130, 32.9942669, 32.938386, 33.0374494,
- 33.1369762, 33.1162747, 33.073130, 33.073130}, 5);
- assertEquals("GeoPolygonQuery failed", td.totalHits, 1);
+ 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", 1, td.totalHits);
}
@Test
@@ -169,6 +193,50 @@ public class TestGeoPointQuery extends L
assertTrue(GeoUtils.rectWithinPoly(-5, 0, -2, 5, px, py, xMin, yMin, xMax, yMax));
}
+ @Test
+ public void testBBoxCrossDateline() throws Exception {
+ TopDocs td = bboxQuery(179.0, -45.0, -179.0, -44.0, 20);
+ assertEquals("BBoxCrossDateline query failed", 1, td.totalHits);
+ }
+
+ @Test
+ public void testWholeMap() throws Exception {
+ TopDocs td = bboxQuery(-179.9, -89.9, 179.9, 89.9, 20);
+ assertEquals("testWholeMap failed", 14, td.totalHits);
+ }
+
+ @Test
+ 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");
+ }
+
+ @Test
+ public void testGeoDistanceQuery() throws Exception {
+ TopDocs td = geoDistanceQuery(-96.4538113027811, 32.94823588839368, 600000, 20);
+ assertEquals("GeoDistanceQuery failed", 6, td.totalHits);
+ }
+
+ @Test
+ public void testGeoDistanceQueryCrossDateline() throws Exception {
+ TopDocs td = geoDistanceQuery(-179.9538113027811, 32.94823588839368, 120000, 20);
+ assertEquals("GeoDistanceQuery failed", 2, td.totalHits);
+ }
+
+ @Test
+ 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 testRandomTiny() throws Exception {
// Make sure single-leaf-node case is OK:
doTestRandom(10);
@@ -298,7 +366,7 @@ public class TestGeoPointQuery extends L
int numThreads = TestUtil.nextInt(random(), 2, 5);
List<Thread> threads = new ArrayList<>();
- final int iters = atLeast(100);
+ final int iters = atLeast(10);
final CountDownLatch startingGun = new CountDownLatch(1);
@@ -319,112 +387,102 @@ public class TestGeoPointQuery extends L
NumericDocValues docIDToID = MultiDocValues.getNumericValues(r, "id");
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);
+ System.out.println("\nTEST: iter=" + iter);
}
Query query;
- boolean tooBigBBox = false;
- boolean polySearch = false;
- double bboxLat0 = lat0;
- double bboxLat1 = lat1;
- double bboxLon0 = lon0;
- double bboxLon1 = lon1;
+ VerifyHits verifyHits;
if (random().nextBoolean()) {
- query = new GeoPointInBBoxQuery(FIELD_NAME, lon0, lat0, lon1, lat1);
- } else {
- polySearch = true;
- if (random().nextBoolean()) {
- // Intentionally pass a "too big" bounding box:
- double pct = random().nextDouble()*0.5;
- double width = lon1-lon0;
- bboxLon0 = Math.max(-180.0, lon0-width*pct);
- bboxLon1 = Math.min(180.0, lon1+width*pct);
- double height = lat1-lat0;
- bboxLat0 = Math.max(-90.0, lat0-height*pct);
- bboxLat1 = Math.min(90.0, lat1+height*pct);
- tooBigBBox = true;
- }
- double[] pLats = new double[5];
- double[] pLons = new double[5];
- pLats[0] = bboxLat0;
- pLons[0] = bboxLon0;
- pLats[1] = bboxLat1;
- pLons[1] = bboxLon0;
- pLats[2] = bboxLat1;
- pLons[2] = bboxLon1;
- pLats[3] = bboxLat0;
- pLons[3] = bboxLon1;
- pLats[4] = bboxLat0;
- pLons[4] = bboxLon0;
- query = new GeoPointInPolygonQuery(FIELD_NAME, bboxLon0, bboxLat0, bboxLon1, bboxLat1, pLons, pLats);
- }
+ final GeoBoundingBox bbox = randomBBox();
- final FixedBitSet hits = new FixedBitSet(r.maxDoc());
- s.search(query, new SimpleCollector() {
+ query = new GeoPointInBBoxQuery(FIELD_NAME, bbox.minLon, bbox.minLat, bbox.maxLon, bbox.maxLat);
+ verifyHits = new VerifyHits() {
+ @Override
+ protected Boolean shouldMatch(double pointLat, double pointLon) {
+
+ // morton encode & decode to compare apples to apples (that is, compare with same hash precision error
+ // present in the index)
+ long pointHash = GeoUtils.mortonHash(pointLon, pointLat);
+ pointLon = GeoUtils.mortonUnhashLon(pointHash);
+ pointLat = GeoUtils.mortonUnhashLat(pointHash);
+
+ if (bboxQueryCanBeWrong(bbox, pointLat, pointLon)) {
+ return null;
+ } else {
+ return rectContainsPointEnc(bbox, pointLat, pointLon);
+ }
+ }
+ };
+ } else if (random().nextBoolean()) {
+
+ // generate a random bounding box
+ GeoBoundingBox bbox = randomBBox();
+
+ final double centerLat = bbox.minLat + ((bbox.maxLat - bbox.minLat)/2.0);
+ final double centerLon = bbox.minLon + ((bbox.maxLon - bbox.minLon)/2.0);
+
+ // radius (in meters) as a function of the random generated bbox
+ // TODO: change 100 back to 1000
+ final double radius = SloppyMath.haversin(centerLat, centerLon, bbox.minLat, centerLon)*100;
+ if (VERBOSE) {
+ System.out.println("\t radius = " + radius);
+ }
+ // query using the centroid of the bounding box
+ query = new GeoPointDistanceQuery(FIELD_NAME, centerLon, centerLat, radius);
- private int docBase;
+ verifyHits = new VerifyHits() {
+ @Override
+ protected Boolean shouldMatch(double pointLat, double pointLon) {
+ if (Double.isNaN(pointLat) || Double.isNaN(pointLon)) {
+ return null;
+ }
+ if (radiusQueryCanBeWrong(centerLat, centerLon, pointLon, pointLat, radius)) {
+ return null;
+ } else {
+ return distanceContainsPt(centerLon, centerLat, pointLon, pointLat, radius);
+ }
+ }
+ };
+
+ } else {
+ final GeoBoundingBox bbox = randomBBox();
- @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<r.maxDoc();docID++) {
- int id = (int) docIDToID.get(docID);
- if (polySearch) {
- lat0 = bboxLat0;
- lon0 = bboxLon0;
- lat1 = bboxLat1;
- lon1 = bboxLon1;
- }
- // morton encode & decode to compare apples to apples (that is, compare with same hash precision error
- // present in the index)
- final long pointHash = GeoUtils.mortonHash(lons[id], lats[id]);
- final double pointLon = GeoUtils.mortonUnhashLon(pointHash);
- final double pointLat = GeoUtils.mortonUnhashLat(pointHash);
- if (!tolerateIgnorance(lat0, lat1, lon0, lon1, pointLat, pointLon)) {
- boolean expected = (deleted.contains(id) == false) &&
- rectContainsPointEnc(lat0, lat1, lon0, lon1, pointLat, pointLon);
- if (hits.get(docID) != expected) {
- System.out.println(Thread.currentThread().getName() + ": iter=" + iter + " id=" + id + " docID=" + docID + " lat=" + pointLat + " lon=" + pointLon + " (bbox: lat=" + lat0 + " TO " + lat1 + " lon=" + lon0 + " TO " + lon1 + ") expected " + expected + " but got: " + hits.get(docID) + " deleted?=" + deleted.contains(id) + " query=" + query);
- if (tooBigBBox) {
- System.out.println(" passed too-big bbox: lat=" + bboxLat0 + " TO " + bboxLat1 + " lon=" + bboxLon0 + " TO " + bboxLon1);
+ double[] pLats = new double[5];
+ double[] pLons = new double[5];
+ pLats[0] = bbox.minLat;
+ pLons[0] = bbox.minLon;
+ pLats[1] = bbox.maxLat;
+ pLons[1] = bbox.minLon;
+ pLats[2] = bbox.maxLat;
+ pLons[2] = bbox.maxLon;
+ pLats[3] = bbox.minLat;
+ pLons[3] = bbox.maxLon;
+ pLats[4] = bbox.minLat;
+ pLons[4] = bbox.minLon;
+ query = new GeoPointInPolygonQuery(FIELD_NAME, pLons, pLats);
+
+ verifyHits = new VerifyHits() {
+ @Override
+ protected Boolean shouldMatch(double pointLat, double pointLon) {
+ // morton encode & decode to compare apples to apples (that is, compare with same hash precision error
+ // present in the index)
+ long pointHash = GeoUtils.mortonHash(pointLon, pointLat);
+ pointLon = GeoUtils.mortonUnhashLon(pointHash);
+ pointLat = GeoUtils.mortonUnhashLat(pointHash);
+
+ if (bboxQueryCanBeWrong(bbox, pointLat, pointLon)) {
+ return null;
+ } else {
+ return rectContainsPointEnc(bbox, pointLat, pointLon);
+ }
}
- fail("wrong result");
- }
- }
+ };
}
+
+ verifyHits.test(s, docIDToID, deleted, query, lats, lons);
}
}
};
@@ -441,35 +499,132 @@ public class TestGeoPointQuery extends L
IOUtils.close(r, dir);
}
- private static boolean rectContainsPointEnc(double rectLatMin, double rectLatMax,
- double rectLonMin, double rectLonMax,
- double pointLat, double pointLon) {
- if (Double.isNaN(pointLat)) {
- return false;
- }
- return GeoUtils.bboxContains(pointLon, pointLat, rectLonMin, rectLatMin, rectLonMax, rectLatMax);
+ private static abstract class VerifyHits {
+
+ public void test(IndexSearcher s, NumericDocValues docIDToID, Set<Integer> deleted, Query query, double[] lats, double[] lons) throws Exception {
+ int maxDoc = s.getIndexReader().maxDoc();
+ final FixedBitSet hits = new FixedBitSet(maxDoc);
+ s.search(query, new SimpleCollector() {
+
+ private int docBase;
+
+ @Override
+ public boolean needsScores() {
+ return false;
+ }
+
+ @Override
+ protected void doSetNextReader(LeafReaderContext context) throws IOException {
+ docBase = context.docBase;
+ }
+
+ @Override
+ public void collect(int doc) {
+ hits.set(docBase+doc);
+ }
+ });
+
+ for(int docID=0;docID<maxDoc;docID++) {
+ int id = (int) docIDToID.get(docID);
+ Boolean expected;
+ if (deleted.contains(id)) {
+ expected = false;
+ } else {
+ expected = shouldMatch(lats[id], lons[id]);
+ }
+
+ // null means it's a borderline case which is allowed to be wrong:
+ if (expected != null) {
+
+ if (hits.get(docID) != expected) {
+ System.out.println(Thread.currentThread().getName() + ": id=" + id +
+ " docID=" + docID + " lat=" + lats[id] + " lon=" + lons[id] +
+ " deleted?=" + deleted.contains(id) + " expected=" + expected + " but got " + hits.get(docID) +
+ " query=" + query);
+ fail("wrong hit");
+ }
+ }
+ }
+ }
+
+ /** Return true if we definitely should match, false if we definitely
+ * should not match, and null if it's a borderline case which might
+ * go either way. */
+ protected abstract Boolean shouldMatch(double lat, double lon);
+ }
+
+ private static boolean distanceContainsPt(double lonA, double latA, double lonB, double latB, final double radius) {
+ final long hashedPtA = GeoUtils.mortonHash(lonA, latA);
+ lonA = GeoUtils.mortonUnhashLon(hashedPtA);
+ latA = GeoUtils.mortonUnhashLat(hashedPtA);
+ final long hashedPtB = GeoUtils.mortonHash(lonB, latB);
+ lonB = GeoUtils.mortonUnhashLon(hashedPtB);
+ latB = GeoUtils.mortonUnhashLat(hashedPtB);
+
+ return (SloppyMath.haversin(latA, lonA, latB, lonB)*1000.0 <= radius);
+ }
+
+ private static boolean rectContainsPointEnc(GeoBoundingBox bbox, double pointLat, double pointLon) {
+ // We should never see a deleted doc here?
+ assert Double.isNaN(pointLat) == false;
+ return GeoUtils.bboxContains(pointLon, pointLat, bbox.minLon, bbox.minLat, bbox.maxLon, bbox.maxLat);
}
- private static boolean tolerateIgnorance(final double minLat, final double maxLat,
- final double minLon, final double maxLon,
- final double lat, final double lon) {
+ private static boolean radiusQueryCanBeWrong(double centerLat, double centerLon, double ptLon, double ptLat,
+ final double radius) {
+ final long hashedCntr = GeoUtils.mortonHash(centerLon, centerLat);
+ centerLon = GeoUtils.mortonUnhashLon(hashedCntr);
+ centerLat = GeoUtils.mortonUnhashLat(hashedCntr);
+ final long hashedPt = GeoUtils.mortonHash(ptLon, ptLat);
+ ptLon = GeoUtils.mortonUnhashLon(hashedPt);
+ ptLat = GeoUtils.mortonUnhashLat(hashedPt);
+
+ double ptDistance = SloppyMath.haversin(centerLat, centerLon, ptLat, ptLon)*1000.0;
+ double delta = StrictMath.abs(ptDistance - radius);
+
+ // if its within the distance error then it can be wrong
+ return delta < DISTANCE_ERR;
+ }
+
+ private static boolean bboxQueryCanBeWrong(GeoBoundingBox bbox, double lat, double lon) {
// we can tolerate variance at the GeoUtils.TOLERANCE decimal place
final int tLon = (int)(lon/(GeoUtils.TOLERANCE-1));
final int tLat = (int)(lat/(GeoUtils.TOLERANCE-1));
- final int tMinLon = (int)(minLon/(GeoUtils.TOLERANCE-1));
- final int tMinLat = (int)(minLat/(GeoUtils.TOLERANCE-1));
- final int tMaxLon = (int)(maxLon/(GeoUtils.TOLERANCE-1));
- final int tMaxLat = (int)(maxLat/(GeoUtils.TOLERANCE-1));
+ final int tMinLon = (int)(bbox.minLon/(GeoUtils.TOLERANCE-1));
+ final int tMinLat = (int)(bbox.minLat/(GeoUtils.TOLERANCE-1));
+ final int tMaxLon = (int)(bbox.maxLon/(GeoUtils.TOLERANCE-1));
+ final int tMaxLat = (int)(bbox.maxLat/(GeoUtils.TOLERANCE-1));
return ((tMinLon - tLon) == 0 || (tMinLat - tLat) == 0
|| (tMaxLon - tLon) == 0 || (tMaxLat - tLat) == 0);
}
private static double randomLat() {
- return originLat + range * (random().nextDouble()-0.5);
+ return GeoUtils.normalizeLat(originLat + latRange * (random().nextDouble() - 0.5));
}
private static double randomLon() {
- return originLon + range * (random().nextDouble()-0.5);
+ return GeoUtils.normalizeLon(originLon + lonRange * (random().nextDouble() - 0.5));
+ }
+
+ private static GeoBoundingBox randomBBox() {
+ 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;
+ }
+
+ return new GeoBoundingBox(lon0, lon1, lat0, lat1);
}
}