You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by nk...@apache.org on 2016/02/05 18:10:54 UTC
[13/34] lucene-solr git commit: LUCENE-7015: refactors lucene-spatial
module to a new lucene-spatial-extras module,
and refactors sandbox GeoPointField and queries to lucene-spatial module
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5b028349/lucene/spatial/src/java/org/apache/lucene/spatial/query/SpatialArgsParser.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/query/SpatialArgsParser.java b/lucene/spatial/src/java/org/apache/lucene/spatial/query/SpatialArgsParser.java
deleted file mode 100644
index 81612ff..0000000
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/query/SpatialArgsParser.java
+++ /dev/null
@@ -1,146 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.lucene.spatial.query;
-
-import com.spatial4j.core.context.SpatialContext;
-import com.spatial4j.core.exception.InvalidShapeException;
-import com.spatial4j.core.shape.Shape;
-
-import java.text.ParseException;
-import java.util.HashMap;
-import java.util.Locale;
-import java.util.Map;
-import java.util.StringTokenizer;
-
-/**
- * Parses a string that usually looks like "OPERATION(SHAPE)" into a {@link SpatialArgs}
- * object. The set of operations supported are defined in {@link SpatialOperation}, such
- * as "Intersects" being a common one. The shape portion is defined by WKT {@link com.spatial4j.core.io.WktShapeParser},
- * but it can be overridden/customized via {@link #parseShape(String, com.spatial4j.core.context.SpatialContext)}.
- * There are some optional name-value pair parameters that follow the closing parenthesis. Example:
- * <pre>
- * Intersects(ENVELOPE(-10,-8,22,20)) distErrPct=0.025
- * </pre>
- * <p>
- * In the future it would be good to support something at least semi-standardized like a
- * variant of <a href="http://docs.geoserver.org/latest/en/user/filter/ecql_reference.html#spatial-predicate">
- * [E]CQL</a>.
- *
- * @lucene.experimental
- */
-public class SpatialArgsParser {
-
- public static final String DIST_ERR_PCT = "distErrPct";
- public static final String DIST_ERR = "distErr";
-
- /** Writes a close approximation to the parsed input format. */
- static String writeSpatialArgs(SpatialArgs args) {
- StringBuilder str = new StringBuilder();
- str.append(args.getOperation().getName());
- str.append('(');
- str.append(args.getShape().toString());
- if (args.getDistErrPct() != null)
- str.append(" distErrPct=").append(String.format(Locale.ROOT, "%.2f%%", args.getDistErrPct() * 100d));
- if (args.getDistErr() != null)
- str.append(" distErr=").append(args.getDistErr());
- str.append(')');
- return str.toString();
- }
-
- /**
- * Parses a string such as "Intersects(ENVELOPE(-10,-8,22,20)) distErrPct=0.025".
- *
- * @param v The string to parse. Mandatory.
- * @param ctx The spatial context. Mandatory.
- * @return Not null.
- * @throws IllegalArgumentException if the parameters don't make sense or an add-on parameter is unknown
- * @throws ParseException If there is a problem parsing the string
- * @throws InvalidShapeException When the coordinates are invalid for the shape
- */
- public SpatialArgs parse(String v, SpatialContext ctx) throws ParseException, InvalidShapeException {
- int idx = v.indexOf('(');
- int edx = v.lastIndexOf(')');
-
- if (idx < 0 || idx > edx) {
- throw new ParseException("missing parens: " + v, -1);
- }
-
- SpatialOperation op = SpatialOperation.get(v.substring(0, idx).trim());
-
- String body = v.substring(idx + 1, edx).trim();
- if (body.length() < 1) {
- throw new ParseException("missing body : " + v, idx + 1);
- }
-
- Shape shape = parseShape(body, ctx);
- SpatialArgs args = newSpatialArgs(op, shape);
-
- if (v.length() > (edx + 1)) {
- body = v.substring(edx + 1).trim();
- if (body.length() > 0) {
- Map<String, String> aa = parseMap(body);
- readNameValuePairs(args, aa);
- if (!aa.isEmpty()) {
- throw new IllegalArgumentException("unused parameters: " + aa);
- }
- }
- }
- args.validate();
- return args;
- }
-
- protected SpatialArgs newSpatialArgs(SpatialOperation op, Shape shape) {
- return new SpatialArgs(op, shape);
- }
-
- protected void readNameValuePairs(SpatialArgs args, Map<String, String> nameValPairs) {
- args.setDistErrPct(readDouble(nameValPairs.remove(DIST_ERR_PCT)));
- args.setDistErr(readDouble(nameValPairs.remove(DIST_ERR)));
- }
-
- protected Shape parseShape(String str, SpatialContext ctx) throws ParseException {
- //return ctx.readShape(str);//still in Spatial4j 0.4 but will be deleted
- return ctx.readShapeFromWkt(str);
- }
-
- protected static Double readDouble(String v) {
- return v == null ? null : Double.valueOf(v);
- }
-
- protected static boolean readBool(String v, boolean defaultValue) {
- return v == null ? defaultValue : Boolean.parseBoolean(v);
- }
-
- /** Parses "a=b c=d f" (whitespace separated) into name-value pairs. If there
- * is no '=' as in 'f' above then it's short for f=f. */
- protected static Map<String, String> parseMap(String body) {
- Map<String, String> map = new HashMap<>();
- StringTokenizer st = new StringTokenizer(body, " \n\t");
- while (st.hasMoreTokens()) {
- String a = st.nextToken();
- int idx = a.indexOf('=');
- if (idx > 0) {
- String k = a.substring(0, idx);
- String v = a.substring(idx + 1);
- map.put(k, v);
- } else {
- map.put(a, a);
- }
- }
- return map;
- }
-}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5b028349/lucene/spatial/src/java/org/apache/lucene/spatial/query/SpatialOperation.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/query/SpatialOperation.java b/lucene/spatial/src/java/org/apache/lucene/spatial/query/SpatialOperation.java
deleted file mode 100644
index 7d750ac..0000000
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/query/SpatialOperation.java
+++ /dev/null
@@ -1,179 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.lucene.spatial.query;
-
-import com.spatial4j.core.shape.Rectangle;
-import com.spatial4j.core.shape.Shape;
-import com.spatial4j.core.shape.SpatialRelation;
-
-import java.io.Serializable;
-import java.util.ArrayList;
-import java.util.HashMap;
-import java.util.List;
-import java.util.Locale;
-import java.util.Map;
-
-/**
- * A predicate that compares a stored geometry to a supplied geometry. It's enum-like. For more
- * explanation of each predicate, consider looking at the source implementation
- * of {@link #evaluate(com.spatial4j.core.shape.Shape, com.spatial4j.core.shape.Shape)}. It's important
- * to be aware that Lucene-spatial makes no distinction of shape boundaries, unlike many standardized
- * definitions. Nor does it make dimensional distinctions (e.g. line vs polygon).
- * You can lookup a predicate by "Covers" or "Contains", for example, and you will get the
- * same underlying predicate implementation.
- *
- * @see <a href="http://en.wikipedia.org/wiki/DE-9IM">DE-9IM at Wikipedia, based on OGC specs</a>
- * @see <a href="http://edndoc.esri.com/arcsde/9.1/general_topics/understand_spatial_relations.htm">
- * ESRIs docs on spatial relations</a>
- *
- * @lucene.experimental
- */
-public abstract class SpatialOperation implements Serializable {
- //TODO rename to SpatialPredicate. Use enum? LUCENE-5771
-
- // Private registry
- private static final Map<String, SpatialOperation> registry = new HashMap<>();//has aliases
- private static final List<SpatialOperation> list = new ArrayList<>();
-
- // Geometry Operations
-
- /** Bounding box of the *indexed* shape, then {@link #Intersects}. */
- public static final SpatialOperation BBoxIntersects = new SpatialOperation("BBoxIntersects") {
- @Override
- public boolean evaluate(Shape indexedShape, Shape queryShape) {
- return indexedShape.getBoundingBox().relate(queryShape).intersects();
- }
- };
- /** Bounding box of the *indexed* shape, then {@link #IsWithin}. */
- public static final SpatialOperation BBoxWithin = new SpatialOperation("BBoxWithin") {
- {
- register("BBoxCoveredBy");//alias -- the better name
- }
- @Override
- public boolean evaluate(Shape indexedShape, Shape queryShape) {
- Rectangle bbox = indexedShape.getBoundingBox();
- return bbox.relate(queryShape) == SpatialRelation.WITHIN || bbox.equals(queryShape);
- }
- };
- /** Meets the "Covers" OGC definition (boundary-neutral). */
- public static final SpatialOperation Contains = new SpatialOperation("Contains") {
- {
- register("Covers");//alias -- the better name
- }
- @Override
- public boolean evaluate(Shape indexedShape, Shape queryShape) {
- return indexedShape.relate(queryShape) == SpatialRelation.CONTAINS || indexedShape.equals(queryShape);
- }
- };
- /** Meets the "Intersects" OGC definition. */
- public static final SpatialOperation Intersects = new SpatialOperation("Intersects") {
- @Override
- public boolean evaluate(Shape indexedShape, Shape queryShape) {
- return indexedShape.relate(queryShape).intersects();
- }
- };
- /** Meets the "Equals" OGC definition. */
- public static final SpatialOperation IsEqualTo = new SpatialOperation("Equals") {
- {
- register("IsEqualTo");//alias (deprecated)
- }
- @Override
- public boolean evaluate(Shape indexedShape, Shape queryShape) {
- return indexedShape.equals(queryShape);
- }
- };
- /** Meets the "Disjoint" OGC definition. */
- public static final SpatialOperation IsDisjointTo = new SpatialOperation("Disjoint") {
- {
- register("IsDisjointTo");//alias (deprecated)
- }
- @Override
- public boolean evaluate(Shape indexedShape, Shape queryShape) {
- return ! indexedShape.relate(queryShape).intersects();
- }
- };
- /** Meets the "CoveredBy" OGC definition (boundary-neutral). */
- public static final SpatialOperation IsWithin = new SpatialOperation("Within") {
- {
- register("IsWithin");//alias (deprecated)
- register("CoveredBy");//alias -- the more appropriate name.
- }
- @Override
- public boolean evaluate(Shape indexedShape, Shape queryShape) {
- return indexedShape.relate(queryShape) == SpatialRelation.WITHIN || indexedShape.equals(queryShape);
- }
- };
- /** Almost meets the "Overlaps" OGC definition, but boundary-neutral (boundary==interior). */
- public static final SpatialOperation Overlaps = new SpatialOperation("Overlaps") {
- @Override
- public boolean evaluate(Shape indexedShape, Shape queryShape) {
- return indexedShape.relate(queryShape) == SpatialRelation.INTERSECTS;//not Contains or Within or Disjoint
- }
- };
-
- private final String name;
-
- protected SpatialOperation(String name) {
- this.name = name;
- register(name);
- list.add( this );
- }
-
- protected void register(String name) {
- registry.put(name, this);
- registry.put(name.toUpperCase(Locale.ROOT), this);
- }
-
- public static SpatialOperation get( String v ) {
- SpatialOperation op = registry.get( v );
- if( op == null ) {
- op = registry.get(v.toUpperCase(Locale.ROOT));
- }
- if( op == null ) {
- throw new IllegalArgumentException("Unknown Operation: " + v );
- }
- return op;
- }
-
- public static List<SpatialOperation> values() {
- return list;
- }
-
- public static boolean is( SpatialOperation op, SpatialOperation ... tst ) {
- for( SpatialOperation t : tst ) {
- if( op == t ) {
- return true;
- }
- }
- return false;
- }
-
- /**
- * Returns whether the relationship between indexedShape and queryShape is
- * satisfied by this operation.
- */
- public abstract boolean evaluate(Shape indexedShape, Shape queryShape);
-
- public String getName() {
- return name;
- }
-
- @Override
- public String toString() {
- return name;
- }
-}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5b028349/lucene/spatial/src/java/org/apache/lucene/spatial/query/UnsupportedSpatialOperation.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/query/UnsupportedSpatialOperation.java b/lucene/spatial/src/java/org/apache/lucene/spatial/query/UnsupportedSpatialOperation.java
deleted file mode 100644
index d6cb152..0000000
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/query/UnsupportedSpatialOperation.java
+++ /dev/null
@@ -1,28 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.lucene.spatial.query;
-
-/**
- * Exception thrown when the {@link org.apache.lucene.spatial.SpatialStrategy} cannot implement the requested operation.
- * @lucene.experimental
- */
-public class UnsupportedSpatialOperation extends UnsupportedOperationException {
-
- public UnsupportedSpatialOperation(SpatialOperation op) {
- super(op.getName());
- }
-}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5b028349/lucene/spatial/src/java/org/apache/lucene/spatial/query/package-info.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/query/package-info.java b/lucene/spatial/src/java/org/apache/lucene/spatial/query/package-info.java
deleted file mode 100644
index 75ee680..0000000
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/query/package-info.java
+++ /dev/null
@@ -1,20 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-/**
- * Spatial Query options useful for client side requests
- */
-package org.apache.lucene.spatial.query;
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5b028349/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointDistanceQuery.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointDistanceQuery.java b/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointDistanceQuery.java
new file mode 100644
index 0000000..bbce004
--- /dev/null
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointDistanceQuery.java
@@ -0,0 +1,182 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.spatial.search;
+
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.search.BooleanClause;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.spatial.util.GeoBoundingBox;
+import org.apache.lucene.spatial.util.GeoDistanceUtils;
+import org.apache.lucene.spatial.util.GeoUtils;
+
+/** Implements a simple point distance query on a GeoPoint field. This is based on
+ * {@link 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. 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 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)
+ *
+ * <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 */
+public class GeoPointDistanceQuery extends GeoPointInBBoxQuery {
+ /** longitude value (in degrees) for query location */
+ protected final double centerLon;
+ /** latitude value (in degrees) for query location */
+ protected final double centerLat;
+ /** distance (in meters) from lon, lat center location */
+ protected final double radiusMeters;
+
+ /**
+ * Constructs a Query for all {@link org.apache.lucene.spatial.document.GeoPointField} types within a
+ * distance (in meters) from a given point
+ **/
+ 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 radiusMeters) {
+ super(field, bbox.minLon, bbox.minLat, bbox.maxLon, bbox.maxLat);
+ {
+ // check longitudinal overlap (limits radius)
+ final double maxRadius = GeoDistanceUtils.maxRadialDistanceMeters(centerLon, centerLat);
+ 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);
+ }
+
+ if (GeoUtils.isValidLat(centerLat) == false) {
+ throw new IllegalArgumentException("invalid centerLat " + centerLat);
+ }
+
+ if (radiusMeters <= 0.0) {
+ throw new IllegalArgumentException("invalid radiusMeters " + radiusMeters);
+ }
+
+ this.centerLon = centerLon;
+ this.centerLat = centerLat;
+ this.radiusMeters = radiusMeters;
+ }
+
+ @Override
+ public Query rewrite(IndexReader reader) {
+ // query crosses dateline; split into left and right queries
+ if (maxLon < minLon) {
+ BooleanQuery.Builder bqb = new BooleanQuery.Builder();
+
+ // unwrap the longitude iff outside the specified min/max lon range
+ double unwrappedLon = centerLon;
+ if (unwrappedLon > maxLon) {
+ // unwrap left
+ unwrappedLon += -360.0D;
+ }
+ GeoPointDistanceQueryImpl left = new GeoPointDistanceQueryImpl(field, this, unwrappedLon,
+ new GeoBoundingBox(GeoUtils.MIN_LON_INCL, maxLon, minLat, maxLat));
+ bqb.add(new BooleanClause(left, BooleanClause.Occur.SHOULD));
+
+ if (unwrappedLon < maxLon) {
+ // unwrap right
+ unwrappedLon += 360.0D;
+ }
+ GeoPointDistanceQueryImpl right = new GeoPointDistanceQueryImpl(field, this, unwrappedLon,
+ new GeoBoundingBox(minLon, GeoUtils.MAX_LON_INCL, minLat, maxLat));
+ bqb.add(new BooleanClause(right, BooleanClause.Occur.SHOULD));
+
+ return bqb.build();
+ }
+ return new GeoPointDistanceQueryImpl(field, this, centerLon,
+ new GeoBoundingBox(this.minLon, this.maxLon, this.minLat, this.maxLat));
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) return true;
+ if (!(o instanceof GeoPointDistanceQuery)) return false;
+ if (!super.equals(o)) return false;
+
+ GeoPointDistanceQuery that = (GeoPointDistanceQuery) o;
+
+ if (Double.compare(that.centerLat, centerLat) != 0) return false;
+ if (Double.compare(that.centerLon, centerLon) != 0) return false;
+ if (Double.compare(that.radiusMeters, radiusMeters) != 0) return false;
+
+ return true;
+ }
+
+ @Override
+ public int hashCode() {
+ int result = super.hashCode();
+ long temp;
+ temp = Double.doubleToLongBits(centerLon);
+ result = 31 * result + (int) (temp ^ (temp >>> 32));
+ temp = Double.doubleToLongBits(centerLat);
+ result = 31 * result + (int) (temp ^ (temp >>> 32));
+ temp = Double.doubleToLongBits(radiusMeters);
+ result = 31 * result + (int) (temp ^ (temp >>> 32));
+ return result;
+ }
+
+ @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 sb.append( " Center: [")
+ .append(centerLon)
+ .append(',')
+ .append(centerLat)
+ .append(']')
+ .append(" Distance: ")
+ .append(radiusMeters)
+ .append(" meters")
+ .append("]")
+ .toString();
+ }
+
+ /** getter method for center longitude value */
+ public double getCenterLon() {
+ return this.centerLon;
+ }
+
+ /** getter method for center latitude value */
+ public double getCenterLat() {
+ return this.centerLat;
+ }
+
+ /** getter method for distance value (in meters) */
+ public double getRadiusMeters() {
+ return this.radiusMeters;
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5b028349/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointDistanceQueryImpl.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointDistanceQueryImpl.java b/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointDistanceQueryImpl.java
new file mode 100644
index 0000000..1566e0d
--- /dev/null
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointDistanceQueryImpl.java
@@ -0,0 +1,130 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.spatial.search;
+
+import java.io.IOException;
+
+import org.apache.lucene.spatial.document.GeoPointField;
+import org.apache.lucene.index.Terms;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.spatial.util.GeoBoundingBox;
+import org.apache.lucene.util.AttributeSource;
+import org.apache.lucene.spatial.util.GeoRelationUtils;
+import org.apache.lucene.util.SloppyMath;
+
+/** Package private implementation for the public facing GeoPointDistanceQuery delegate class.
+ *
+ * @lucene.experimental
+ */
+final class GeoPointDistanceQueryImpl extends GeoPointInBBoxQueryImpl {
+ private final GeoPointDistanceQuery query;
+ private final double centerLon;
+
+ GeoPointDistanceQueryImpl(final String field, final GeoPointDistanceQuery q, final double centerLonUnwrapped,
+ final GeoBoundingBox bbox) {
+ super(field, bbox.minLon, bbox.minLat, bbox.maxLon, bbox.maxLat);
+ query = q;
+ centerLon = centerLonUnwrapped;
+ }
+
+ @Override @SuppressWarnings("unchecked")
+ protected TermsEnum getTermsEnum(final Terms terms, AttributeSource atts) throws IOException {
+ return new GeoPointRadiusTermsEnum(terms.iterator(), this.minLon, this.minLat, this.maxLon, this.maxLat);
+ }
+
+ @Override
+ public void setRewriteMethod(RewriteMethod method) {
+ throw new UnsupportedOperationException("cannot change rewrite method");
+ }
+
+ private final class GeoPointRadiusTermsEnum extends GeoPointTermsEnum {
+ GeoPointRadiusTermsEnum(final TermsEnum tenum, final double minLon, final double minLat,
+ final double maxLon, final double maxLat) {
+ 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 GeoRelationUtils.rectCrossesCircle(minLon, minLat, maxLon, maxLat,
+ centerLon, query.centerLat, query.radiusMeters, true);
+ }
+
+ @Override
+ protected boolean cellWithin(final double minLon, final double minLat, final double maxLon, final double maxLat) {
+ return GeoRelationUtils.rectWithinCircle(minLon, minLat, maxLon, maxLat,
+ centerLon, query.centerLat, query.radiusMeters, true);
+ }
+
+ @Override
+ protected boolean cellIntersectsShape(final double minLon, final double minLat, final double maxLon, final double maxLat) {
+ return (cellContains(minLon, minLat, maxLon, maxLat)
+ || cellWithin(minLon, minLat, maxLon, maxLat) || cellCrosses(minLon, minLat, maxLon, maxLat));
+ }
+
+ /**
+ * The two-phase query approach. The parent {@link GeoPointTermsEnum} class matches
+ * encoded terms that fall within the minimum bounding box of the point-radius circle. Those documents that pass
+ * the initial bounding box filter are then post filter compared to the provided distance using the
+ * {@link org.apache.lucene.util.SloppyMath#haversin} method.
+ */
+ @Override
+ protected boolean postFilter(final double lon, final double lat) {
+ return (SloppyMath.haversin(query.centerLat, centerLon, lat, lon) * 1000.0 <= query.radiusMeters);
+ }
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) return true;
+ if (!(o instanceof GeoPointDistanceQueryImpl)) return false;
+ if (!super.equals(o)) return false;
+
+ GeoPointDistanceQueryImpl that = (GeoPointDistanceQueryImpl) o;
+
+ if (!query.equals(that.query)) return false;
+
+ return true;
+ }
+
+ @Override
+ public int hashCode() {
+ int result = super.hashCode();
+ result = 31 * result + query.hashCode();
+ return result;
+ }
+
+ public double getRadiusMeters() {
+ return query.getRadiusMeters();
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5b028349/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointDistanceRangeQuery.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointDistanceRangeQuery.java b/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointDistanceRangeQuery.java
new file mode 100644
index 0000000..beec15e
--- /dev/null
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointDistanceRangeQuery.java
@@ -0,0 +1,111 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.spatial.search;
+
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.search.BooleanClause;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.Query;
+
+/** Implements a point distance range query on a GeoPoint field. This is based on
+ * {@code GeoPointDistanceQuery} and is implemented using a
+ * {@code org.apache.lucene.search.BooleanClause.MUST_NOT} clause to exclude any points that fall within
+ * minRadiusMeters from the provided point.
+ *
+ * @lucene.experimental
+ */
+public final class GeoPointDistanceRangeQuery extends GeoPointDistanceQuery {
+ /** minimum distance range (in meters) from lon, lat center location, maximum is inherited */
+ protected final double minRadiusMeters;
+
+ /**
+ * Constructs a query for all {@link org.apache.lucene.spatial.document.GeoPointField} types within a minimum / maximum
+ * distance (in meters) range from a given point
+ */
+ public GeoPointDistanceRangeQuery(final String field, final double centerLon, final double centerLat,
+ final double minRadiusMeters, final double maxRadius) {
+ super(field, centerLon, centerLat, maxRadius);
+ this.minRadiusMeters = minRadiusMeters;
+ }
+
+ @Override
+ public Query rewrite(IndexReader reader) {
+ Query q = super.rewrite(reader);
+ if (minRadiusMeters == 0.0) {
+ return q;
+ }
+
+ // add an exclusion query
+ BooleanQuery.Builder bqb = new BooleanQuery.Builder();
+
+ // create a new exclusion query
+ GeoPointDistanceQuery exclude = new GeoPointDistanceQuery(field, centerLon, centerLat, minRadiusMeters);
+ // full map search
+// if (radiusMeters >= 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));
+// }
+ bqb.add(new BooleanClause(exclude, BooleanClause.Occur.MUST_NOT));
+
+ return bqb.build();
+ }
+
+ @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 sb.append( " Center: [")
+ .append(centerLon)
+ .append(',')
+ .append(centerLat)
+ .append(']')
+ .append(" From Distance: ")
+ .append(minRadiusMeters)
+ .append(" m")
+ .append(" To Distance: ")
+ .append(radiusMeters)
+ .append(" m")
+ .append(" Lower Left: [")
+ .append(minLon)
+ .append(',')
+ .append(minLat)
+ .append(']')
+ .append(" Upper Right: [")
+ .append(maxLon)
+ .append(',')
+ .append(maxLat)
+ .append("]")
+ .toString();
+ }
+
+ /** getter method for minimum distance */
+ public double getMinRadiusMeters() {
+ return this.minRadiusMeters;
+ }
+
+ /** getter method for maximum distance */
+ public double getMaxRadiusMeters() {
+ return this.radiusMeters;
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5b028349/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointInBBoxQuery.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointInBBoxQuery.java b/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointInBBoxQuery.java
new file mode 100644
index 0000000..1c235c3
--- /dev/null
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointInBBoxQuery.java
@@ -0,0 +1,171 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.spatial.search;
+
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.search.BooleanClause;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.FieldValueQuery;
+import org.apache.lucene.search.LegacyNumericRangeQuery;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.spatial.util.GeoUtils;
+
+/** Implements a simple bounding box query on a GeoPoint field. This is inspired by
+ * {@link LegacyNumericRangeQuery} and is implemented using a
+ * two phase approach. First, 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 final check that verifies whether
+ * the decoded lat/lon falls within (or on the boundary) of the query bounding box.
+ * The value comparisons are subject to a precision tolerance defined in
+ * {@value GeoUtils#TOLERANCE}
+ *
+ * NOTES:
+ * 1. All latitude/longitude values must be in decimal degrees.
+ * 2. Complex computational geometry (e.g., dateline wrapping) is not supported
+ * 3. For more advanced GeoSpatial indexing and query operations see spatial module
+ * 4. This is well suited for small rectangles, large bounding boxes may result
+ * in many terms, depending whether the bounding box falls on the boundary of
+ * many cells (degenerate case)
+ *
+ * @lucene.experimental
+ */
+public class GeoPointInBBoxQuery extends Query {
+ /** field name */
+ protected final String field;
+ /** minimum longitude value (in degrees) */
+ protected final double minLon;
+ /** minimum latitude value (in degrees) */
+ protected final double minLat;
+ /** maximum longitude value (in degrees) */
+ protected final double maxLon;
+ /** maximum latitude value (in degrees) */
+ protected final double maxLat;
+
+ /**
+ * Constructs a query for all {@link org.apache.lucene.spatial.document.GeoPointField} types that fall within a
+ * defined bounding box
+ */
+ public GeoPointInBBoxQuery(final String field, final double minLon, final double minLat, final double maxLon, final double maxLat) {
+ this.field = field;
+ this.minLon = minLon;
+ this.minLat = minLat;
+ this.maxLon = maxLon;
+ this.maxLat = maxLat;
+ }
+
+ @Override
+ public Query rewrite(IndexReader reader) {
+ // short-circuit to match all if specifying the whole map
+ if (minLon == GeoUtils.MIN_LON_INCL && maxLon == GeoUtils.MAX_LON_INCL
+ && minLat == GeoUtils.MIN_LAT_INCL && maxLat == GeoUtils.MAX_LAT_INCL) {
+ // FieldValueQuery is valid since DocValues are *required* for GeoPointField
+ return new FieldValueQuery(field);
+ }
+
+ if (maxLon < minLon) {
+ BooleanQuery.Builder bqb = new BooleanQuery.Builder();
+
+ GeoPointInBBoxQueryImpl left = new GeoPointInBBoxQueryImpl(field, -180.0D, minLat, maxLon, maxLat);
+ bqb.add(new BooleanClause(left, BooleanClause.Occur.SHOULD));
+ GeoPointInBBoxQueryImpl right = new GeoPointInBBoxQueryImpl(field, minLon, minLat, 180.0D, maxLat);
+ bqb.add(new BooleanClause(right, BooleanClause.Occur.SHOULD));
+ return bqb.build();
+ }
+ 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 sb.append(" Lower Left: [")
+ .append(minLon)
+ .append(',')
+ .append(minLat)
+ .append(']')
+ .append(" Upper Right: [")
+ .append(maxLon)
+ .append(',')
+ .append(maxLat)
+ .append("]")
+ .toString();
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) return true;
+ if (!(o instanceof GeoPointInBBoxQuery)) return false;
+ if (!super.equals(o)) return false;
+
+ GeoPointInBBoxQuery that = (GeoPointInBBoxQuery) o;
+
+ if (Double.compare(that.maxLat, maxLat) != 0) return false;
+ 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;
+ }
+
+ @Override
+ 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);
+ result = 31 * result + (int) (temp ^ (temp >>> 32));
+ temp = Double.doubleToLongBits(maxLon);
+ result = 31 * result + (int) (temp ^ (temp >>> 32));
+ temp = Double.doubleToLongBits(maxLat);
+ result = 31 * result + (int) (temp ^ (temp >>> 32));
+ return result;
+ }
+
+ /** getter method for retrieving the field name */
+ public final String getField() {
+ return this.field;
+ }
+
+ /** getter method for retrieving the minimum longitude (in degrees) */
+ public final double getMinLon() {
+ return this.minLon;
+ }
+
+ /** getter method for retrieving the minimum latitude (in degrees) */
+ public final double getMinLat() {
+ return this.minLat;
+ }
+
+ /** getter method for retrieving the maximum longitude (in degrees) */
+ public final double getMaxLon() {
+ return this.maxLon;
+ }
+
+ /** getter method for retrieving the maximum latitude (in degrees) */
+ public final double getMaxLat() {
+ return this.maxLat;
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5b028349/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointInBBoxQueryImpl.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointInBBoxQueryImpl.java b/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointInBBoxQueryImpl.java
new file mode 100644
index 0000000..2e993e1
--- /dev/null
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointInBBoxQueryImpl.java
@@ -0,0 +1,160 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.spatial.search;
+
+import java.io.IOException;
+
+import org.apache.lucene.spatial.document.GeoPointField;
+import org.apache.lucene.index.Terms;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.util.AttributeSource;
+import org.apache.lucene.spatial.util.GeoRelationUtils;
+import org.apache.lucene.util.SloppyMath;
+
+/** Package private implementation for the public facing GeoPointInBBoxQuery delegate class.
+ *
+ * @lucene.experimental
+ */
+class GeoPointInBBoxQueryImpl extends GeoPointTermQuery {
+ /**
+ * 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
+ */
+ GeoPointInBBoxQueryImpl(final String field, final double minLon, final double minLat, final double maxLon, final double maxLat) {
+ super(field, minLon, minLat, maxLon, maxLat);
+ }
+
+ @Override @SuppressWarnings("unchecked")
+ protected TermsEnum getTermsEnum(final Terms terms, AttributeSource atts) throws IOException {
+ return new GeoPointInBBoxTermsEnum(terms.iterator(), minLon, minLat, maxLon, maxLat);
+ }
+
+ @Override
+ public void setRewriteMethod(RewriteMethod method) {
+ throw new UnsupportedOperationException("cannot change rewrite method");
+ }
+
+ protected class GeoPointInBBoxTermsEnum extends GeoPointTermsEnum {
+ protected GeoPointInBBoxTermsEnum(final TermsEnum tenum, final double minLon, final double minLat,
+ final double maxLon, final double maxLat) {
+ 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
+ */
+ @Override
+ protected boolean cellCrosses(final double minLon, final double minLat, final double maxLon, final double maxLat) {
+ return GeoRelationUtils.rectCrosses(minLon, minLat, maxLon, maxLat, this.minLon, this.minLat, this.maxLon, this.maxLat);
+ }
+
+ /**
+ * Determine whether quad-cell is within the shape
+ */
+ @Override
+ protected boolean cellWithin(final double minLon, final double minLat, final double maxLon, final double maxLat) {
+ return GeoRelationUtils.rectWithin(minLon, minLat, maxLon, maxLat, this.minLon, this.minLat, this.maxLon, this.maxLat);
+ }
+
+ @Override
+ protected boolean cellIntersectsShape(final double minLon, final double minLat, final double maxLon, final double maxLat) {
+ return cellIntersectsMBR(minLon, minLat, maxLon, maxLat);
+ }
+
+ @Override
+ protected boolean postFilter(final double lon, final double lat) {
+ return GeoRelationUtils.pointInRectPrecise(lon, lat, minLon, minLat, maxLon, maxLat);
+ }
+ }
+
+ @Override
+ @SuppressWarnings({"unchecked","rawtypes"})
+ public boolean equals(Object o) {
+ if (this == o) return true;
+ if (o == null || getClass() != o.getClass()) return false;
+ if (!super.equals(o)) return false;
+
+ GeoPointInBBoxQueryImpl that = (GeoPointInBBoxQueryImpl) o;
+
+ if (Double.compare(that.maxLat, maxLat) != 0) return false;
+ 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;
+
+ return true;
+ }
+
+ @Override
+ public int hashCode() {
+ int result = super.hashCode();
+ long temp;
+ temp = Double.doubleToLongBits(minLon);
+ result = 31 * result + (int) (temp ^ (temp >>> 32));
+ temp = Double.doubleToLongBits(minLat);
+ result = 31 * result + (int) (temp ^ (temp >>> 32));
+ temp = Double.doubleToLongBits(maxLon);
+ result = 31 * result + (int) (temp ^ (temp >>> 32));
+ temp = Double.doubleToLongBits(maxLat);
+ result = 31 * result + (int) (temp ^ (temp >>> 32));
+ 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("]")
+ .toString();
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5b028349/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointInPolygonQuery.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointInPolygonQuery.java b/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointInPolygonQuery.java
new file mode 100644
index 0000000..bf6945e
--- /dev/null
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointInPolygonQuery.java
@@ -0,0 +1,197 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.spatial.search;
+
+import java.io.IOException;
+import java.util.Arrays;
+
+import org.apache.lucene.index.Terms;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.spatial.document.GeoPointField;
+import org.apache.lucene.spatial.util.GeoBoundingBox;
+import org.apache.lucene.util.AttributeSource;
+import org.apache.lucene.spatial.util.GeoRelationUtils;
+import org.apache.lucene.spatial.util.GeoUtils;
+
+/** Implements a simple point in polygon query on a GeoPoint field. This is based on
+ * {@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
+ * (or on the boundary) of the bounding box query. Finally, the remaining candidate
+ * term is passed to the final point in polygon check. All value comparisons are subject
+ * to the same precision tolerance defined in {@value GeoUtils#TOLERANCE}
+ *
+ * <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
+ */
+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;
+ private final double[] y;
+
+ /**
+ * Constructs a new GeoPolygonQuery that will match encoded {@link GeoPointField} terms
+ * that fall within or on the boundary of the polygon defined by the input parameters.
+ */
+ public GeoPointInPolygonQuery(final String field, final double[] polyLons, final double[] polyLats) {
+ this(field, GeoUtils.polyToBBox(polyLons, polyLats), 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);
+ if (polyLats.length != polyLons.length) {
+ throw new IllegalArgumentException("polyLats and polyLons must be equal length");
+ }
+ if (polyLats.length < 4) {
+ throw new IllegalArgumentException("at least 4 polygon points required");
+ }
+ if (polyLats[0] != polyLats[polyLats.length-1]) {
+ throw new IllegalArgumentException("first and last points of the polygon must be the same (it must close itself): polyLats[0]=" + polyLats[0] + " polyLats[" + (polyLats.length-1) + "]=" + polyLats[polyLats.length-1]);
+ }
+ if (polyLons[0] != polyLons[polyLons.length-1]) {
+ throw new IllegalArgumentException("first and last points of the polygon must be the same (it must close itself): polyLons[0]=" + polyLons[0] + " polyLons[" + (polyLons.length-1) + "]=" + polyLons[polyLons.length-1]);
+ }
+
+ this.x = polyLons;
+ this.y = polyLats;
+ }
+
+ @Override @SuppressWarnings("unchecked")
+ protected TermsEnum getTermsEnum(final Terms terms, AttributeSource atts) throws IOException {
+ return new GeoPolygonTermsEnum(terms.iterator(), this.minLon, this.minLat, this.maxLon, this.maxLat);
+ }
+
+ /** throw exception if trying to change rewrite method */
+ @Override
+ 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;
+
+ GeoPointInPolygonQuery that = (GeoPointInPolygonQuery) o;
+
+ if (!Arrays.equals(x, that.x)) return false;
+ if (!Arrays.equals(y, that.y)) return false;
+
+ return true;
+ }
+
+ @Override
+ 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);
+ return result;
+ }
+
+ /** print out this polygon query */
+ @Override
+ public String toString(String field) {
+ assert x.length == y.length;
+
+ final StringBuilder sb = new StringBuilder();
+ sb.append(getClass().getSimpleName());
+ sb.append(':');
+ if (!getField().equals(field)) {
+ sb.append(" field=");
+ sb.append(getField());
+ sb.append(':');
+ }
+ sb.append(" Points: ");
+ for (int i=0; i<x.length; ++i) {
+ sb.append("[")
+ .append(x[i])
+ .append(", ")
+ .append(y[i])
+ .append("] ");
+ }
+
+ 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, final double minLon, final double minLat,
+ final double maxLon, final double maxLat) {
+ super(tenum, minLon, minLat, maxLon, maxLat);
+ }
+
+ @Override
+ protected boolean cellCrosses(final double minLon, final double minLat, final double maxLon, final double maxLat) {
+ return GeoRelationUtils.rectCrossesPolyApprox(minLon, minLat, maxLon, maxLat, x, y, GeoPointInPolygonQuery.this.minLon,
+ GeoPointInPolygonQuery.this.minLat, GeoPointInPolygonQuery.this.maxLon, GeoPointInPolygonQuery.this.maxLat);
+ }
+
+ @Override
+ protected boolean cellWithin(final double minLon, final double minLat, final double maxLon, final double maxLat) {
+ return GeoRelationUtils.rectWithinPolyApprox(minLon, minLat, maxLon, maxLat, x, y, GeoPointInPolygonQuery.this.minLon,
+ GeoPointInPolygonQuery.this.minLat, GeoPointInPolygonQuery.this.maxLon, GeoPointInPolygonQuery.this.maxLat);
+ }
+
+ @Override
+ protected boolean cellIntersectsShape(final double minLon, final double minLat, final double maxLon, final double maxLat) {
+ return cellContains(minLon, minLat, maxLon, maxLat) || cellWithin(minLon, minLat, maxLon, maxLat)
+ || cellCrosses(minLon, minLat, maxLon, maxLat);
+ }
+
+ /**
+ * The two-phase query approach. The parent
+ * {@link GeoPointTermsEnum#accept} method is called to match
+ * encoded terms that fall within the bounding box of the polygon. Those documents that pass the initial
+ * bounding box filter are then compared to the provided polygon using the
+ * {@link GeoRelationUtils#pointInPolygon} method.
+ */
+ @Override
+ protected boolean postFilter(final double lon, final double lat) {
+ return GeoRelationUtils.pointInPolygon(x, y, lat, lon);
+ }
+ }
+
+ /**
+ * 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;
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5b028349/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointTermQuery.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointTermQuery.java b/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointTermQuery.java
new file mode 100644
index 0000000..591619b
--- /dev/null
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointTermQuery.java
@@ -0,0 +1,115 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.spatial.search;
+
+import java.io.IOException;
+
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.index.Terms;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.MultiTermQuery;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.spatial.util.GeoUtils;
+import org.apache.lucene.util.AttributeSource;
+
+/**
+ * TermQuery for GeoPointField for overriding {@link org.apache.lucene.search.MultiTermQuery} methods specific to
+ * Geospatial operations
+ *
+ * @lucene.experimental
+ */
+abstract class GeoPointTermQuery extends MultiTermQuery {
+ // simple bounding box optimization - no objects used to avoid dependencies
+ /** minimum longitude value (in degrees) */
+ protected final double minLon;
+ /** minimum latitude value (in degrees) */
+ protected final double minLat;
+ /** maximum longitude value (in degrees) */
+ protected final double maxLon;
+ /** maximum latitude value (in degrees) */
+ protected final double maxLat;
+
+ /**
+ * Constructs a query matching terms that cannot be represented with a single
+ * Term.
+ */
+ public GeoPointTermQuery(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.minLon = minLon;
+ this.minLat = minLat;
+ this.maxLon = maxLon;
+ this.maxLat = maxLat;
+
+ this.rewriteMethod = GEO_CONSTANT_SCORE_REWRITE;
+ }
+
+ private static final RewriteMethod GEO_CONSTANT_SCORE_REWRITE = new RewriteMethod() {
+ @Override
+ public Query rewrite(IndexReader reader, MultiTermQuery query) {
+ return new GeoPointTermQueryConstantScoreWrapper<>((GeoPointTermQuery)query);
+ }
+ };
+
+ /** override package protected method */
+ @Override
+ protected abstract TermsEnum getTermsEnum(final Terms terms, AttributeSource atts) throws IOException;
+
+ /** check if this instance equals another instance */
+ @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;
+
+ GeoPointTermQuery that = (GeoPointTermQuery) o;
+
+ if (Double.compare(that.minLon, minLon) != 0) return false;
+ if (Double.compare(that.minLat, minLat) != 0) return false;
+ if (Double.compare(that.maxLon, maxLon) != 0) return false;
+ return Double.compare(that.maxLat, maxLat) == 0;
+
+ }
+
+ /** compute hashcode */
+ @Override
+ public int hashCode() {
+ int result = super.hashCode();
+ long temp;
+ temp = Double.doubleToLongBits(minLon);
+ result = 31 * result + (int) (temp ^ (temp >>> 32));
+ temp = Double.doubleToLongBits(minLat);
+ result = 31 * result + (int) (temp ^ (temp >>> 32));
+ temp = Double.doubleToLongBits(maxLon);
+ result = 31 * result + (int) (temp ^ (temp >>> 32));
+ temp = Double.doubleToLongBits(maxLat);
+ result = 31 * result + (int) (temp ^ (temp >>> 32));
+ return result;
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5b028349/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointTermQueryConstantScoreWrapper.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointTermQueryConstantScoreWrapper.java b/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointTermQueryConstantScoreWrapper.java
new file mode 100644
index 0000000..5bc42a3
--- /dev/null
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointTermQueryConstantScoreWrapper.java
@@ -0,0 +1,139 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.spatial.search;
+
+import java.io.IOException;
+
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.PostingsEnum;
+import org.apache.lucene.index.SortedNumericDocValues;
+import org.apache.lucene.index.Terms;
+import org.apache.lucene.search.BulkScorer;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSet;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.AttributeSource;
+import org.apache.lucene.util.DocIdSetBuilder;
+import org.apache.lucene.spatial.util.GeoUtils;
+
+/**
+ * Custom ConstantScoreWrapper for {@code GeoPointTermQuery} that cuts over to DocValues
+ * for post filtering boundary ranges. Multi-valued GeoPoint documents are supported.
+ *
+ * @lucene.experimental
+ */
+final class GeoPointTermQueryConstantScoreWrapper <Q extends GeoPointTermQuery> extends Query {
+ protected final Q query;
+
+ protected GeoPointTermQueryConstantScoreWrapper(Q query) {
+ this.query = query;
+ }
+
+ @Override
+ public String toString(String field) {
+ return query.toString();
+ }
+
+ @Override
+ public final boolean equals(final Object o) {
+ if (super.equals(o) == false) {
+ return false;
+ }
+ final GeoPointTermQueryConstantScoreWrapper<?> that = (GeoPointTermQueryConstantScoreWrapper<?>) o;
+ return this.query.equals(that.query);
+ }
+
+ @Override
+ public final int hashCode() {
+ return 31 * super.hashCode() + query.hashCode();
+ }
+
+ @Override
+ public Weight createWeight(IndexSearcher searcher, boolean needsScores) throws IOException {
+ return new ConstantScoreWeight(this) {
+
+ private DocIdSet getDocIDs(LeafReaderContext context) throws IOException {
+ final Terms terms = context.reader().terms(query.getField());
+ if (terms == null) {
+ return DocIdSet.EMPTY;
+ }
+
+ final GeoPointTermsEnum termsEnum = (GeoPointTermsEnum)(query.getTermsEnum(terms, new AttributeSource()));
+ assert termsEnum != null;
+
+ LeafReader reader = context.reader();
+ DocIdSetBuilder builder = new DocIdSetBuilder(reader.maxDoc());
+ PostingsEnum docs = null;
+ SortedNumericDocValues sdv = reader.getSortedNumericDocValues(query.getField());
+
+ while (termsEnum.next() != null) {
+ docs = termsEnum.postings(docs, PostingsEnum.NONE);
+ // boundary terms need post filtering by
+ if (termsEnum.boundaryTerm()) {
+ int docId = docs.nextDoc();
+ long hash;
+ do {
+ sdv.setDocument(docId);
+ for (int i=0; i<sdv.count(); ++i) {
+ hash = sdv.valueAt(i);
+ if (termsEnum.postFilter(GeoUtils.mortonUnhashLon(hash), GeoUtils.mortonUnhashLat(hash))) {
+ builder.add(docId);
+ break;
+ }
+ }
+ } while ((docId = docs.nextDoc()) != DocIdSetIterator.NO_MORE_DOCS);
+ } else {
+ builder.add(docs);
+ }
+ }
+
+ return builder.build();
+ }
+
+ private Scorer scorer(DocIdSet set) throws IOException {
+ if (set == null) {
+ return null;
+ }
+ final DocIdSetIterator disi = set.iterator();
+ if (disi == null) {
+ return null;
+ }
+ return new ConstantScoreScorer(this, score(), disi);
+ }
+
+ @Override
+ public BulkScorer bulkScorer(LeafReaderContext context) throws IOException {
+ final Scorer scorer = scorer(getDocIDs(context));
+ if (scorer == null) {
+ return null;
+ }
+ return new DefaultBulkScorer(scorer);
+ }
+
+ @Override
+ public Scorer scorer(LeafReaderContext context) throws IOException {
+ return scorer(getDocIDs(context));
+ }
+ };
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5b028349/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointTermsEnum.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointTermsEnum.java b/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointTermsEnum.java
new file mode 100644
index 0000000..71eb26e
--- /dev/null
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointTermsEnum.java
@@ -0,0 +1,249 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.spatial.search;
+
+import java.util.Collections;
+import java.util.LinkedList;
+import java.util.List;
+
+import org.apache.lucene.spatial.document.GeoPointField;
+import org.apache.lucene.index.FilteredTermsEnum;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.BytesRefBuilder;
+import org.apache.lucene.spatial.util.GeoRelationUtils;
+import org.apache.lucene.spatial.util.GeoUtils;
+import org.apache.lucene.util.LegacyNumericUtils;
+
+/**
+ * computes all ranges along a space-filling curve that represents
+ * the given bounding box and enumerates all terms contained within those ranges
+ *
+ * @lucene.experimental
+ */
+abstract class GeoPointTermsEnum extends FilteredTermsEnum {
+ protected final double minLon;
+ protected final double minLat;
+ protected final double maxLon;
+ protected final double maxLat;
+
+ protected Range currentRange;
+ private final BytesRefBuilder currentCell = new BytesRefBuilder();
+ private final BytesRefBuilder nextSubRange = new BytesRefBuilder();
+
+ 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)
+ protected final short DETAIL_LEVEL;
+
+ 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);
+ final long rectMaxHash = GeoUtils.mortonHash(maxLon, maxLat);
+ this.minLon = GeoUtils.mortonUnhashLon(rectMinHash);
+ this.minLat = GeoUtils.mortonUnhashLat(rectMinHash);
+ this.maxLon = GeoUtils.mortonUnhashLon(rectMaxHash);
+ this.maxLat = GeoUtils.mortonUnhashLat(rectMaxHash);
+ DETAIL_LEVEL = (short)(((GeoUtils.BITS<<1)-computeMaxShift())/2);
+
+ computeRange(0L, (short) ((GeoUtils.BITS << 1) - 1));
+ assert rangeBounds.isEmpty() == false;
+ Collections.sort(rangeBounds);
+ }
+
+ /**
+ * entry point for recursively computing ranges
+ */
+ private final void computeRange(long term, final short shift) {
+ final long split = term | (0x1L<<shift);
+ assert shift < 64;
+ final long upperMax;
+ if (shift < 63) {
+ upperMax = term | ((1L << (shift+1))-1);
+ } else {
+ upperMax = 0xffffffffffffffffL;
+ }
+ final long lowerMax = split-1;
+
+ relateAndRecurse(term, lowerMax, shift);
+ relateAndRecurse(split, upperMax, shift);
+ }
+
+ /**
+ * recurse to higher level precision cells to find ranges along the space-filling curve that fall within the
+ * query box
+ *
+ * @param start starting value on the space-filling curve for a cell at a given res
+ * @param end ending value on the space-filling curve for a cell at a given res
+ * @param res spatial res represented as a bit shift (MSB is lower res)
+ */
+ private void relateAndRecurse(final long start, final long end, final short res) {
+ final double minLon = GeoUtils.mortonUnhashLon(start);
+ final double minLat = GeoUtils.mortonUnhashLat(start);
+ final double maxLon = GeoUtils.mortonUnhashLon(end);
+ final double maxLat = GeoUtils.mortonUnhashLat(end);
+
+ final short level = (short)((GeoUtils.BITS<<1)-res>>>1);
+
+ // 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))) {
+ 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
+ */
+ protected abstract boolean cellCrosses(final double minLon, final double minLat, final double maxLon, final double maxLat);
+
+ /**
+ * Determine whether quad-cell is within the shape
+ */
+ protected abstract boolean cellWithin(final double minLon, final double minLat, final double maxLon, final double maxLat);
+
+ /**
+ * Default shape is a rectangle, so this returns the same as {@code cellIntersectsMBR}
+ */
+ protected abstract boolean cellIntersectsShape(final double minLon, final double minLat, final double maxLon, final double maxLat);
+
+ /**
+ * Primary driver for cells intersecting shape boundaries
+ */
+ protected boolean cellIntersectsMBR(final double minLon, final double minLat, final double maxLon, final double maxLat) {
+ return GeoRelationUtils.rectIntersects(minLon, minLat, maxLon, maxLat, this.minLon, this.minLat, this.maxLon, this.maxLat);
+ }
+
+ /**
+ * Return whether quad-cell contains the bounding box of this shape
+ */
+ protected boolean cellContains(final double minLon, final double minLat, final double maxLon, final double maxLat) {
+ return GeoRelationUtils.rectWithin(this.minLon, this.minLat, this.maxLon, this.maxLat, minLon, minLat, maxLon, maxLat);
+ }
+
+ public boolean boundaryTerm() {
+ if (currentRange == null) {
+ throw new IllegalStateException("GeoPointTermsEnum empty or not initialized");
+ }
+ return currentRange.boundary;
+ }
+
+ private void nextRange() {
+ currentRange = rangeBounds.remove(0);
+ currentRange.fillBytesRef(currentCell);
+ }
+
+ @Override
+ protected final BytesRef nextSeekTerm(BytesRef term) {
+ while (!rangeBounds.isEmpty()) {
+ if (currentRange == null) {
+ nextRange();
+ }
+
+ // if the new upper bound is before the term parameter, the sub-range is never a hit
+ if (term != null && term.compareTo(currentCell.get()) > 0) {
+ nextRange();
+ if (!rangeBounds.isEmpty()) {
+ continue;
+ }
+ }
+ // never seek backwards, so use current term if lower bound is smaller
+ return (term != null && term.compareTo(currentCell.get()) > 0) ?
+ term : currentCell.get();
+ }
+
+ // no more sub-range enums available
+ assert rangeBounds.isEmpty();
+ return null;
+ }
+
+ /**
+ * The two-phase query approach. {@link #nextSeekTerm} is called to obtain the next term that matches a numeric
+ * range of the bounding box. Those terms that pass the initial range filter are then compared against the
+ * decoded min/max latitude and longitude values of the bounding box only if the range is not a "boundary" range
+ * (e.g., a range that straddles the boundary of the bbox).
+ * @param term term for candidate document
+ * @return match status
+ */
+ @Override
+ protected AcceptStatus accept(BytesRef term) {
+ // validate value is in range
+ while (currentCell == null || term.compareTo(currentCell.get()) > 0) {
+ if (rangeBounds.isEmpty()) {
+ return AcceptStatus.END;
+ }
+ // peek next sub-range, only seek if the current term is smaller than next lower bound
+ rangeBounds.get(0).fillBytesRef(this.nextSubRange);
+ if (term.compareTo(this.nextSubRange.get()) < 0) {
+ return AcceptStatus.NO_AND_SEEK;
+ }
+ // step forward to next range without seeking, as next range is less or equal current term
+ nextRange();
+ }
+
+ return AcceptStatus.YES;
+ }
+
+ protected abstract boolean postFilter(final double lon, final double lat);
+
+ /**
+ * Internal class to represent a range along the space filling curve
+ */
+ protected final class Range implements Comparable<Range> {
+ final short shift;
+ final long start;
+ final boolean boundary;
+
+ Range(final long lower, final short shift, boolean boundary) {
+ this.boundary = boundary;
+ this.start = lower;
+ this.shift = shift;
+ }
+
+ /**
+ * Encode as a BytesRef using a reusable object. This allows us to lazily create the BytesRef (which is
+ * quite expensive), only when we need it.
+ */
+ private void fillBytesRef(BytesRefBuilder result) {
+ assert result != null;
+ LegacyNumericUtils.longToPrefixCoded(start, shift, result);
+ }
+
+ @Override
+ public int compareTo(Range other) {
+ final int result = Short.compare(this.shift, other.shift);
+ if (result == 0) {
+ return Long.compare(this.start, other.start);
+ }
+ return result;
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5b028349/lucene/spatial/src/java/org/apache/lucene/spatial/search/package-info.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/search/package-info.java b/lucene/spatial/src/java/org/apache/lucene/spatial/search/package-info.java
new file mode 100644
index 0000000..8e8265c
--- /dev/null
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/search/package-info.java
@@ -0,0 +1,21 @@
+/*
+ * 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.
+ */
+
+/**
+ * Geospatial Query Implementations for Core Lucene
+ */
+package org.apache.lucene.spatial.search;
\ No newline at end of file