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/05/29 15:18:03 UTC
svn commit: r1682453 - in
/lucene/dev/branches/LUCENE-6481/lucene/sandbox/src/java/org/apache/lucene:
search/GeoBoundingBox.java search/GeoPointInBBoxQuery.java
search/GeoPointInPolygonQuery.java util/GeoUtils.java
Author: mikemccand
Date: Fri May 29 13:18:03 2015
New Revision: 1682453
URL: http://svn.apache.org/r1682453
Log:
LUCENE-6481: Nick's latest patch: create range terms once per query, not per segment; check cell intersection against polygon not its bbox for more restrictive recursing
Modified:
lucene/dev/branches/LUCENE-6481/lucene/sandbox/src/java/org/apache/lucene/search/GeoBoundingBox.java
lucene/dev/branches/LUCENE-6481/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInBBoxQuery.java
lucene/dev/branches/LUCENE-6481/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInPolygonQuery.java
lucene/dev/branches/LUCENE-6481/lucene/sandbox/src/java/org/apache/lucene/util/GeoUtils.java
Modified: lucene/dev/branches/LUCENE-6481/lucene/sandbox/src/java/org/apache/lucene/search/GeoBoundingBox.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/LUCENE-6481/lucene/sandbox/src/java/org/apache/lucene/search/GeoBoundingBox.java?rev=1682453&r1=1682452&r2=1682453&view=diff
==============================================================================
--- lucene/dev/branches/LUCENE-6481/lucene/sandbox/src/java/org/apache/lucene/search/GeoBoundingBox.java (original)
+++ lucene/dev/branches/LUCENE-6481/lucene/sandbox/src/java/org/apache/lucene/search/GeoBoundingBox.java Fri May 29 13:18:03 2015
@@ -19,7 +19,7 @@ package org.apache.lucene.search;
import org.apache.lucene.util.GeoUtils;
-/** NOTE: package private; just used so {@link GeoPointInBBoxQuery} can communicate its bounding box to {@link GeoPointInBBoxQuery}. */
+/** NOTE: package private; just used so {@link GeoPointInPolygonQuery} can communicate its bounding box to {@link GeoPointInBBoxQuery}. */
class GeoBoundingBox {
public final double minLon;
public final double maxLon;
Modified: lucene/dev/branches/LUCENE-6481/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInBBoxQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/LUCENE-6481/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInBBoxQuery.java?rev=1682453&r1=1682452&r2=1682453&view=diff
==============================================================================
--- lucene/dev/branches/LUCENE-6481/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInBBoxQuery.java (original)
+++ lucene/dev/branches/LUCENE-6481/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInBBoxQuery.java Fri May 29 13:18:03 2015
@@ -18,18 +18,11 @@ package org.apache.lucene.search;
*/
import java.io.IOException;
-import java.util.Collections;
-import java.util.LinkedList;
-import org.apache.lucene.document.GeoPointField;
-import org.apache.lucene.index.FilteredTermsEnum;
import org.apache.lucene.index.Terms;
import org.apache.lucene.index.TermsEnum;
import org.apache.lucene.util.AttributeSource;
-import org.apache.lucene.util.BytesRef;
-import org.apache.lucene.util.BytesRefBuilder;
import org.apache.lucene.util.GeoUtils;
-import org.apache.lucene.util.NumericUtils;
import org.apache.lucene.util.ToStringUtils;
/** Implements a simple bounding box query on a GeoPoint field. This is inspired by
@@ -57,8 +50,6 @@ public class GeoPointInBBoxQuery extends
protected final double maxLon;
protected final double maxLat;
- private static final short DETAIL_LEVEL = 16;
-
/**
* 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
@@ -95,7 +86,7 @@ public class GeoPointInBBoxQuery extends
if (min != null && max != null && min.compareTo(max) > 0) {
return TermsEnum.EMPTY;
}
- return new GeoBBoxTermsEnum(terms.iterator());
+ return new GeoPointTermsEnum(terms.iterator(), atts, minLon, minLat, maxLon, maxLat);
}
@Override
@@ -153,161 +144,4 @@ public class GeoPointInBBoxQuery extends
.append(ToStringUtils.boost(getBoost()))
.toString();
}
-
- /**
- * computes all ranges along a space-filling curve that represents
- * the given bounding box and enumerates all terms contained within those ranges
- */
- protected class GeoBBoxTermsEnum extends FilteredTermsEnum {
- private Range currentRange;
- private BytesRef currentLowerBound, currentUpperBound;
- private final LinkedList<Range> rangeBounds = new LinkedList<>();
-
- GeoBBoxTermsEnum(final TermsEnum tenum) {
- super(tenum);
- computeRange(0L, (short) (((GeoUtils.BITS) << 1) - 1));
- Collections.sort(rangeBounds);
- }
-
- /**
- * entry point for recursively computing ranges
- */
- private final void computeRange(long term, final short shift) {
- final long split = term | (0x1L<<shift);
- final long upperMax = term | ((0x1L<<(shift+1))-1);
- 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)(62-res>>>1);
-
- final boolean within = isWithin(minLon, minLat, maxLon, maxLat);
- final boolean bboxIntersects = (within) ? true : intersects(minLon, minLat, maxLon, maxLat);
-
- if ((within && res%GeoPointField.PRECISION_STEP == 0) || (bboxIntersects && level == DETAIL_LEVEL)) {
- rangeBounds.add(new Range(start, end, res, level, !within));
- } else if (bboxIntersects) {
- computeRange(start, (short)(res - 1));
- }
- }
-
- protected boolean intersects(final double minLon, final double minLat, final double maxLon, final double maxLat) {
- return GeoUtils.rectIntersects(minLon, minLat, maxLon, maxLat, GeoPointInBBoxQuery.this.minLon,
- GeoPointInBBoxQuery.this.minLat, GeoPointInBBoxQuery.this.maxLon, GeoPointInBBoxQuery.this.maxLat);
- }
-
- protected boolean isWithin(final double minLon, final double minLat, final double maxLon, final double maxLat) {
- return GeoUtils.rectIsWithin(minLon, minLat, maxLon, maxLat, GeoPointInBBoxQuery.this.minLon,
- GeoPointInBBoxQuery.this.minLat, GeoPointInBBoxQuery.this.maxLon, GeoPointInBBoxQuery.this.maxLat);
- }
-
- private void nextRange() {
- currentRange = rangeBounds.removeFirst();
- currentLowerBound = currentRange.lower;
- assert currentUpperBound == null || currentUpperBound.compareTo(currentRange.lower) <= 0 :
- "The current upper bound must be <= the new lower bound";
-
- currentUpperBound = currentRange.upper;
- }
-
- @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(currentUpperBound) > 0) {
- nextRange();
- if (!rangeBounds.isEmpty()) {
- continue;
- }
- }
- // never seek backwards, so use current term if lower bound is smaller
- return (term != null && term.compareTo(currentLowerBound) > 0) ?
- term : currentLowerBound;
- }
-
- // no more sub-range enums available
- assert rangeBounds.isEmpty();
- currentLowerBound = currentUpperBound = null;
- 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 (currentUpperBound == null || term.compareTo(currentUpperBound) > 0) {
- 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)
- return AcceptStatus.NO_AND_SEEK;
- // step forward to next range without seeking, as next lower range bound is less or equal current term
- nextRange();
- }
-
- // final-filter boundary ranges by bounding box
- if (currentRange.boundary) {
- final long val = NumericUtils.prefixCodedToLong(term);
- final double lon = GeoUtils.mortonUnhashLon(val);
- final double lat = GeoUtils.mortonUnhashLat(val);
- if (!GeoUtils.bboxContains(lon, lat, minLon, minLat, maxLon, maxLat)) {
- return AcceptStatus.NO;
- }
- }
- return AcceptStatus.YES;
- }
-
- /**
- * Internal class to represent a range along the space filling curve
- */
- private final class Range implements Comparable<Range> {
- final BytesRef lower;
- final BytesRef upper;
- final short level;
- final boolean boundary;
-
- Range(final long lower, final long upper, final short res, final short level, boolean boundary) {
- this.level = level;
- this.boundary = boundary;
-
- BytesRefBuilder brb = new BytesRefBuilder();
- NumericUtils.longToPrefixCodedBytes(lower, boundary ? 0 : res, brb);
- this.lower = brb.get();
- NumericUtils.longToPrefixCodedBytes(upper, boundary ? 0 : res, (brb = new BytesRefBuilder()));
- this.upper = brb.get();
- }
-
- @Override
- public final int compareTo(Range other) {
- return this.lower.compareTo(other.lower);
- }
- }
- }
}
Modified: lucene/dev/branches/LUCENE-6481/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInPolygonQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/LUCENE-6481/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInPolygonQuery.java?rev=1682453&r1=1682452&r2=1682453&view=diff
==============================================================================
--- lucene/dev/branches/LUCENE-6481/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInPolygonQuery.java (original)
+++ lucene/dev/branches/LUCENE-6481/lucene/sandbox/src/java/org/apache/lucene/search/GeoPointInPolygonQuery.java Fri May 29 13:18:03 2015
@@ -109,7 +109,7 @@ public final class GeoPointInPolygonQuer
if (min != null && max != null && min.compareTo(max) > 0) {
return TermsEnum.EMPTY;
}
- return new GeoPolygonTermsEnum(terms.iterator());
+ return new GeoPolygonTermsEnum(terms.iterator(), atts, minLon, minLat, maxLon, maxLat);
}
@Override
@@ -159,19 +159,33 @@ public final class GeoPointInPolygonQuer
return sb.toString();
}
- private final class GeoPolygonTermsEnum extends GeoBBoxTermsEnum {
- GeoPolygonTermsEnum(final TermsEnum tenum) {
- super(tenum);
+ private final class GeoPolygonTermsEnum extends GeoPointTermsEnum {
+ GeoPolygonTermsEnum(final TermsEnum tenum, AttributeSource atts, final double minLon, final double minLat,
+ final double maxLon, final double maxLat) {
+ super(tenum, atts, minLon, minLat, maxLon, maxLat);
}
@Override
- protected boolean isWithin(final double minLon, final double minLat, final double maxLon, final double maxLat) {
- return GeoUtils.rectIsWithin(minLon, minLat, maxLon, maxLat, x, y);
+ protected boolean cellCrosses(final double minLon, final double minLat, final double maxLon, final double maxLat) {
+ return GeoUtils.rectCrossesPoly(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 GeoUtils.rectWithinPoly(minLon, minLat, maxLon, maxLat, x, y, GeoPointInPolygonQuery.this.minLon,
+ GeoPointInPolygonQuery.this.minLat, GeoPointInPolygonQuery.this.maxLon, GeoPointInPolygonQuery.this.maxLat);
+ }
+
+ @Override
+ protected boolean cellIntersects(final double minLon, final double minLat, final double maxLon, final double maxLat) {
+ return GeoUtils.rectIntersects(minLon, minLat, maxLon, maxLat, GeoPointInPolygonQuery.this.minLon,
+ GeoPointInPolygonQuery.this.minLat, GeoPointInPolygonQuery.this.maxLon, GeoPointInPolygonQuery.this.maxLat);
}
/**
* The two-phase query approach. The parent
- * {@link org.apache.lucene.search.GeoPointInBBoxQuery.GeoBBoxTermsEnum#accept} method is called to match
+ * {@link org.apache.lucene.search.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 org.apache.lucene.util.GeoUtils#pointInPolygon} method.
Modified: lucene/dev/branches/LUCENE-6481/lucene/sandbox/src/java/org/apache/lucene/util/GeoUtils.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/LUCENE-6481/lucene/sandbox/src/java/org/apache/lucene/util/GeoUtils.java?rev=1682453&r1=1682452&r2=1682453&view=diff
==============================================================================
--- lucene/dev/branches/LUCENE-6481/lucene/sandbox/src/java/org/apache/lucene/util/GeoUtils.java (original)
+++ lucene/dev/branches/LUCENE-6481/lucene/sandbox/src/java/org/apache/lucene/util/GeoUtils.java Fri May 29 13:18:03 2015
@@ -241,16 +241,28 @@ public final class GeoUtils {
return s.toString();
}
+
+ public static boolean rectDisjoint(final double aMinX, final double aMinY, final double aMaxX, final double aMaxY,
+ final double bMinX, final double bMinY, final double bMaxX, final double bMaxY) {
+ return (aMaxX < bMinX || aMinX > bMaxX || aMaxY < bMinY || aMinY > bMaxY);
+ }
+
/**
* Computes whether a rectangle is wholly within another rectangle (shared boundaries allowed)
*/
- public static boolean rectIsWithin(final double aMinX, final double aMinY, final double aMaxX, final double aMaxY,
- final double bMinX, final double bMinY, final double bMaxX, final double bMaxY) {
+ public static boolean rectWithin(final double aMinX, final double aMinY, final double aMaxX, final double aMaxY,
+ final double bMinX, final double bMinY, final double bMaxX, final double bMaxY) {
return !(aMinX < bMinX || aMinY < bMinY || aMaxX > bMaxX || aMaxY > bMaxY);
}
+ public static boolean rectCrosses(final double aMinX, final double aMinY, final double aMaxX, final double aMaxY,
+ final double bMinX, final double bMinY, final double bMaxX, final double bMaxY) {
+ return !(rectDisjoint(aMinX, aMinY, aMaxX, aMaxY, bMinX, bMinY, bMaxX, bMaxY) ||
+ rectWithin(aMinX, aMinY, aMaxX, aMaxY, bMinX, bMinY, bMaxX, bMaxY));
+ }
+
/**
- * Computes whether a rectangle intersects another rectangle
+ * Computes whether rectangle a contains rectangle b (touching allowed)
*/
public static boolean rectContains(final double aMinX, final double aMinY, final double aMaxX, final double aMaxY,
final double bMinX, final double bMinY, final double bMaxX, final double bMaxY) {
@@ -258,7 +270,7 @@ public final class GeoUtils {
}
/**
- * Computes whether a rectangle contains another rectangle
+ * Computes whether a rectangle intersects another rectangle (crosses, within, touching, etc)
*/
public static boolean rectIntersects(final double aMinX, final double aMinY, final double aMaxX, final double aMaxY,
final double bMinX, final double bMinY, final double bMaxX, final double bMaxY) {
@@ -266,12 +278,66 @@ public final class GeoUtils {
}
/**
- * Computes whether a rectangle is wholly within a given shape (shared boundaries allowed)
+ * Computes whether a rectangle crosses a shape. (touching not allowed)
*/
- public static boolean rectIsWithin(final double rMinX, final double rMinY, final double rMaxX, final double rMaxY,
- final double[] shapeX, final double[] shapeY) {
- // nocommit is this really correct? poly can be convex, and then all 4 bbox corners can be within it, yet not fully contained?
- return !(!pointInPolygon(shapeX, shapeY, rMinY, rMinX) || !pointInPolygon(shapeX, shapeY, rMinY, rMaxX) ||
+ 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) {
+ // short-circuit: if the bounding boxes are disjoint then the shape does not cross
+ if (rectDisjoint(rMinX, rMinY, rMaxX, rMaxY, sMinX, sMinY, sMaxX, sMaxY))
+ return false;
+
+ final double[][] bbox = new double[][] { {rMinX, rMinY}, {rMaxX, rMinY}, {rMaxX, rMaxY}, {rMinX, rMaxY}, {rMinX, rMinY} };
+ final int polyLength = shapeX.length-1;
+ double d, s, t, a1, b1, c1, a2, b2, c2;
+ double x00, y00, x01, y01, x10, y10, x11, y11;
+
+ // computes the intersection point between each bbox edge and the polygon edge
+ for (short b=0; b<4; ++b) {
+ a1 = bbox[b+1][1]-bbox[b][1];
+ b1 = bbox[b][0]-bbox[b+1][0];
+ c1 = a1*bbox[b+1][0] + b1*bbox[b+1][1];
+ for (int p=0; p<polyLength; ++p) {
+ a2 = shapeY[p+1]-shapeY[p];
+ b2 = shapeX[p]-shapeX[p+1];
+ // compute determinant
+ d = a1*b2 - a2*b1;
+ if (d != 0) {
+ // lines are not parallel, check intersecting points
+ c2 = a2*shapeX[p+1] + b2*shapeY[p+1];
+ s = (1/d)*(b2*c1 - b1*c2);
+ t = (1/d)*(a1*c2 - a2*c1);
+ x00 = StrictMath.min(bbox[b][0], bbox[b+1][0]) - TOLERANCE;
+ x01 = StrictMath.max(bbox[b][0], bbox[b+1][0]) + TOLERANCE;
+ y00 = StrictMath.min(bbox[b][1], bbox[b+1][1]) - TOLERANCE;
+ y01 = StrictMath.max(bbox[b][1], bbox[b+1][1]) + TOLERANCE;
+ x10 = StrictMath.min(shapeX[p], shapeX[p+1]) - TOLERANCE;
+ x11 = StrictMath.max(shapeX[p], shapeX[p+1]) + TOLERANCE;
+ y10 = StrictMath.min(shapeY[p], shapeY[p+1]) - TOLERANCE;
+ y11 = StrictMath.max(shapeY[p], shapeY[p+1]) + TOLERANCE;
+ // check whether the intersection point is touching one of the line segments
+ boolean touching = ((x00 == s && y00 == t) || (x01 == s && y01 == t))
+ || ((x10 == s && y10 == t) || (x11 == s && y11 == t));
+ // if line segments are not touching and the intersection point is within the range of either segment
+ if (!(touching || x00 > s || x01 < s || y00 > t || y01 < t || x10 > s || x11 < s || y10 > t || y11 < t))
+ return true;
+ }
+ } // for each poly edge
+ } // for each bbox edge
+ return false;
+ }
+
+ /**
+ * 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,
+ final double[] shapeX, final double[] shapeY, final double sMinX,
+ final double sMinY, final double sMaxX, final double sMaxY) {
+ // check if rectangle crosses poly (to handle concave/pacman polys), then check that all 4 corners
+ // are contained
+ return !(rectCrossesPoly(rMinX, rMinY, rMaxX, rMaxY, shapeX, shapeY, sMinX, sMinY, sMaxX, sMaxY) ||
+ !pointInPolygon(shapeX, shapeY, rMinY, rMinX) || !pointInPolygon(shapeX, shapeY, rMinY, rMaxX) ||
!pointInPolygon(shapeX, shapeY, rMaxY, rMaxX) || !pointInPolygon(shapeX, shapeY, rMaxY, rMinX));
}
@@ -282,4 +348,53 @@ public final class GeoUtils {
public static boolean isValidLon(double lon) {
return Double.isNaN(lon) == false && lon >= MIN_LON_INCL && lon <= MAX_LON_INCL;
}
+
+ // nocommit add these to unit test
+ public static void main(String[] args) {
+ // pacman
+ double[] px = {0, 10, 10, 0, -8, -10, -8, 0, 10, 10, 0};
+ double[] py = {0, 5, 9, 10, 9, 0, -9, -10, -9, -5, 0};
+
+ // bbox
+ double xMinA = -10;
+ double xMaxA = 10;
+ double yMinA = -10;
+ double yMaxA = 10;
+
+ // candidate cell
+ double xMin = 2;//-5;
+ double xMax = 11;//0.000001;
+ double yMin = -1;//0;
+ double yMax = 1;//5;
+
+ System.out.println("CELL AND POLY\n--------------");
+ // cell crosses poly (touching not allowed)
+ if (rectCrossesPoly(xMin, yMin, xMax, yMax, px, py, -10, -10, 10, 10)) {
+ System.out.println("CROSSES");
+ } else {
+ System.out.println("NO CROSS");
+ }
+
+ // cell within poly (touching allowed)
+ if (rectWithinPoly(xMin, yMin, xMax, yMax, px, py, -10, -10, 10, 10)) {
+ System.out.println("WITHIN");
+ } else {
+ System.out.println("NOT WITHIN");
+ }
+
+ System.out.println("\nCELL AND BBOX\n--------------");
+ // cell crosses poly (touching not allowed)
+ if (rectCrosses(xMin, yMin, xMax, yMax, xMinA, yMinA, xMaxA, yMaxA)) {
+ System.out.println("CROSSES");
+ } else {
+ System.out.println("NO CROSS");
+ }
+
+ // cell within poly (touching allowed)
+ if (rectWithin(xMin, yMin, xMax, yMax, xMinA, yMinA, xMaxA, yMaxA)) {
+ System.out.println("WITHIN");
+ } else {
+ System.out.println("NOT WITHIN");
+ }
+ }
}