You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by da...@apache.org on 2018/12/15 10:03:57 UTC
[05/34] lucene-solr:jira/http2: LUCENE-8605: Separate bounding box
spatial logic from query logic on LatLonShapeBoundingBoxQuery
LUCENE-8605: Separate bounding box spatial logic from query logic on LatLonShapeBoundingBoxQuery
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/ce9a8012
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/ce9a8012
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/ce9a8012
Branch: refs/heads/jira/http2
Commit: ce9a8012c080dbf2a96a6755a0b7048ab5739419
Parents: 55993ec
Author: iverase <iv...@apache.org>
Authored: Wed Dec 12 13:46:35 2018 +0100
Committer: iverase <iv...@apache.org>
Committed: Wed Dec 12 13:46:35 2018 +0100
----------------------------------------------------------------------
lucene/CHANGES.txt | 3 +
.../document/LatLonShapeBoundingBoxQuery.java | 269 +---------------
.../java/org/apache/lucene/geo/Rectangle2D.java | 315 +++++++++++++++++++
.../org/apache/lucene/geo/TestRectangle2D.java | 100 ++++++
4 files changed, 428 insertions(+), 259 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/ce9a8012/lucene/CHANGES.txt
----------------------------------------------------------------------
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 212607f..b4c7ca5 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -276,6 +276,9 @@ Other
* LUCENE-8573: BKDWriter now uses FutureArrays#mismatch to compute shared prefixes.
(Christoph Büscher via Adrien Grand)
+* LUCENE-8605: Separate bounding box spatial logic from query logic on LatLonShapeBoundingBoxQuery.
+ (Ignacio Vera)
+
======================= Lucene 7.6.0 =======================
Build
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/ce9a8012/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java
index ebbdeed..43fe28e 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java
@@ -16,25 +16,11 @@
*/
package org.apache.lucene.document;
-import java.util.Arrays;
-
import org.apache.lucene.geo.Rectangle;
-import org.apache.lucene.geo.Tessellator;
+import org.apache.lucene.geo.Rectangle2D;
import org.apache.lucene.index.PointValues.Relation;
-import org.apache.lucene.util.FutureArrays;
import org.apache.lucene.util.NumericUtils;
-import static org.apache.lucene.document.LatLonShape.BYTES;
-import static org.apache.lucene.geo.GeoEncodingUtils.MAX_LON_ENCODED;
-import static org.apache.lucene.geo.GeoEncodingUtils.MIN_LON_ENCODED;
-import static org.apache.lucene.geo.GeoEncodingUtils.decodeLatitude;
-import static org.apache.lucene.geo.GeoEncodingUtils.decodeLongitude;
-import static org.apache.lucene.geo.GeoEncodingUtils.encodeLatitude;
-import static org.apache.lucene.geo.GeoEncodingUtils.encodeLatitudeCeil;
-import static org.apache.lucene.geo.GeoEncodingUtils.encodeLongitude;
-import static org.apache.lucene.geo.GeoEncodingUtils.encodeLongitudeCeil;
-import static org.apache.lucene.geo.GeoUtils.orient;
-
/**
* Finds all previously indexed shapes that intersect the specified bounding box.
*
@@ -44,88 +30,18 @@ import static org.apache.lucene.geo.GeoUtils.orient;
* @lucene.experimental
**/
final class LatLonShapeBoundingBoxQuery extends LatLonShapeQuery {
- final byte[] bbox;
- final byte[] west;
- final int minX;
- final int maxX;
- final int minY;
- final int maxY;
+ final Rectangle2D rectangle2D;
public LatLonShapeBoundingBoxQuery(String field, LatLonShape.QueryRelation queryRelation, double minLat, double maxLat, double minLon, double maxLon) {
super(field, queryRelation);
-
- this.bbox = new byte[4 * LatLonShape.BYTES];
- int minXenc = encodeLongitudeCeil(minLon);
- int maxXenc = encodeLongitude(maxLon);
- int minYenc = encodeLatitudeCeil(minLat);
- int maxYenc = encodeLatitude(maxLat);
- if (minYenc > maxYenc) {
- minYenc = maxYenc;
- }
- this.minY = minYenc;
- this.maxY = maxYenc;
-
- if (minLon > maxLon == true) {
- // crossing dateline is split into east/west boxes
- this.west = new byte[4 * LatLonShape.BYTES];
- this.minX = minXenc;
- this.maxX = maxXenc;
- encode(MIN_LON_ENCODED, this.maxX, this.minY, this.maxY, this.west);
- encode(this.minX, MAX_LON_ENCODED, this.minY, this.maxY, this.bbox);
- } else {
- // encodeLongitudeCeil may cause minX to be > maxX iff
- // the delta between the longtude < the encoding resolution
- if (minXenc > maxXenc) {
- minXenc = maxXenc;
- }
- this.west = null;
- this.minX = minXenc;
- this.maxX = maxXenc;
- encode(this.minX, this.maxX, this.minY, this.maxY, bbox);
- }
- }
-
- /** encodes a bounding box into the provided byte array */
- private static void encode(final int minX, final int maxX, final int minY, final int maxY, byte[] b) {
- if (b == null) {
- b = new byte[4 * LatLonShape.BYTES];
- }
- LatLonShape.encodeTriangleBoxVal(minY, b, 0);
- LatLonShape.encodeTriangleBoxVal(minX, b, BYTES);
- LatLonShape.encodeTriangleBoxVal(maxY, b, 2 * BYTES);
- LatLonShape.encodeTriangleBoxVal(maxX, b, 3 * BYTES);
+ Rectangle rectangle = new Rectangle(minLat, maxLat, minLon, maxLon);
+ this.rectangle2D = Rectangle2D.create(rectangle);
}
@Override
protected Relation relateRangeBBoxToQuery(int minXOffset, int minYOffset, byte[] minTriangle,
int maxXOffset, int maxYOffset, byte[] maxTriangle) {
- Relation eastRelation = compareBBoxToRangeBBox(this.bbox, minXOffset, minYOffset, minTriangle, maxXOffset, maxYOffset, maxTriangle);
- if (this.crossesDateline() && eastRelation == Relation.CELL_OUTSIDE_QUERY) {
- return compareBBoxToRangeBBox(this.west, minXOffset, minYOffset, minTriangle, maxXOffset, maxYOffset, maxTriangle);
- }
-
- return eastRelation;
- }
-
- /** static utility method to compare a bbox with a range of triangles (just the bbox of the triangle collection) */
- protected static Relation compareBBoxToRangeBBox(final byte[] bbox,
- int minXOffset, int minYOffset, byte[] minTriangle,
- int maxXOffset, int maxYOffset, byte[] maxTriangle) {
- // check bounding box (DISJOINT)
- if (FutureArrays.compareUnsigned(minTriangle, minXOffset, minXOffset + BYTES, bbox, 3 * BYTES, 4 * BYTES) > 0 ||
- FutureArrays.compareUnsigned(maxTriangle, maxXOffset, maxXOffset + BYTES, bbox, BYTES, 2 * BYTES) < 0 ||
- FutureArrays.compareUnsigned(minTriangle, minYOffset, minYOffset + BYTES, bbox, 2 * BYTES, 3 * BYTES) > 0 ||
- FutureArrays.compareUnsigned(maxTriangle, maxYOffset, maxYOffset + BYTES, bbox, 0, BYTES) < 0) {
- return Relation.CELL_OUTSIDE_QUERY;
- }
-
- if (FutureArrays.compareUnsigned(minTriangle, minXOffset, minXOffset + BYTES, bbox, BYTES, 2 * BYTES) >= 0 &&
- FutureArrays.compareUnsigned(maxTriangle, maxXOffset, maxXOffset + BYTES, bbox, 3 * BYTES, 4 * BYTES) <= 0 &&
- FutureArrays.compareUnsigned(minTriangle, minYOffset, minYOffset + BYTES, bbox, 0, BYTES) >= 0 &&
- FutureArrays.compareUnsigned(maxTriangle, maxYOffset, maxYOffset + BYTES, bbox, 2 * BYTES, 3 * BYTES) <= 0) {
- return Relation.CELL_INSIDE_QUERY;
- }
- return Relation.CELL_CROSSES_QUERY;
+ return rectangle2D.relateRangeBBox(minXOffset, minYOffset, minTriangle, maxXOffset, maxYOffset, maxTriangle);
}
/** returns true if the query matches the encoded triangle */
@@ -144,160 +60,9 @@ final class LatLonShapeBoundingBoxQuery extends LatLonShapeQuery {
int cY = (int)(c & 0x00000000FFFFFFFFL);
if (queryRelation == LatLonShape.QueryRelation.WITHIN) {
- return queryContainsTriangle(aX, aY, bX, bY, cX, cY);
- }
- return queryMatches(aX, aY, bX, bY, cX, cY);
- }
-
- private boolean queryContainsTriangle(int ax, int ay, int bx, int by, int cx, int cy) {
- if (this.crossesDateline() == true) {
- return bboxContainsTriangle(ax, ay, bx, by, cx, cy, MIN_LON_ENCODED, this.maxX, this.minY, this.maxY)
- || bboxContainsTriangle(ax, ay, bx, by, cx, cy, this.minX, MAX_LON_ENCODED, this.minY, this.maxY);
- }
- return bboxContainsTriangle(ax, ay, bx, by, cx, cy, minX, maxX, minY, maxY);
- }
-
- /** static utility method to check if a bounding box contains a point */
- private static boolean bboxContainsPoint(int x, int y, int minX, int maxX, int minY, int maxY) {
- return (x < minX || x > maxX || y < minY || y > maxY) == false;
- }
-
- /** static utility method to check if a bounding box contains a triangle */
- private static boolean bboxContainsTriangle(int ax, int ay, int bx, int by, int cx, int cy,
- int minX, int maxX, int minY, int maxY) {
- return bboxContainsPoint(ax, ay, minX, maxX, minY, maxY)
- && bboxContainsPoint(bx, by, minX, maxX, minY, maxY)
- && bboxContainsPoint(cx, cy, minX, maxX, minY, maxY);
- }
-
- /** instance method to check if query box contains point */
- private boolean queryContainsPoint(int x, int y) {
- if (this.crossesDateline() == true) {
- return bboxContainsPoint(x, y, MIN_LON_ENCODED, this.maxX, this.minY, this.maxY)
- || bboxContainsPoint(x, y, this.minX, MAX_LON_ENCODED, this.minY, this.maxY);
- }
- return bboxContainsPoint(x, y, this.minX, this.maxX, this.minY, this.maxY);
- }
-
- protected boolean queryMatches(int aX, int aY, int bX, int bY, int cX, int cY) {
- // 1. query contains any triangle points
- if (queryContainsPoint(aX, aY) || queryContainsPoint(bX, bY) || queryContainsPoint(cX, cY)) {
- return true;
- }
-
- // compute bounding box of triangle
- int tMinX = StrictMath.min(StrictMath.min(aX, bX), cX);
- int tMaxX = StrictMath.max(StrictMath.max(aX, bX), cX);
- int tMinY = StrictMath.min(StrictMath.min(aY, bY), cY);
- int tMaxY = StrictMath.max(StrictMath.max(aY, bY), cY);
-
- // 2. check bounding boxes are disjoint
- if (this.crossesDateline() == true) {
- if (boxesAreDisjoint(tMinX, tMaxX, tMinY, tMaxY, MIN_LON_ENCODED, this.maxX, this.minY, this.maxY)
- && boxesAreDisjoint(tMinX, tMaxX, tMinY, tMaxY, this.minX, MAX_LON_ENCODED, this.minY, this.maxY)) {
- return false;
- }
- } else if (tMaxX < minX || tMinX > maxX || tMinY > maxY || tMaxY < minY) {
- return false;
+ return rectangle2D.containsTriangle(aX, aY, bX, bY, cX, cY);
}
-
- // 3. check triangle contains any query points
- if (Tessellator.pointInTriangle(minX, minY, aX, aY, bX, bY, cX, cY)) {
- return true;
- } else if (Tessellator.pointInTriangle(maxX, minY, aX, aY, bX, bY, cX, cY)) {
- return true;
- } else if (Tessellator.pointInTriangle(maxX, maxY, aX, aY, bX, bY, cX, cY)) {
- return true;
- } else if (Tessellator.pointInTriangle(minX, maxY, aX, aY, bX, bY, cX, cY)) {
- return true;
- }
-
- // 4. last ditch effort: check crossings
- if (queryIntersects(aX, aY, bX, bY, cX, cY)) {
- return true;
- }
- return false;
- }
-
- /** returns true if the edge (defined by (ax, ay) (bx, by)) intersects the query */
- private static boolean edgeIntersectsBox(int ax, int ay, int bx, int by,
- int minX, int maxX, int minY, int maxY) {
- // shortcut: if edge is a point (occurs w/ Line shapes); simply check bbox w/ point
- if (ax == bx && ay == by) {
- return Rectangle.containsPoint(ay, ax, minY, maxY, minX, maxX);
- }
-
- // shortcut: check if either of the end points fall inside the box
- if (bboxContainsPoint(ax, ay, minX, maxX, minY, maxY)
- || bboxContainsPoint(bx, by, minX, maxX, minY, maxY)) {
- return true;
- }
-
- // shortcut: check bboxes of edges are disjoint
- if (boxesAreDisjoint(Math.min(ax, bx), Math.max(ax, bx), Math.min(ay, by), Math.max(ay, by),
- minX, maxX, minY, maxY)) {
- return false;
- }
-
- // shortcut: edge is a point
- if (ax == bx && ay == by) {
- return false;
- }
-
- // top
- if (orient(ax, ay, bx, by, minX, maxY) * orient(ax, ay, bx, by, maxX, maxY) <= 0 &&
- orient(minX, maxY, maxX, maxY, ax, ay) * orient(minX, maxY, maxX, maxY, bx, by) <= 0) {
- return true;
- }
-
- // right
- if (orient(ax, ay, bx, by, maxX, maxY) * orient(ax, ay, bx, by, maxX, minY) <= 0 &&
- orient(maxX, maxY, maxX, minY, ax, ay) * orient(maxX, maxY, maxX, minY, bx, by) <= 0) {
- return true;
- }
-
- // bottom
- if (orient(ax, ay, bx, by, maxX, minY) * orient(ax, ay, bx, by, minX, minY) <= 0 &&
- orient(maxX, minY, minX, minY, ax, ay) * orient(maxX, minY, minX, minY, bx, by) <= 0) {
- return true;
- }
-
- // left
- if (orient(ax, ay, bx, by, minX, minY) * orient(ax, ay, bx, by, minX, maxY) <= 0 &&
- orient(minX, minY, minX, maxY, ax, ay) * orient(minX, minY, minX, maxY, bx, by) <= 0) {
- return true;
- }
- return false;
- }
-
- /** returns true if the edge (defined by (ax, ay) (bx, by)) intersects the query */
- private boolean edgeIntersectsQuery(int ax, int ay, int bx, int by) {
- if (this.crossesDateline() == true) {
- return edgeIntersectsBox(ax, ay, bx, by, MIN_LON_ENCODED, this.maxX, this.minY, this.maxY)
- || edgeIntersectsBox(ax, ay, bx, by, this.minX, MAX_LON_ENCODED, this.minY, this.maxY);
- }
- return edgeIntersectsBox(ax, ay, bx, by, this.minX, this.maxX, this.minY, this.maxY);
- }
-
- /** returns true if the query intersects the provided triangle (in encoded space) */
- private boolean queryIntersects(int ax, int ay, int bx, int by, int cx, int cy) {
- // check each edge of the triangle against the query
- if (edgeIntersectsQuery(ax, ay, bx, by) ||
- edgeIntersectsQuery(bx, by, cx, cy) ||
- edgeIntersectsQuery(cx, cy, ax, ay)) {
- return true;
- }
- return false;
- }
-
- /** utility method to check if two boxes are disjoint */
- public static boolean boxesAreDisjoint(final int aMinX, final int aMaxX, final int aMinY, final int aMaxY,
- final int bMinX, final int bMaxX, final int bMinY, final int bMaxY) {
- return (aMaxX < bMinX || aMinX > bMaxX || aMaxY < bMinY || aMinY > bMaxY);
- }
-
- public boolean crossesDateline() {
- return minX > maxX;
+ return rectangle2D.intersectsTriangle(aX, aY, bX, bY, cX, cY);
}
@Override
@@ -307,16 +72,13 @@ final class LatLonShapeBoundingBoxQuery extends LatLonShapeQuery {
@Override
protected boolean equalsTo(Object o) {
- return super.equalsTo(o)
- && Arrays.equals(bbox, ((LatLonShapeBoundingBoxQuery)o).bbox)
- && Arrays.equals(west, ((LatLonShapeBoundingBoxQuery)o).west);
+ return super.equalsTo(o) && rectangle2D.equals(((LatLonShapeBoundingBoxQuery)o).rectangle2D);
}
@Override
public int hashCode() {
int hash = super.hashCode();
- hash = 31 * hash + Arrays.hashCode(bbox);
- hash = 31 * hash + Arrays.hashCode(west);
+ hash = 31 * hash + rectangle2D.hashCode();
return hash;
}
@@ -330,18 +92,7 @@ final class LatLonShapeBoundingBoxQuery extends LatLonShapeQuery {
sb.append(this.field);
sb.append(':');
}
- sb.append("Rectangle(lat=");
- sb.append(decodeLatitude(minY));
- sb.append(" TO ");
- sb.append(decodeLatitude(maxY));
- sb.append(" lon=");
- sb.append(decodeLongitude(minX));
- sb.append(" TO ");
- sb.append(decodeLongitude(maxX));
- if (maxX < minX) {
- sb.append(" [crosses dateline!]");
- }
- sb.append(")");
+ sb.append(rectangle2D.toString());
return sb.toString();
}
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/ce9a8012/lucene/sandbox/src/java/org/apache/lucene/geo/Rectangle2D.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/geo/Rectangle2D.java b/lucene/sandbox/src/java/org/apache/lucene/geo/Rectangle2D.java
new file mode 100644
index 0000000..c3acaa5
--- /dev/null
+++ b/lucene/sandbox/src/java/org/apache/lucene/geo/Rectangle2D.java
@@ -0,0 +1,315 @@
+/*
+ * 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.geo;
+
+import java.util.Arrays;
+
+import org.apache.lucene.document.LatLonShape;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.util.FutureArrays;
+
+import static org.apache.lucene.document.LatLonShape.BYTES;
+import static org.apache.lucene.geo.GeoEncodingUtils.MAX_LON_ENCODED;
+import static org.apache.lucene.geo.GeoEncodingUtils.MIN_LON_ENCODED;
+import static org.apache.lucene.geo.GeoEncodingUtils.decodeLatitude;
+import static org.apache.lucene.geo.GeoEncodingUtils.decodeLongitude;
+import static org.apache.lucene.geo.GeoEncodingUtils.encodeLatitude;
+import static org.apache.lucene.geo.GeoEncodingUtils.encodeLatitudeCeil;
+import static org.apache.lucene.geo.GeoEncodingUtils.encodeLongitude;
+import static org.apache.lucene.geo.GeoEncodingUtils.encodeLongitudeCeil;
+import static org.apache.lucene.geo.GeoUtils.orient;
+
+/**
+ * 2D rectangle implementation containing spatial logic.
+ *
+ * @lucene.internal
+ */
+public class Rectangle2D {
+ final byte[] bbox;
+ final byte[] west;
+ final int minX;
+ final int maxX;
+ final int minY;
+ final int maxY;
+
+ private Rectangle2D(double minLat, double maxLat, double minLon, double maxLon) {
+ this.bbox = new byte[4 * BYTES];
+ int minXenc = encodeLongitudeCeil(minLon);
+ int maxXenc = encodeLongitude(maxLon);
+ int minYenc = encodeLatitudeCeil(minLat);
+ int maxYenc = encodeLatitude(maxLat);
+ if (minYenc > maxYenc) {
+ minYenc = maxYenc;
+ }
+ this.minY = minYenc;
+ this.maxY = maxYenc;
+
+ if (minLon > maxLon == true) {
+ // crossing dateline is split into east/west boxes
+ this.west = new byte[4 * BYTES];
+ this.minX = minXenc;
+ this.maxX = maxXenc;
+ encode(MIN_LON_ENCODED, this.maxX, this.minY, this.maxY, this.west);
+ encode(this.minX, MAX_LON_ENCODED, this.minY, this.maxY, this.bbox);
+ } else {
+ // encodeLongitudeCeil may cause minX to be > maxX iff
+ // the delta between the longitude < the encoding resolution
+ if (minXenc > maxXenc) {
+ minXenc = maxXenc;
+ }
+ this.west = null;
+ this.minX = minXenc;
+ this.maxX = maxXenc;
+ encode(this.minX, this.maxX, this.minY, this.maxY, bbox);
+ }
+ }
+
+ /** Builds a Rectangle2D from rectangle */
+ public static Rectangle2D create(Rectangle rectangle) {
+ return new Rectangle2D(rectangle.minLat, rectangle.maxLat, rectangle.minLon, rectangle.maxLon);
+ }
+
+ public boolean crossesDateline() {
+ return minX > maxX;
+ }
+
+ /** Checks if the rectangle contains the provided point **/
+ public boolean queryContainsPoint(int x, int y) {
+ if (this.crossesDateline() == true) {
+ return bboxContainsPoint(x, y, MIN_LON_ENCODED, this.maxX, this.minY, this.maxY)
+ || bboxContainsPoint(x, y, this.minX, MAX_LON_ENCODED, this.minY, this.maxY);
+ }
+ return bboxContainsPoint(x, y, this.minX, this.maxX, this.minY, this.maxY);
+ }
+
+ /** compare this to a provided rangle bounding box **/
+ public PointValues.Relation relateRangeBBox(int minXOffset, int minYOffset, byte[] minTriangle,
+ int maxXOffset, int maxYOffset, byte[] maxTriangle) {
+ PointValues.Relation eastRelation = compareBBoxToRangeBBox(this.bbox, minXOffset, minYOffset, minTriangle, maxXOffset, maxYOffset, maxTriangle);
+ if (this.crossesDateline() && eastRelation == PointValues.Relation.CELL_OUTSIDE_QUERY) {
+ return compareBBoxToRangeBBox(this.west, minXOffset, minYOffset, minTriangle, maxXOffset, maxYOffset, maxTriangle);
+ }
+ return eastRelation;
+ }
+
+ /** Checks if the rectangle intersects the provided triangle **/
+ public boolean intersectsTriangle(int aX, int aY, int bX, int bY, int cX, int cY) {
+ // 1. query contains any triangle points
+ if (queryContainsPoint(aX, aY) || queryContainsPoint(bX, bY) || queryContainsPoint(cX, cY)) {
+ return true;
+ }
+
+ // compute bounding box of triangle
+ int tMinX = StrictMath.min(StrictMath.min(aX, bX), cX);
+ int tMaxX = StrictMath.max(StrictMath.max(aX, bX), cX);
+ int tMinY = StrictMath.min(StrictMath.min(aY, bY), cY);
+ int tMaxY = StrictMath.max(StrictMath.max(aY, bY), cY);
+
+ // 2. check bounding boxes are disjoint
+ if (this.crossesDateline() == true) {
+ if (boxesAreDisjoint(tMinX, tMaxX, tMinY, tMaxY, MIN_LON_ENCODED, this.maxX, this.minY, this.maxY)
+ && boxesAreDisjoint(tMinX, tMaxX, tMinY, tMaxY, this.minX, MAX_LON_ENCODED, this.minY, this.maxY)) {
+ return false;
+ }
+ } else if (tMaxX < minX || tMinX > maxX || tMinY > maxY || tMaxY < minY) {
+ return false;
+ }
+
+ // 3. check triangle contains any query points
+ if (Tessellator.pointInTriangle(minX, minY, aX, aY, bX, bY, cX, cY)) {
+ return true;
+ } else if (Tessellator.pointInTriangle(maxX, minY, aX, aY, bX, bY, cX, cY)) {
+ return true;
+ } else if (Tessellator.pointInTriangle(maxX, maxY, aX, aY, bX, bY, cX, cY)) {
+ return true;
+ } else if (Tessellator.pointInTriangle(minX, maxY, aX, aY, bX, bY, cX, cY)) {
+ return true;
+ }
+
+ // 4. last ditch effort: check crossings
+ if (queryIntersects(aX, aY, bX, bY, cX, cY)) {
+ return true;
+ }
+ return false;
+ }
+
+ /** Checks if the rectangle contains the provided triangle **/
+ public boolean containsTriangle(int ax, int ay, int bx, int by, int cx, int cy) {
+ if (this.crossesDateline() == true) {
+ return bboxContainsTriangle(ax, ay, bx, by, cx, cy, MIN_LON_ENCODED, this.maxX, this.minY, this.maxY)
+ || bboxContainsTriangle(ax, ay, bx, by, cx, cy, this.minX, MAX_LON_ENCODED, this.minY, this.maxY);
+ }
+ return bboxContainsTriangle(ax, ay, bx, by, cx, cy, minX, maxX, minY, maxY);
+ }
+
+ /** static utility method to compare a bbox with a range of triangles (just the bbox of the triangle collection) */
+ private static PointValues.Relation compareBBoxToRangeBBox(final byte[] bbox,
+ int minXOffset, int minYOffset, byte[] minTriangle,
+ int maxXOffset, int maxYOffset, byte[] maxTriangle) {
+ // check bounding box (DISJOINT)
+ if (FutureArrays.compareUnsigned(minTriangle, minXOffset, minXOffset + BYTES, bbox, 3 * BYTES, 4 * BYTES) > 0 ||
+ FutureArrays.compareUnsigned(maxTriangle, maxXOffset, maxXOffset + BYTES, bbox, BYTES, 2 * BYTES) < 0 ||
+ FutureArrays.compareUnsigned(minTriangle, minYOffset, minYOffset + BYTES, bbox, 2 * BYTES, 3 * BYTES) > 0 ||
+ FutureArrays.compareUnsigned(maxTriangle, maxYOffset, maxYOffset + BYTES, bbox, 0, BYTES) < 0) {
+ return PointValues.Relation.CELL_OUTSIDE_QUERY;
+ }
+
+ if (FutureArrays.compareUnsigned(minTriangle, minXOffset, minXOffset + BYTES, bbox, BYTES, 2 * BYTES) >= 0 &&
+ FutureArrays.compareUnsigned(maxTriangle, maxXOffset, maxXOffset + BYTES, bbox, 3 * BYTES, 4 * BYTES) <= 0 &&
+ FutureArrays.compareUnsigned(minTriangle, minYOffset, minYOffset + BYTES, bbox, 0, BYTES) >= 0 &&
+ FutureArrays.compareUnsigned(maxTriangle, maxYOffset, maxYOffset + BYTES, bbox, 2 * BYTES, 3 * BYTES) <= 0) {
+ return PointValues.Relation.CELL_INSIDE_QUERY;
+ }
+ return PointValues.Relation.CELL_CROSSES_QUERY;
+ }
+
+ /**
+ * encodes a bounding box into the provided byte array
+ */
+ private static void encode(final int minX, final int maxX, final int minY, final int maxY, byte[] b) {
+ if (b == null) {
+ b = new byte[4 * LatLonShape.BYTES];
+ }
+ LatLonShape.encodeTriangleBoxVal(minY, b, 0);
+ LatLonShape.encodeTriangleBoxVal(minX, b, BYTES);
+ LatLonShape.encodeTriangleBoxVal(maxY, b, 2 * BYTES);
+ LatLonShape.encodeTriangleBoxVal(maxX, b, 3 * BYTES);
+ }
+
+ /** returns true if the query intersects the provided triangle (in encoded space) */
+ private boolean queryIntersects(int ax, int ay, int bx, int by, int cx, int cy) {
+ // check each edge of the triangle against the query
+ if (edgeIntersectsQuery(ax, ay, bx, by) ||
+ edgeIntersectsQuery(bx, by, cx, cy) ||
+ edgeIntersectsQuery(cx, cy, ax, ay)) {
+ return true;
+ }
+ return false;
+ }
+
+ /** returns true if the edge (defined by (ax, ay) (bx, by)) intersects the query */
+ private boolean edgeIntersectsQuery(int ax, int ay, int bx, int by) {
+ if (this.crossesDateline() == true) {
+ return edgeIntersectsBox(ax, ay, bx, by, MIN_LON_ENCODED, this.maxX, this.minY, this.maxY)
+ || edgeIntersectsBox(ax, ay, bx, by, this.minX, MAX_LON_ENCODED, this.minY, this.maxY);
+ }
+ return edgeIntersectsBox(ax, ay, bx, by, this.minX, this.maxX, this.minY, this.maxY);
+ }
+
+ /** static utility method to check if a bounding box contains a point */
+ private static boolean bboxContainsPoint(int x, int y, int minX, int maxX, int minY, int maxY) {
+ return (x < minX || x > maxX || y < minY || y > maxY) == false;
+ }
+
+ /** static utility method to check if a bounding box contains a triangle */
+ private static boolean bboxContainsTriangle(int ax, int ay, int bx, int by, int cx, int cy,
+ int minX, int maxX, int minY, int maxY) {
+ return bboxContainsPoint(ax, ay, minX, maxX, minY, maxY)
+ && bboxContainsPoint(bx, by, minX, maxX, minY, maxY)
+ && bboxContainsPoint(cx, cy, minX, maxX, minY, maxY);
+ }
+
+ /** returns true if the edge (defined by (ax, ay) (bx, by)) intersects the query */
+ private static boolean edgeIntersectsBox(int ax, int ay, int bx, int by,
+ int minX, int maxX, int minY, int maxY) {
+ // shortcut: if edge is a point (occurs w/ Line shapes); simply check bbox w/ point
+ if (ax == bx && ay == by) {
+ return Rectangle.containsPoint(ay, ax, minY, maxY, minX, maxX);
+ }
+
+ // shortcut: check if either of the end points fall inside the box
+ if (bboxContainsPoint(ax, ay, minX, maxX, minY, maxY)
+ || bboxContainsPoint(bx, by, minX, maxX, minY, maxY)) {
+ return true;
+ }
+
+ // shortcut: check bboxes of edges are disjoint
+ if (boxesAreDisjoint(Math.min(ax, bx), Math.max(ax, bx), Math.min(ay, by), Math.max(ay, by),
+ minX, maxX, minY, maxY)) {
+ return false;
+ }
+
+ // shortcut: edge is a point
+ if (ax == bx && ay == by) {
+ return false;
+ }
+
+ // top
+ if (orient(ax, ay, bx, by, minX, maxY) * orient(ax, ay, bx, by, maxX, maxY) <= 0 &&
+ orient(minX, maxY, maxX, maxY, ax, ay) * orient(minX, maxY, maxX, maxY, bx, by) <= 0) {
+ return true;
+ }
+
+ // right
+ if (orient(ax, ay, bx, by, maxX, maxY) * orient(ax, ay, bx, by, maxX, minY) <= 0 &&
+ orient(maxX, maxY, maxX, minY, ax, ay) * orient(maxX, maxY, maxX, minY, bx, by) <= 0) {
+ return true;
+ }
+
+ // bottom
+ if (orient(ax, ay, bx, by, maxX, minY) * orient(ax, ay, bx, by, minX, minY) <= 0 &&
+ orient(maxX, minY, minX, minY, ax, ay) * orient(maxX, minY, minX, minY, bx, by) <= 0) {
+ return true;
+ }
+
+ // left
+ if (orient(ax, ay, bx, by, minX, minY) * orient(ax, ay, bx, by, minX, maxY) <= 0 &&
+ orient(minX, minY, minX, maxY, ax, ay) * orient(minX, minY, minX, maxY, bx, by) <= 0) {
+ return true;
+ }
+ return false;
+ }
+
+ /** utility method to check if two boxes are disjoint */
+ private static boolean boxesAreDisjoint(final int aMinX, final int aMaxX, final int aMinY, final int aMaxY,
+ final int bMinX, final int bMaxX, final int bMinY, final int bMaxY) {
+ return (aMaxX < bMinX || aMinX > bMaxX || aMaxY < bMinY || aMinY > bMaxY);
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ return Arrays.equals(bbox, ((Rectangle2D)o).bbox)
+ && Arrays.equals(west, ((Rectangle2D)o).west);
+ }
+
+ @Override
+ public int hashCode() {
+ int hash = super.hashCode();
+ hash = 31 * hash + Arrays.hashCode(bbox);
+ hash = 31 * hash + Arrays.hashCode(west);
+ return hash;
+ }
+
+ @Override
+ public String toString() {
+ final StringBuilder sb = new StringBuilder();
+ sb.append("Rectangle(lat=");
+ sb.append(decodeLatitude(minY));
+ sb.append(" TO ");
+ sb.append(decodeLatitude(maxY));
+ sb.append(" lon=");
+ sb.append(decodeLongitude(minX));
+ sb.append(" TO ");
+ sb.append(decodeLongitude(maxX));
+ if (maxX < minX) {
+ sb.append(" [crosses dateline!]");
+ }
+ sb.append(")");
+ return sb.toString();
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/ce9a8012/lucene/sandbox/src/test/org/apache/lucene/geo/TestRectangle2D.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/geo/TestRectangle2D.java b/lucene/sandbox/src/test/org/apache/lucene/geo/TestRectangle2D.java
new file mode 100644
index 0000000..2714936
--- /dev/null
+++ b/lucene/sandbox/src/test/org/apache/lucene/geo/TestRectangle2D.java
@@ -0,0 +1,100 @@
+/*
+ * 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.geo;
+
+import org.apache.lucene.document.LatLonShape;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.util.LuceneTestCase;
+
+import static org.apache.lucene.document.LatLonShape.BYTES;
+
+public class TestRectangle2D extends LuceneTestCase {
+
+ public void testTriangleDisjoint() {
+ Rectangle rectangle = new Rectangle(0, 1, 0, 1);
+ Rectangle2D rectangle2D = Rectangle2D.create(rectangle);
+ int ax = GeoEncodingUtils.encodeLongitude(4);
+ int ay = GeoEncodingUtils.encodeLatitude(4);
+ int bx = GeoEncodingUtils.encodeLongitude(5);
+ int by = GeoEncodingUtils.encodeLatitude(5);
+ int cx = GeoEncodingUtils.encodeLongitude(5);
+ int cy = GeoEncodingUtils.encodeLatitude(4);
+ assertFalse(rectangle2D.intersectsTriangle(ax, ay, bx, by , cx, cy));
+ assertFalse(rectangle2D.containsTriangle(ax, ay, bx, by , cx, cy));
+ }
+
+ public void testTriangleIntersects() {
+ Rectangle rectangle = new Rectangle(0, 1, 0, 1);
+ Rectangle2D rectangle2D = Rectangle2D.create(rectangle);
+ int ax = GeoEncodingUtils.encodeLongitude(0.5);
+ int ay = GeoEncodingUtils.encodeLatitude(0.5);
+ int bx = GeoEncodingUtils.encodeLongitude(2);
+ int by = GeoEncodingUtils.encodeLatitude(2);
+ int cx = GeoEncodingUtils.encodeLongitude(0.5);
+ int cy = GeoEncodingUtils.encodeLatitude(2);
+ assertTrue(rectangle2D.intersectsTriangle(ax, ay, bx, by , cx, cy));
+ assertFalse(rectangle2D.containsTriangle(ax, ay, bx, by , cx, cy));
+ }
+
+ public void testTriangleContains() {
+ Rectangle rectangle = new Rectangle(0, 1, 0, 1);
+ Rectangle2D rectangle2D = Rectangle2D.create(rectangle);
+ int ax = GeoEncodingUtils.encodeLongitude(0.25);
+ int ay = GeoEncodingUtils.encodeLatitude(0.25);
+ int bx = GeoEncodingUtils.encodeLongitude(0.5);
+ int by = GeoEncodingUtils.encodeLatitude(0.5);
+ int cx = GeoEncodingUtils.encodeLongitude(0.5);
+ int cy = GeoEncodingUtils.encodeLatitude(0.25);
+ assertTrue(rectangle2D.intersectsTriangle(ax, ay, bx, by , cx, cy));
+ assertTrue(rectangle2D.containsTriangle(ax, ay, bx, by , cx, cy));
+ }
+
+ public void testRandomTriangles() {
+ Rectangle rectangle = GeoTestUtil.nextBox();
+ Rectangle2D rectangle2D = Rectangle2D.create(rectangle);
+
+ for (int i =0; i < 100; i++) {
+ int ax = GeoEncodingUtils.encodeLongitude(GeoTestUtil.nextLongitude());
+ int ay = GeoEncodingUtils.encodeLatitude(GeoTestUtil.nextLatitude());
+ int bx = GeoEncodingUtils.encodeLongitude(GeoTestUtil.nextLongitude());
+ int by = GeoEncodingUtils.encodeLatitude(GeoTestUtil.nextLatitude());
+ int cx = GeoEncodingUtils.encodeLongitude(GeoTestUtil.nextLongitude());
+ int cy = GeoEncodingUtils.encodeLatitude(GeoTestUtil.nextLatitude());
+
+ int tMinX = StrictMath.min(StrictMath.min(ax, bx), cx);
+ int tMaxX = StrictMath.max(StrictMath.max(ax, bx), cx);
+ int tMinY = StrictMath.min(StrictMath.min(ay, by), cy);
+ int tMaxY = StrictMath.max(StrictMath.max(ay, by), cy);
+
+ byte[] triangle = new byte[4 * LatLonShape.BYTES];
+ LatLonShape.encodeTriangleBoxVal(tMinY, triangle, 0);
+ LatLonShape.encodeTriangleBoxVal(tMinX, triangle, BYTES);
+ LatLonShape.encodeTriangleBoxVal(tMaxY, triangle, 2 * BYTES);
+ LatLonShape.encodeTriangleBoxVal(tMaxX, triangle, 3 * BYTES);
+
+ PointValues.Relation r = rectangle2D.relateRangeBBox(LatLonShape.BYTES, 0, triangle, 3 * LatLonShape.BYTES, 2 * LatLonShape.BYTES, triangle);
+ if (r == PointValues.Relation.CELL_OUTSIDE_QUERY) {
+ assertFalse(rectangle2D.intersectsTriangle(ax, ay, bx, by , cx, cy));
+ assertFalse(rectangle2D.containsTriangle(ax, ay, bx, by , cx, cy));
+ }
+ else if (rectangle2D.containsTriangle(ax, ay, bx, by , cx, cy)) {
+ assertTrue(rectangle2D.intersectsTriangle(ax, ay, bx, by , cx, cy));
+ }
+ }
+ }
+}