You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by iv...@apache.org on 2018/12/18 15:53:34 UTC
lucene-solr:master: LUCENE-8581: Change LatLonShape encoding to use 4
bytes Per Dimension
Repository: lucene-solr
Updated Branches:
refs/heads/master 3be5b5990 -> d185ba99d
LUCENE-8581: Change LatLonShape encoding to use 4 bytes Per Dimension
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/d185ba99
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/d185ba99
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/d185ba99
Branch: refs/heads/master
Commit: d185ba99de0828bd31c2f6bcd74dc96fe8c6a452
Parents: 3be5b59
Author: iverase <iv...@apache.org>
Authored: Tue Dec 18 16:50:24 2018 +0100
Committer: iverase <iv...@apache.org>
Committed: Tue Dec 18 16:50:24 2018 +0100
----------------------------------------------------------------------
lucene/CHANGES.txt | 3 +
.../org/apache/lucene/document/LatLonShape.java | 287 +++++++---
.../document/LatLonShapeBoundingBoxQuery.java | 19 +-
.../lucene/document/LatLonShapeLineQuery.java | 33 +-
.../document/LatLonShapePolygonQuery.java | 34 +-
.../lucene/document/LatLonShapeQuery.java | 13 +-
.../java/org/apache/lucene/geo/Rectangle2D.java | 9 +-
.../java/org/apache/lucene/geo/Tessellator.java | 21 -
.../document/BaseLatLonShapeTestCase.java | 29 +-
.../document/TestLatLonLineShapeQueries.java | 79 +--
.../document/TestLatLonPolygonShapeQueries.java | 54 +-
.../apache/lucene/document/TestLatLonShape.java | 557 ++++++++++++++++++-
.../org/apache/lucene/geo/TestRectangle2D.java | 9 +-
13 files changed, 880 insertions(+), 267 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/d185ba99/lucene/CHANGES.txt
----------------------------------------------------------------------
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 10e1536..09f9011 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -268,6 +268,9 @@ Improvements
detects script boundaries more accurately with Character#UnicodeScript#of.
(Christophe Bismuth, Jim Ferenczi)
+* LUCENE-8581: Change LatLonShape encoding to use 4 bytes Per Dimension.
+ (Ignacio Vera, Nick Knize, Adrien Grand)
+
Optimizations
* LUCENE-8552: FieldInfos.getMergedFieldInfos no longer does any merging if there is <= 1 segment.
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/d185ba99/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShape.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShape.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShape.java
index 7c074cf..30b4819 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShape.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShape.java
@@ -19,6 +19,7 @@ package org.apache.lucene.document;
import java.util.ArrayList;
import java.util.List;
+import org.apache.lucene.geo.GeoUtils;
import org.apache.lucene.geo.Line;
import org.apache.lucene.geo.Polygon;
import org.apache.lucene.geo.Tessellator;
@@ -54,7 +55,7 @@ import static org.apache.lucene.geo.GeoEncodingUtils.encodeLongitude;
* @lucene.experimental
*/
public class LatLonShape {
- public static final int BYTES = 2 * LatLonPoint.BYTES;
+ public static final int BYTES = LatLonPoint.BYTES;
protected static final FieldType TYPE = new FieldType();
static {
@@ -80,35 +81,12 @@ public class LatLonShape {
/** create indexable fields for line geometry */
public static Field[] createIndexableFields(String fieldName, Line line) {
int numPoints = line.numPoints();
- List<LatLonTriangle> fields = new ArrayList<>(numPoints - 1);
-
+ Field[] fields = new Field[numPoints - 1];
// create "flat" triangles
- double aLat, bLat, aLon, bLon, temp;
for (int i = 0, j = 1; j < numPoints; ++i, ++j) {
- aLat = line.getLat(i);
- aLon = line.getLon(i);
- bLat = line.getLat(j);
- bLon = line.getLon(j);
- if (aLat > bLat) {
- temp = aLat;
- aLat = bLat;
- bLat = temp;
- temp = aLon;
- aLon = bLon;
- bLon = temp;
- } else if (aLat == bLat) {
- if (aLon > bLon) {
- temp = aLat;
- aLat = bLat;
- bLat = temp;
- temp = aLon;
- aLon = bLon;
- bLon = temp;
- }
- }
- fields.add(new LatLonTriangle(fieldName, aLat, aLon, bLat, bLon, aLat, aLon));
+ fields[i] = new LatLonTriangle(fieldName, line.getLat(i), line.getLon(i), line.getLat(j), line.getLon(j), line.getLat(i), line.getLon(i));
}
- return fields.toArray(new Field[fields.size()]);
+ return fields;
}
/** create indexable fields for point geometry */
@@ -151,6 +129,7 @@ public class LatLonShape {
setTriangleValue(t.getEncodedX(0), t.getEncodedY(0), t.getEncodedX(1), t.getEncodedY(1), t.getEncodedX(2), t.getEncodedY(2));
}
+
public void setTriangleValue(int aX, int aY, int bX, int bY, int cX, int cY) {
final byte[] bytes;
@@ -160,49 +139,231 @@ public class LatLonShape {
} else {
bytes = ((BytesRef) fieldsData).bytes;
}
-
- int minX = StrictMath.min(aX, StrictMath.min(bX, cX));
- int minY = StrictMath.min(aY, StrictMath.min(bY, cY));
- int maxX = StrictMath.max(aX, StrictMath.max(bX, cX));
- int maxY = StrictMath.max(aY, StrictMath.max(bY, cY));
-
- encodeTriangle(bytes, minY, minX, maxY, maxX, aX, aY, bX, bY, cX, cY);
+ encodeTriangle(bytes, aY, aX, bY, bX, cY, cX);
}
+ }
- private void encodeTriangle(byte[] bytes, int minY, int minX, int maxY, int maxX, int aX, int aY, int bX, int bY, int cX, int cY) {
- encodeTriangleBoxVal(minY, bytes, 0);
- encodeTriangleBoxVal(minX, bytes, BYTES);
- encodeTriangleBoxVal(maxY, bytes, 2 * BYTES);
- encodeTriangleBoxVal(maxX, bytes, 3 * BYTES);
-
- long a = (((long)aX) << 32) | (((long)aY) & 0x00000000FFFFFFFFL);
- long b = (((long)bX) << 32) | (((long)bY) & 0x00000000FFFFFFFFL);
- long c = (((long)cX) << 32) | (((long)cY) & 0x00000000FFFFFFFFL);
- NumericUtils.longToSortableBytes(a, bytes, 4 * BYTES);
- NumericUtils.longToSortableBytes(b, bytes, 5 * BYTES);
- NumericUtils.longToSortableBytes(c, bytes, 6 * BYTES);
- }
+ /** Query Relation Types **/
+ public enum QueryRelation {
+ INTERSECTS, WITHIN, DISJOINT
}
- /** encodes bounding box value of triangle. Note the encoding uses 64bit encoding, but the bounding box only needs
- * 32bits, so we pad w/ zeros to take advantage of prefix compression.
+ private static final int MINY_MINX_MAXY_MAXX_Y_X = 0;
+ private static final int MINY_MINX_Y_X_MAXY_MAXX = 1;
+ private static final int MAXY_MINX_Y_X_MINY_MAXX = 2;
+ private static final int MAXY_MINX_MINY_MAXX_Y_X = 3;
+ private static final int Y_MINX_MINY_X_MAXY_MAXX = 4;
+ private static final int Y_MINX_MINY_MAXX_MAXY_X = 5;
+ private static final int MAXY_MINX_MINY_X_Y_MAXX = 6;
+ private static final int MINY_MINX_Y_MAXX_MAXY_X = 7;
+
+ /**
+ * A triangle is encoded using 6 points and an extra point with encoded information in three bits of how to reconstruct it.
+ * Triangles are encoded with CCW orientation and might be rotated to limit the number of possible reconstructions to 2^3.
+ * Reconstruction always happens from west to east.
*/
- public static void encodeTriangleBoxVal(int encodedVal, byte[] bytes, int offset) {
- long val = (long)(encodedVal ^ 0x80000000);
- val &= 0x00000000FFFFFFFFL;
- val ^= 0x8000000000000000L;
- NumericUtils.longToSortableBytes(val, bytes, offset);
- }
+ public static void encodeTriangle(byte[] bytes, int aLat, int aLon, int bLat, int bLon, int cLat, int cLon) {
+ assert bytes.length == 7 * BYTES;
+ int aX;
+ int bX;
+ int cX;
+ int aY;
+ int bY;
+ int cY;
+ //change orientation if CW
+ if (GeoUtils.orient(aLon, aLat, bLon, bLat, cLon, cLat) == -1) {
+ aX = cLon;
+ bX = bLon;
+ cX = aLon;
+ aY = cLat;
+ bY = bLat;
+ cY = aLat;
+ } else {
+ aX = aLon;
+ bX = bLon;
+ cX = cLon;
+ aY = aLat;
+ bY = bLat;
+ cY = cLat;
+ }
+ //rotate edges and place minX at the beginning
+ if (bX < aX || cX < aX) {
+ if (bX < cX) {
+ int tempX = aX;
+ int tempY = aY;
+ aX = bX;
+ aY = bY;
+ bX = cX;
+ bY = cY;
+ cX = tempX;
+ cY = tempY;
+ } else if (cX < aX) {
+ int tempX = aX;
+ int tempY = aY;
+ aX = cX;
+ aY = cY;
+ cX = bX;
+ cY = bY;
+ bX = tempX;
+ bY = tempY;
+ }
+ } else if (aX == bX && aX == cX) {
+ //degenerated case, all points with same longitude
+ //we need to prevent that aX is in the middle (not part of the MBS)
+ if (bY < aY || cY < aY) {
+ if (bY < cY) {
+ int tempX = aX;
+ int tempY = aY;
+ aX = bX;
+ aY = bY;
+ bX = cX;
+ bY = cY;
+ cX = tempX;
+ cY = tempY;
+ } else if (cY < aY) {
+ int tempX = aX;
+ int tempY = aY;
+ aX = cX;
+ aY = cY;
+ cX = bX;
+ cY = bY;
+ bX = tempX;
+ bY = tempY;
+ }
+ }
+ }
- /** counterpart to {@link #encodeTriangleBoxVal}; decodes encoded triangle bounding box values */
- public static int decodeTriangleBoxVal(byte[] encoded, int offset) {
- long val = NumericUtils.sortableBytesToLong(encoded, offset);
- int result = (int)(val & 0x00000000FFFFFFFF);
- return result ^ 0x80000000;
+ int minX = aX;
+ int minY = StrictMath.min(aY, StrictMath.min(bY, cY));
+ int maxX = StrictMath.max(aX, StrictMath.max(bX, cX));
+ int maxY = StrictMath.max(aY, StrictMath.max(bY, cY));
+
+ int bits, x, y;
+ if (minY == aY) {
+ if (maxY == bY && maxX == bX) {
+ y = cY;
+ x = cX;
+ bits = MINY_MINX_MAXY_MAXX_Y_X;
+ } else if (maxY == cY && maxX == cX) {
+ y = bY;
+ x = bX;
+ bits = MINY_MINX_Y_X_MAXY_MAXX;
+ } else {
+ y = bY;
+ x = cX;
+ bits = MINY_MINX_Y_MAXX_MAXY_X;
+ }
+ } else if (maxY == aY) {
+ if (minY == bY && maxX == bX) {
+ y = cY;
+ x = cX;
+ bits = MAXY_MINX_MINY_MAXX_Y_X;
+ } else if (minY == cY && maxX == cX) {
+ y = bY;
+ x = bX;
+ bits = MAXY_MINX_Y_X_MINY_MAXX;
+ } else {
+ y = cY;
+ x = bX;
+ bits = MAXY_MINX_MINY_X_Y_MAXX;
+ }
+ } else if (maxX == bX && minY == bY) {
+ y = aY;
+ x = cX;
+ bits = Y_MINX_MINY_MAXX_MAXY_X;
+ } else if (maxX == cX && maxY == cY) {
+ y = aY;
+ x = bX;
+ bits = Y_MINX_MINY_X_MAXY_MAXX;
+ } else {
+ throw new IllegalArgumentException("Could not encode the provided triangle");
+ }
+ NumericUtils.intToSortableBytes(minY, bytes, 0);
+ NumericUtils.intToSortableBytes(minX, bytes, BYTES);
+ NumericUtils.intToSortableBytes(maxY, bytes, 2 * BYTES);
+ NumericUtils.intToSortableBytes(maxX, bytes, 3 * BYTES);
+ NumericUtils.intToSortableBytes(y, bytes, 4 * BYTES);
+ NumericUtils.intToSortableBytes(x, bytes, 5 * BYTES);
+ NumericUtils.intToSortableBytes(bits, bytes, 6 * BYTES);
}
- /** Query Relation Types **/
- public enum QueryRelation {
- INTERSECTS, WITHIN, DISJOINT
+ /**
+ * Decode a triangle encoded by {@link LatLonShape#encodeTriangle(byte[], int, int, int, int, int, int)}.
+ */
+ public static void decodeTriangle(byte[] t, int[] triangle) {
+ assert triangle.length == 6;
+ int bits = NumericUtils.sortableBytesToInt(t, 6 * LatLonShape.BYTES);
+ //extract the first three bits
+ int tCode = (((1 << 3) - 1) & (bits >> 0));
+ switch (tCode) {
+ case MINY_MINX_MAXY_MAXX_Y_X:
+ triangle[0] = NumericUtils.sortableBytesToInt(t, 0 * LatLonShape.BYTES);
+ triangle[1] = NumericUtils.sortableBytesToInt(t, 1 * LatLonShape.BYTES);
+ triangle[2] = NumericUtils.sortableBytesToInt(t, 2 * LatLonShape.BYTES);
+ triangle[3] = NumericUtils.sortableBytesToInt(t, 3 * LatLonShape.BYTES);
+ triangle[4] = NumericUtils.sortableBytesToInt(t, 4 * LatLonShape.BYTES);
+ triangle[5] = NumericUtils.sortableBytesToInt(t, 5 * LatLonShape.BYTES);
+ break;
+ case MINY_MINX_Y_X_MAXY_MAXX:
+ triangle[0] = NumericUtils.sortableBytesToInt(t, 0 * LatLonShape.BYTES);
+ triangle[1] = NumericUtils.sortableBytesToInt(t, 1 * LatLonShape.BYTES);
+ triangle[2] = NumericUtils.sortableBytesToInt(t, 4 * LatLonShape.BYTES);
+ triangle[3] = NumericUtils.sortableBytesToInt(t, 5 * LatLonShape.BYTES);
+ triangle[4] = NumericUtils.sortableBytesToInt(t, 2 * LatLonShape.BYTES);
+ triangle[5] = NumericUtils.sortableBytesToInt(t, 3 * LatLonShape.BYTES);
+ break;
+ case MAXY_MINX_Y_X_MINY_MAXX:
+ triangle[0] = NumericUtils.sortableBytesToInt(t, 2 * LatLonShape.BYTES);
+ triangle[1] = NumericUtils.sortableBytesToInt(t, 1 * LatLonShape.BYTES);
+ triangle[2] = NumericUtils.sortableBytesToInt(t, 4 * LatLonShape.BYTES);
+ triangle[3] = NumericUtils.sortableBytesToInt(t, 5 * LatLonShape.BYTES);
+ triangle[4] = NumericUtils.sortableBytesToInt(t, 0 * LatLonShape.BYTES);
+ triangle[5] = NumericUtils.sortableBytesToInt(t, 3 * LatLonShape.BYTES);
+ break;
+ case MAXY_MINX_MINY_MAXX_Y_X:
+ triangle[0] = NumericUtils.sortableBytesToInt(t, 2 * LatLonShape.BYTES);
+ triangle[1] = NumericUtils.sortableBytesToInt(t, 1 * LatLonShape.BYTES);
+ triangle[2] = NumericUtils.sortableBytesToInt(t, 0 * LatLonShape.BYTES);
+ triangle[3] = NumericUtils.sortableBytesToInt(t, 3 * LatLonShape.BYTES);
+ triangle[4] = NumericUtils.sortableBytesToInt(t, 4 * LatLonShape.BYTES);
+ triangle[5] = NumericUtils.sortableBytesToInt(t, 5 * LatLonShape.BYTES);
+ break;
+ case Y_MINX_MINY_X_MAXY_MAXX:
+ triangle[0] = NumericUtils.sortableBytesToInt(t, 4 * LatLonShape.BYTES);
+ triangle[1] = NumericUtils.sortableBytesToInt(t, 1 * LatLonShape.BYTES);
+ triangle[2] = NumericUtils.sortableBytesToInt(t, 0 * LatLonShape.BYTES);
+ triangle[3] = NumericUtils.sortableBytesToInt(t, 5 * LatLonShape.BYTES);
+ triangle[4] = NumericUtils.sortableBytesToInt(t, 2 * LatLonShape.BYTES);
+ triangle[5] = NumericUtils.sortableBytesToInt(t, 3 * LatLonShape.BYTES);
+ break;
+ case Y_MINX_MINY_MAXX_MAXY_X:
+ triangle[0] = NumericUtils.sortableBytesToInt(t, 4 * LatLonShape.BYTES);
+ triangle[1] = NumericUtils.sortableBytesToInt(t, 1 * LatLonShape.BYTES);
+ triangle[2] = NumericUtils.sortableBytesToInt(t, 0 * LatLonShape.BYTES);
+ triangle[3] = NumericUtils.sortableBytesToInt(t, 3 * LatLonShape.BYTES);
+ triangle[4] = NumericUtils.sortableBytesToInt(t, 2 * LatLonShape.BYTES);
+ triangle[5] = NumericUtils.sortableBytesToInt(t, 5 * LatLonShape.BYTES);
+ break;
+ case MAXY_MINX_MINY_X_Y_MAXX:
+ triangle[0] = NumericUtils.sortableBytesToInt(t, 2 * LatLonShape.BYTES);
+ triangle[1] = NumericUtils.sortableBytesToInt(t, 1 * LatLonShape.BYTES);
+ triangle[2] = NumericUtils.sortableBytesToInt(t, 0 * LatLonShape.BYTES);
+ triangle[3] = NumericUtils.sortableBytesToInt(t, 5 * LatLonShape.BYTES);
+ triangle[4] = NumericUtils.sortableBytesToInt(t, 4 * LatLonShape.BYTES);
+ triangle[5] = NumericUtils.sortableBytesToInt(t, 3 * LatLonShape.BYTES);
+ break;
+ case MINY_MINX_Y_MAXX_MAXY_X:
+ triangle[0] = NumericUtils.sortableBytesToInt(t, 0 * LatLonShape.BYTES);
+ triangle[1] = NumericUtils.sortableBytesToInt(t, 1 * LatLonShape.BYTES);
+ triangle[2] = NumericUtils.sortableBytesToInt(t, 4 * LatLonShape.BYTES);
+ triangle[3] = NumericUtils.sortableBytesToInt(t, 3 * LatLonShape.BYTES);
+ triangle[4] = NumericUtils.sortableBytesToInt(t, 2 * LatLonShape.BYTES);
+ triangle[5] = NumericUtils.sortableBytesToInt(t, 5 * LatLonShape.BYTES);
+ break;
+ default:
+ throw new IllegalArgumentException("Could not decode the provided triangle");
+ }
+ //Points of the decoded triangle must be co-planar or CCW oriented
+ assert GeoUtils.orient(triangle[1], triangle[0], triangle[3], triangle[2], triangle[5], triangle[4]) >= 0;
}
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/d185ba99/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 43fe28e..79d4d07 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java
@@ -19,7 +19,6 @@ package org.apache.lucene.document;
import org.apache.lucene.geo.Rectangle;
import org.apache.lucene.geo.Rectangle2D;
import org.apache.lucene.index.PointValues.Relation;
-import org.apache.lucene.util.NumericUtils;
/**
* Finds all previously indexed shapes that intersect the specified bounding box.
@@ -46,18 +45,16 @@ final class LatLonShapeBoundingBoxQuery extends LatLonShapeQuery {
/** returns true if the query matches the encoded triangle */
@Override
- protected boolean queryMatches(byte[] t) {
+ protected boolean queryMatches(byte[] t, int[] scratchTriangle) {
// decode indexed triangle
- long a = NumericUtils.sortableBytesToLong(t, 4 * LatLonShape.BYTES);
- long b = NumericUtils.sortableBytesToLong(t, 5 * LatLonShape.BYTES);
- long c = NumericUtils.sortableBytesToLong(t, 6 * LatLonShape.BYTES);
+ LatLonShape.decodeTriangle(t, scratchTriangle);
- int aX = (int)((a >>> 32) & 0x00000000FFFFFFFFL);
- int bX = (int)((b >>> 32) & 0x00000000FFFFFFFFL);
- int cX = (int)((c >>> 32) & 0x00000000FFFFFFFFL);
- int aY = (int)(a & 0x00000000FFFFFFFFL);
- int bY = (int)(b & 0x00000000FFFFFFFFL);
- int cY = (int)(c & 0x00000000FFFFFFFFL);
+ int aY = scratchTriangle[0];
+ int aX = scratchTriangle[1];
+ int bY = scratchTriangle[2];
+ int bX = scratchTriangle[3];
+ int cY = scratchTriangle[4];
+ int cX = scratchTriangle[5];
if (queryRelation == LatLonShape.QueryRelation.WITHIN) {
return rectangle2D.containsTriangle(aX, aY, bX, bY, cX, cY);
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/d185ba99/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeLineQuery.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeLineQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeLineQuery.java
index e49b4ec..fc6836e 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeLineQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeLineQuery.java
@@ -74,34 +74,25 @@ final class LatLonShapeLineQuery extends LatLonShapeQuery {
@Override
protected Relation relateRangeBBoxToQuery(int minXOffset, int minYOffset, byte[] minTriangle,
int maxXOffset, int maxYOffset, byte[] maxTriangle) {
- double minLat = GeoEncodingUtils.decodeLatitude(LatLonShape.decodeTriangleBoxVal(minTriangle, minYOffset));
- double minLon = GeoEncodingUtils.decodeLongitude(LatLonShape.decodeTriangleBoxVal(minTriangle, minXOffset));
- double maxLat = GeoEncodingUtils.decodeLatitude(LatLonShape.decodeTriangleBoxVal(maxTriangle, maxYOffset));
- double maxLon = GeoEncodingUtils.decodeLongitude(LatLonShape.decodeTriangleBoxVal(maxTriangle, maxXOffset));
+ double minLat = GeoEncodingUtils.decodeLatitude(NumericUtils.sortableBytesToInt(minTriangle, minYOffset));
+ double minLon = GeoEncodingUtils.decodeLongitude(NumericUtils.sortableBytesToInt(minTriangle, minXOffset));
+ double maxLat = GeoEncodingUtils.decodeLatitude(NumericUtils.sortableBytesToInt(maxTriangle, maxYOffset));
+ double maxLon = GeoEncodingUtils.decodeLongitude(NumericUtils.sortableBytesToInt(maxTriangle, maxXOffset));
// check internal node against query
return line2D.relate(minLat, maxLat, minLon, maxLon);
}
@Override
- protected boolean queryMatches(byte[] t) {
- long a = NumericUtils.sortableBytesToLong(t, 4 * LatLonShape.BYTES);
- long b = NumericUtils.sortableBytesToLong(t, 5 * LatLonShape.BYTES);
- long c = NumericUtils.sortableBytesToLong(t, 6 * LatLonShape.BYTES);
+ protected boolean queryMatches(byte[] t, int[] scratchTriangle) {
+ LatLonShape.decodeTriangle(t, scratchTriangle);
- int aX = (int)((a >>> 32) & 0x00000000FFFFFFFFL);
- int bX = (int)((b >>> 32) & 0x00000000FFFFFFFFL);
- int cX = (int)((c >>> 32) & 0x00000000FFFFFFFFL);
- int aY = (int)(a & 0x00000000FFFFFFFFL);
- int bY = (int)(b & 0x00000000FFFFFFFFL);
- int cY = (int)(c & 0x00000000FFFFFFFFL);
-
- double alat = GeoEncodingUtils.decodeLatitude(aY);
- double alon = GeoEncodingUtils.decodeLongitude(aX);
- double blat = GeoEncodingUtils.decodeLatitude(bY);
- double blon = GeoEncodingUtils.decodeLongitude(bX);
- double clat = GeoEncodingUtils.decodeLatitude(cY);
- double clon = GeoEncodingUtils.decodeLongitude(cX);
+ double alat = GeoEncodingUtils.decodeLatitude(scratchTriangle[0]);
+ double alon = GeoEncodingUtils.decodeLongitude(scratchTriangle[1]);
+ double blat = GeoEncodingUtils.decodeLatitude(scratchTriangle[2]);
+ double blon = GeoEncodingUtils.decodeLongitude(scratchTriangle[3]);
+ double clat = GeoEncodingUtils.decodeLatitude(scratchTriangle[4]);
+ double clon = GeoEncodingUtils.decodeLongitude(scratchTriangle[5]);
if (queryRelation == LatLonShape.QueryRelation.WITHIN) {
return line2D.relateTriangle(alon, alat, blon, blat, clon, clat) == Relation.CELL_INSIDE_QUERY;
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/d185ba99/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapePolygonQuery.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapePolygonQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapePolygonQuery.java
index 2b342a8..f1ac299 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapePolygonQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapePolygonQuery.java
@@ -62,34 +62,26 @@ final class LatLonShapePolygonQuery extends LatLonShapeQuery {
@Override
protected Relation relateRangeBBoxToQuery(int minXOffset, int minYOffset, byte[] minTriangle,
int maxXOffset, int maxYOffset, byte[] maxTriangle) {
- double minLat = GeoEncodingUtils.decodeLatitude(LatLonShape.decodeTriangleBoxVal(minTriangle, minYOffset));
- double minLon = GeoEncodingUtils.decodeLongitude(LatLonShape.decodeTriangleBoxVal(minTriangle, minXOffset));
- double maxLat = GeoEncodingUtils.decodeLatitude(LatLonShape.decodeTriangleBoxVal(maxTriangle, maxYOffset));
- double maxLon = GeoEncodingUtils.decodeLongitude(LatLonShape.decodeTriangleBoxVal(maxTriangle, maxXOffset));
+
+ double minLat = GeoEncodingUtils.decodeLatitude(NumericUtils.sortableBytesToInt(minTriangle, minYOffset));
+ double minLon = GeoEncodingUtils.decodeLongitude(NumericUtils.sortableBytesToInt(minTriangle, minXOffset));
+ double maxLat = GeoEncodingUtils.decodeLatitude(NumericUtils.sortableBytesToInt(maxTriangle, maxYOffset));
+ double maxLon = GeoEncodingUtils.decodeLongitude(NumericUtils.sortableBytesToInt(maxTriangle, maxXOffset));
// check internal node against query
return poly2D.relate(minLat, maxLat, minLon, maxLon);
}
@Override
- protected boolean queryMatches(byte[] t) {
- long a = NumericUtils.sortableBytesToLong(t, 4 * LatLonShape.BYTES);
- long b = NumericUtils.sortableBytesToLong(t, 5 * LatLonShape.BYTES);
- long c = NumericUtils.sortableBytesToLong(t, 6 * LatLonShape.BYTES);
-
- int aX = (int)((a >>> 32) & 0x00000000FFFFFFFFL);
- int bX = (int)((b >>> 32) & 0x00000000FFFFFFFFL);
- int cX = (int)((c >>> 32) & 0x00000000FFFFFFFFL);
- int aY = (int)(a & 0x00000000FFFFFFFFL);
- int bY = (int)(b & 0x00000000FFFFFFFFL);
- int cY = (int)(c & 0x00000000FFFFFFFFL);
+ protected boolean queryMatches(byte[] t, int[] scratchTriangle) {
+ LatLonShape.decodeTriangle(t, scratchTriangle);
- double alat = GeoEncodingUtils.decodeLatitude(aY);
- double alon = GeoEncodingUtils.decodeLongitude(aX);
- double blat = GeoEncodingUtils.decodeLatitude(bY);
- double blon = GeoEncodingUtils.decodeLongitude(bX);
- double clat = GeoEncodingUtils.decodeLatitude(cY);
- double clon = GeoEncodingUtils.decodeLongitude(cX);
+ double alat = GeoEncodingUtils.decodeLatitude(scratchTriangle[0]);
+ double alon = GeoEncodingUtils.decodeLongitude(scratchTriangle[1]);
+ double blat = GeoEncodingUtils.decodeLatitude(scratchTriangle[2]);
+ double blon = GeoEncodingUtils.decodeLongitude(scratchTriangle[3]);
+ double clat = GeoEncodingUtils.decodeLatitude(scratchTriangle[4]);
+ double clon = GeoEncodingUtils.decodeLongitude(scratchTriangle[5]);
if (queryRelation == QueryRelation.WITHIN) {
return poly2D.relateTriangle(alon, alat, blon, blat, clon, clat) == Relation.CELL_INSIDE_QUERY;
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/d185ba99/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeQuery.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeQuery.java
index 8aa932f..847043a 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeQuery.java
@@ -73,7 +73,7 @@ abstract class LatLonShapeQuery extends Query {
int maxXOffset, int maxYOffset, byte[] maxTriangle);
/** returns true if the provided triangle matches the query */
- protected abstract boolean queryMatches(byte[] triangle);
+ protected abstract boolean queryMatches(byte[] triangle, int[] scratchTriangle);
/** relates a range of triangles (internal node) to the query */
protected Relation relateRangeToQuery(byte[] minTriangle, byte[] maxTriangle) {
@@ -93,6 +93,7 @@ abstract class LatLonShapeQuery extends Query {
/** create a visitor that adds documents that match the query using a sparse bitset. (Used by INTERSECT) */
protected IntersectVisitor getSparseIntersectVisitor(DocIdSetBuilder result) {
return new IntersectVisitor() {
+ final int[] scratchTriangle = new int[6];
DocIdSetBuilder.BulkAdder adder;
@Override
@@ -107,7 +108,7 @@ abstract class LatLonShapeQuery extends Query {
@Override
public void visit(int docID, byte[] t) throws IOException {
- if (queryMatches(t)) {
+ if (queryMatches(t, scratchTriangle)) {
adder.add(docID);
}
}
@@ -122,7 +123,7 @@ abstract class LatLonShapeQuery extends Query {
/** create a visitor that adds documents that match the query using a dense bitset. (Used by WITHIN, DISJOINT) */
protected IntersectVisitor getDenseIntersectVisitor(FixedBitSet intersect, FixedBitSet disjoint) {
return new IntersectVisitor() {
-
+ final int[] scratchTriangle = new int[6];
@Override
public void visit(int docID) throws IOException {
if (queryRelation == QueryRelation.DISJOINT) {
@@ -136,7 +137,7 @@ abstract class LatLonShapeQuery extends Query {
@Override
public void visit(int docID, byte[] t) throws IOException {
- if (queryMatches(t)) {
+ if (queryMatches(t, scratchTriangle)) {
intersect.set(docID);
} else {
disjoint.set(docID);
@@ -284,7 +285,7 @@ abstract class LatLonShapeQuery extends Query {
/** create a visitor that clears documents that do NOT match the polygon query; used with INTERSECTS */
private IntersectVisitor getInverseIntersectVisitor(LatLonShapeQuery query, FixedBitSet result, int[] cost) {
return new IntersectVisitor() {
-
+ int[] scratchTriangle = new int[6];
@Override
public void visit(int docID) {
result.clear(docID);
@@ -293,7 +294,7 @@ abstract class LatLonShapeQuery extends Query {
@Override
public void visit(int docID, byte[] packedTriangle) {
- if (query.queryMatches(packedTriangle) == false) {
+ if (query.queryMatches(packedTriangle, scratchTriangle) == false) {
result.clear(docID);
cost[0]--;
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/d185ba99/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
index c3acaa5..7f7def5 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/geo/Rectangle2D.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/geo/Rectangle2D.java
@@ -22,6 +22,7 @@ import java.util.Arrays;
import org.apache.lucene.document.LatLonShape;
import org.apache.lucene.index.PointValues;
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;
@@ -185,10 +186,10 @@ public class Rectangle2D {
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);
+ NumericUtils.intToSortableBytes(minY, b, 0);
+ NumericUtils.intToSortableBytes(minX, b, BYTES);
+ NumericUtils.intToSortableBytes(maxY, b, 2 * BYTES);
+ NumericUtils.intToSortableBytes(maxX, b, 3 * BYTES);
}
/** returns true if the query intersects the provided triangle (in encoded space) */
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/d185ba99/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java b/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
index 1fa0443..6159a0a 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
@@ -17,7 +17,6 @@
package org.apache.lucene.geo;
import java.util.ArrayList;
-import java.util.Arrays;
import java.util.List;
import org.apache.lucene.geo.GeoUtils.WindingOrder;
@@ -820,24 +819,6 @@ final public class Tessellator {
return polygon.getPolyLat(vrtxIdx);
}
- /** compare nodes by y then x */
- public int compareLat(Node other) {
- return compare(this.getLat(), this.getLon(), other.getLat(), other.getLon());
- }
-
- public int compare(double aX, double aY, double bX, double bY) {
- if (aX > bX) {
- return 1;
- } else if (aX == bX) {
- if (aY > bY) {
- return 1;
- } else if (aY == bY) {
- return 0;
- }
- }
- return -1;
- }
-
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
@@ -860,8 +841,6 @@ final public class Tessellator {
protected Triangle(Node a, Node b, Node c) {
this.vertex = new Node[] {a, b, c};
- // sort nodes by morton value
- Arrays.sort(this.vertex, (x, y) -> x.compareLat(y));
}
/** get quantized x value for the given vertex */
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/d185ba99/lucene/sandbox/src/test/org/apache/lucene/document/BaseLatLonShapeTestCase.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/BaseLatLonShapeTestCase.java b/lucene/sandbox/src/test/org/apache/lucene/document/BaseLatLonShapeTestCase.java
index e8ea640..da8d567 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/BaseLatLonShapeTestCase.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/BaseLatLonShapeTestCase.java
@@ -94,26 +94,19 @@ public abstract class BaseLatLonShapeTestCase extends LuceneTestCase {
return decodeLongitude(encodeLongitudeCeil(rawLon));
}
- /** quantizes a provided polygon to be consistent with the index encoding */
- protected Polygon quantizePolygon(Polygon polygon) {
- double[] lats = new double[polygon.numPoints()];
- double[] lons = new double[polygon.numPoints()];
- for (int i = 0; i < lats.length; ++i) {
- lats[i] = quantizeLat(polygon.getPolyLat(i));
- lons[i] = quantizeLon(polygon.getPolyLon(i));
- }
- return new Polygon(lats, lons);
+ /** quantizes a triangle to be consistent with index encoding */
+ protected double[] quantizeTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
+ int[] decoded = encodeDecodeTriangle(ax, ay, bx, by, cx, cy);
+ return new double[]{decodeLatitude(decoded[0]), decodeLongitude(decoded[1]), decodeLatitude(decoded[2]), decodeLongitude(decoded[3]), decodeLatitude(decoded[4]), decodeLongitude(decoded[5])};
}
- /** quantizes a provided linestring to be consistent with the index encoding */
- protected Line quantizeLine(Line line) {
- double[] lats = new double[line.numPoints()];
- double[] lons = new double[line.numPoints()];
- for (int i = 0; i < lats.length; ++i) {
- lats[i] = quantizeLat(line.getLat(i));
- lons[i] = quantizeLon(line.getLon(i));
- }
- return new Line(lats, lons);
+ /** encode/decode a triangle */
+ protected int[] encodeDecodeTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
+ byte[] encoded = new byte[7 * LatLonShape.BYTES];
+ LatLonShape.encodeTriangle(encoded, encodeLatitude(ay), encodeLongitude(ax), encodeLatitude(by), encodeLongitude(bx), encodeLatitude(cy), encodeLongitude(cx));
+ int[] decoded = new int[6];
+ LatLonShape.decodeTriangle(encoded, decoded);
+ return decoded;
}
/** use {@link GeoTestUtil#nextPolygon()} to create a random line; TODO: move to GeoTestUtil */
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/d185ba99/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonLineShapeQueries.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonLineShapeQueries.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonLineShapeQueries.java
index 3919e17..ab409f2 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonLineShapeQueries.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonLineShapeQueries.java
@@ -16,19 +16,18 @@
*/
package org.apache.lucene.document;
+
import com.carrotsearch.randomizedtesting.generators.RandomNumbers;
import org.apache.lucene.document.LatLonShape.QueryRelation;
import org.apache.lucene.geo.EdgeTree;
import org.apache.lucene.geo.GeoTestUtil;
-import org.apache.lucene.geo.GeoUtils;
import org.apache.lucene.geo.Line;
import org.apache.lucene.geo.Line2D;
import org.apache.lucene.geo.Polygon2D;
+import org.apache.lucene.geo.Rectangle;
+import org.apache.lucene.geo.Rectangle2D;
import org.apache.lucene.index.PointValues.Relation;
-import static org.apache.lucene.geo.GeoUtils.MAX_LON_INCL;
-import static org.apache.lucene.geo.GeoUtils.MIN_LON_INCL;
-
/** random bounding box and polygon query tests for random generated {@link Line} types */
public class TestLatLonLineShapeQueries extends BaseLatLonShapeTestCase {
@@ -79,40 +78,21 @@ public class TestLatLonLineShapeQueries extends BaseLatLonShapeTestCase {
protected class LineValidator extends Validator {
@Override
public boolean testBBoxQuery(double minLat, double maxLat, double minLon, double maxLon, Object shape) {
- Line l = (Line)shape;
- if (queryRelation == QueryRelation.WITHIN) {
- // within: bounding box of shape should be within query box
- double lMinLat = quantizeLat(l.minLat);
- double lMinLon = quantizeLon(l.minLon);
- double lMaxLat = quantizeLat(l.maxLat);
- double lMaxLon = quantizeLon(l.maxLon);
-
- if (minLon > maxLon) {
- // crosses dateline:
- return minLat <= lMinLat && maxLat >= lMaxLat
- && ((GeoUtils.MIN_LON_INCL <= lMinLon && maxLon >= lMaxLon)
- || (minLon <= lMinLon && GeoUtils.MAX_LON_INCL >= lMaxLon));
- }
- return minLat <= lMinLat && maxLat >= lMaxLat
- && minLon <= lMinLon && maxLon >= lMaxLon;
- }
-
- Line2D line = Line2D.create(quantizeLine(l));
- Relation r;
- if (minLon > maxLon) {
- // crosses dateline:
- r = line.relate(minLat, maxLat, MIN_LON_INCL, maxLon);
- if (r == Relation.CELL_OUTSIDE_QUERY) {
- r = line.relate(minLat, maxLat, minLon, MAX_LON_INCL);
+ Line line = (Line)shape;
+ Rectangle2D rectangle2D = Rectangle2D.create(new Rectangle(minLat, maxLat, minLon, maxLon));
+ for (int i = 0, j = 1; j < line.numPoints(); ++i, ++j) {
+ int[] decoded = encodeDecodeTriangle(line.getLon(i), line.getLat(i), line.getLon(j), line.getLat(j), line.getLon(i), line.getLat(i));
+ if (queryRelation == QueryRelation.WITHIN) {
+ if (rectangle2D.containsTriangle(decoded[1], decoded[0], decoded[3], decoded[2], decoded[5], decoded[4]) == false) {
+ return false;
+ }
+ } else {
+ if (rectangle2D.intersectsTriangle(decoded[1], decoded[0], decoded[3], decoded[2], decoded[5], decoded[4]) == true) {
+ return queryRelation == QueryRelation.INTERSECTS;
+ }
}
- } else {
- r = line.relate(minLat, maxLat, minLon, maxLon);
- }
-
- if (queryRelation == QueryRelation.DISJOINT) {
- return r == Relation.CELL_OUTSIDE_QUERY;
}
- return r != Relation.CELL_OUTSIDE_QUERY;
+ return queryRelation != QueryRelation.INTERSECTS;
}
@Override
@@ -126,31 +106,10 @@ public class TestLatLonLineShapeQueries extends BaseLatLonShapeTestCase {
}
private boolean testLine(EdgeTree queryPoly, Line line) {
- double ax, ay, bx, by, temp;
- Relation r;
+
for (int i = 0, j = 1; j < line.numPoints(); ++i, ++j) {
- ay = quantizeLat(line.getLat(i));
- ax = quantizeLon(line.getLon(i));
- by = quantizeLat(line.getLat(j));
- bx = quantizeLon(line.getLon(j));
- if (ay > by) {
- temp = ay;
- ay = by;
- by = temp;
- temp = ax;
- ax = bx;
- bx = temp;
- } else if (ay == by) {
- if (ax > bx) {
- temp = ay;
- ay = by;
- by = temp;
- temp = ax;
- ax = bx;
- bx = temp;
- }
- }
- r = queryPoly.relateTriangle(ax, ay, bx, by, ax, ay);
+ double[] qTriangle = quantizeTriangle(line.getLon(i), line.getLat(i), line.getLon(j), line.getLat(j), line.getLon(i), line.getLat(i));
+ Relation r = queryPoly.relateTriangle(qTriangle[1], qTriangle[0], qTriangle[3], qTriangle[2], qTriangle[5], qTriangle[4]);
if (queryRelation == QueryRelation.DISJOINT) {
if (r != Relation.CELL_OUTSIDE_QUERY) return false;
} else if (queryRelation == QueryRelation.WITHIN) {
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/d185ba99/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPolygonShapeQueries.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPolygonShapeQueries.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPolygonShapeQueries.java
index 24cba64..9bc9b48 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPolygonShapeQueries.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPolygonShapeQueries.java
@@ -23,12 +23,11 @@ import org.apache.lucene.geo.EdgeTree;
import org.apache.lucene.geo.Line2D;
import org.apache.lucene.geo.Polygon;
import org.apache.lucene.geo.Polygon2D;
+import org.apache.lucene.geo.Rectangle;
+import org.apache.lucene.geo.Rectangle2D;
import org.apache.lucene.geo.Tessellator;
import org.apache.lucene.index.PointValues.Relation;
-import static org.apache.lucene.geo.GeoUtils.MAX_LON_INCL;
-import static org.apache.lucene.geo.GeoUtils.MIN_LON_INCL;
-
/** random bounding box and polygon query tests for random indexed {@link Polygon} types */
public class TestLatLonPolygonShapeQueries extends BaseLatLonShapeTestCase {
@@ -69,38 +68,21 @@ public class TestLatLonPolygonShapeQueries extends BaseLatLonShapeTestCase {
@Override
public boolean testBBoxQuery(double minLat, double maxLat, double minLon, double maxLon, Object shape) {
Polygon p = (Polygon)shape;
- if (queryRelation == QueryRelation.WITHIN) {
- // within: bounding box of shape should be within query box
- double pMinLat = quantizeLat(p.minLat);
- double pMinLon = quantizeLon(p.minLon);
- double pMaxLat = quantizeLat(p.maxLat);
- double pMaxLon = quantizeLon(p.maxLon);
-
- if (minLon > maxLon) {
- // crosses dateline:
- return minLat <= pMinLat && maxLat >= pMaxLat
- && ((MIN_LON_INCL <= pMinLon && maxLon >= pMaxLon)
- || (minLon <= pMinLon && MAX_LON_INCL >= pMaxLon));
- }
- return minLat <= pMinLat && maxLat >= pMaxLat
- && minLon <= pMinLon && maxLon >= pMaxLon;
- }
-
- Polygon2D poly = Polygon2D.create(quantizePolygon(p));
- Relation r;
- if (minLon > maxLon) {
- // crosses dateline:
- r = poly.relate(minLat, maxLat, MIN_LON_INCL, maxLon);
- if (r == Relation.CELL_OUTSIDE_QUERY) {
- r = poly.relate(minLat, maxLat, minLon, MAX_LON_INCL);
+ Rectangle2D rectangle2D = Rectangle2D.create(new Rectangle(minLat, maxLat, minLon, maxLon));
+ List<Tessellator.Triangle> tessellation = Tessellator.tessellate(p);
+ for (Tessellator.Triangle t : tessellation) {
+ int[] decoded = encodeDecodeTriangle(t.getLon(0), t.getLat(0), t.getLon(1), t.getLat(1), t.getLon(2), t.getLat(2));
+ if (queryRelation == QueryRelation.WITHIN) {
+ if (rectangle2D.containsTriangle(decoded[1], decoded[0], decoded[3], decoded[2], decoded[5], decoded[4]) == false) {
+ return false;
+ }
+ } else {
+ if (rectangle2D.intersectsTriangle(decoded[1], decoded[0], decoded[3], decoded[2], decoded[5], decoded[4]) == true) {
+ return queryRelation == QueryRelation.INTERSECTS;
+ }
}
- } else {
- r = poly.relate(minLat, maxLat, minLon, maxLon);
- }
- if (queryRelation == QueryRelation.DISJOINT) {
- return r == Relation.CELL_OUTSIDE_QUERY;
}
- return r != Relation.CELL_OUTSIDE_QUERY;
+ return queryRelation != QueryRelation.INTERSECTS;
}
@Override
@@ -116,10 +98,8 @@ public class TestLatLonPolygonShapeQueries extends BaseLatLonShapeTestCase {
private boolean testPolygon(EdgeTree tree, Polygon shape) {
List<Tessellator.Triangle> tessellation = Tessellator.tessellate(shape);
for (Tessellator.Triangle t : tessellation) {
- // we quantize the triangle for consistency with the index
- Relation r = tree.relateTriangle(quantizeLon(t.getLon(0)), quantizeLat(t.getLat(0)),
- quantizeLon(t.getLon(1)), quantizeLat(t.getLat(1)),
- quantizeLon(t.getLon(2)), quantizeLat(t.getLat(2)));
+ double[] qTriangle = quantizeTriangle(t.getLon(0), t.getLat(0), t.getLon(1), t.getLat(1), t.getLon(2), t.getLat(2));
+ Relation r = tree.relateTriangle(qTriangle[1], qTriangle[0], qTriangle[3], qTriangle[2], qTriangle[5], qTriangle[4]);
if (queryRelation == QueryRelation.DISJOINT) {
if (r != Relation.CELL_OUTSIDE_QUERY) return false;
} else if (queryRelation == QueryRelation.WITHIN) {
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/d185ba99/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShape.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShape.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShape.java
index d3ab8a6..c4e0581 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShape.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShape.java
@@ -16,15 +16,24 @@
*/
package org.apache.lucene.document;
+import java.util.Arrays;
+
import com.carrotsearch.randomizedtesting.generators.RandomNumbers;
import org.apache.lucene.document.LatLonShape.QueryRelation;
+import org.apache.lucene.geo.GeoEncodingUtils;
import org.apache.lucene.geo.GeoTestUtil;
+import org.apache.lucene.geo.GeoUtils;
import org.apache.lucene.geo.Line;
import org.apache.lucene.geo.Polygon;
+import org.apache.lucene.geo.Polygon2D;
+import org.apache.lucene.geo.Rectangle;
+import org.apache.lucene.geo.Rectangle2D;
+import org.apache.lucene.geo.Tessellator;
import org.apache.lucene.index.DirectoryReader;
import org.apache.lucene.index.IndexReader;
import org.apache.lucene.index.IndexWriter;
import org.apache.lucene.index.IndexWriterConfig;
+import org.apache.lucene.index.PointValues;
import org.apache.lucene.index.RandomIndexWriter;
import org.apache.lucene.index.SerialMergeScheduler;
import org.apache.lucene.search.IndexSearcher;
@@ -35,6 +44,9 @@ import org.apache.lucene.util.LuceneTestCase;
import org.apache.lucene.util.TestUtil;
import org.junit.Ignore;
+import static org.apache.lucene.geo.GeoEncodingUtils.encodeLatitude;
+import static org.apache.lucene.geo.GeoEncodingUtils.encodeLongitude;
+
/** Test case for indexing polygons and querying by bounding box */
public class TestLatLonShape extends LuceneTestCase {
protected static String FIELDNAME = "field";
@@ -208,6 +220,19 @@ public class TestLatLonShape extends LuceneTestCase {
Polygon poly = new Polygon(new double[] {-1.490648725633769E-132d, 90d, 90d, -1.490648725633769E-132d},
new double[] {0d, 0d, 180d, 0d});
+ Rectangle rectangle = new Rectangle(-29.46555603761226d, 0.0d, 8.381903171539307E-8d, 0.9999999403953552d);
+ Rectangle2D rectangle2D = Rectangle2D.create(rectangle);
+
+ Tessellator.Triangle t = Tessellator.tessellate(poly).get(0);
+
+ byte[] encoded = new byte[7 * LatLonShape.BYTES];
+ LatLonShape.encodeTriangle(encoded, encodeLatitude(t.getLat(0)), encodeLongitude(t.getLon(0)),
+ encodeLatitude(t.getLat(1)), encodeLongitude(t.getLon(1)), encodeLatitude(t.getLat(2)), encodeLongitude(t.getLon(2)));
+ int[] decoded = new int[6];
+ LatLonShape.decodeTriangle(encoded, decoded);
+
+ int expected =rectangle2D.intersectsTriangle(decoded[1], decoded[0], decoded[3], decoded[2], decoded[5], decoded[4]) ? 0 : 1;
+
Document document = new Document();
addPolygonsToDoc(FIELDNAME, document, poly);
writer.addDocument(document);
@@ -219,7 +244,7 @@ public class TestLatLonShape extends LuceneTestCase {
// search a bbox in the hole
Query q = LatLonShape.newBoxQuery(FIELDNAME, QueryRelation.DISJOINT,-29.46555603761226d, 0.0d, 8.381903171539307E-8d, 0.9999999403953552d);
- assertEquals(0, searcher.count(q));
+ assertEquals(expected, searcher.count(q));
IOUtils.close(reader, dir);
}
@@ -245,4 +270,534 @@ public class TestLatLonShape extends LuceneTestCase {
assertEquals(1, s.count(q));
IOUtils.close(r, dir);
}
+
+ //One shared point with MBR -> MinLat, MinLon
+ public void testPolygonEncodingMinLatMinLon() {
+ double alat = 0.0;
+ double alon = 0.0;
+ double blat = 1.0;
+ double blon = 2.0;
+ double clat = 2.0;
+ double clon = 1.0;
+ int alatEnc = GeoEncodingUtils.encodeLatitude(alat);
+ int alonEnc = GeoEncodingUtils.encodeLongitude(alon);
+ int blatEnc = GeoEncodingUtils.encodeLatitude(blat);
+ int blonEnc = GeoEncodingUtils.encodeLongitude(blon);
+ int clatEnc = GeoEncodingUtils.encodeLatitude(clat);
+ int clonEnc = GeoEncodingUtils.encodeLongitude(clon);
+ verifyEncodingPermutations(alatEnc, alonEnc, blatEnc, blonEnc, clatEnc, clonEnc);
+ byte[] b = new byte[7 * LatLonShape.BYTES];
+ LatLonShape.encodeTriangle(b, alatEnc, alonEnc, blatEnc, blonEnc, clatEnc, clonEnc);
+ int[] encoded = new int[6];
+ LatLonShape.decodeTriangle(b, encoded);
+ assertTrue(encoded[0] == alatEnc);
+ assertTrue(encoded[1] == alonEnc);
+ assertTrue(encoded[2] == blatEnc);
+ assertTrue(encoded[3] == blonEnc);
+ assertTrue(encoded[4] == clatEnc);
+ assertTrue(encoded[5] == clonEnc);
+ }
+
+ //One shared point with MBR -> MinLat, MaxLon
+ public void testPolygonEncodingMinLatMaxLon() {
+ double alat = 1.0;
+ double alon = 0.0;
+ double blat = 0.0;
+ double blon = 2.0;
+ double clat = 2.0;
+ double clon = 1.0;
+ int alatEnc = GeoEncodingUtils.encodeLatitude(alat);
+ int alonEnc = GeoEncodingUtils.encodeLongitude(alon);
+ int blatEnc = GeoEncodingUtils.encodeLatitude(blat);
+ int blonEnc = GeoEncodingUtils.encodeLongitude(blon);
+ int clatEnc = GeoEncodingUtils.encodeLatitude(clat);
+ int clonEnc = GeoEncodingUtils.encodeLongitude(clon);
+ verifyEncodingPermutations(alatEnc, alonEnc, blatEnc, blonEnc, clatEnc, clonEnc);
+ byte[] b = new byte[7 * LatLonShape.BYTES];
+ LatLonShape.encodeTriangle(b, alatEnc, alonEnc, blatEnc, blonEnc, clatEnc, clonEnc);
+ int[] encoded = new int[6];
+ LatLonShape.decodeTriangle(b, encoded);
+ assertTrue(encoded[0] == alatEnc);
+ assertTrue(encoded[1] == alonEnc);
+ assertTrue(encoded[2] == blatEnc);
+ assertTrue(encoded[3] == blonEnc);
+ assertTrue(encoded[4] == clatEnc);
+ assertTrue(encoded[5] == clonEnc);
+ }
+
+ //One shared point with MBR -> MaxLat, MaxLon
+ public void testPolygonEncodingMaxLatMaxLon() {
+ double alat = 1.0;
+ double alon = 0.0;
+ double blat = 2.0;
+ double blon = 2.0;
+ double clat = 0.0;
+ double clon = 1.0;
+ int alatEnc = GeoEncodingUtils.encodeLatitude(alat);
+ int alonEnc = GeoEncodingUtils.encodeLongitude(alon);
+ int blatEnc = GeoEncodingUtils.encodeLatitude(clat);
+ int blonEnc = GeoEncodingUtils.encodeLongitude(clon);
+ int clatEnc = GeoEncodingUtils.encodeLatitude(blat);
+ int clonEnc = GeoEncodingUtils.encodeLongitude(blon);
+ verifyEncodingPermutations(alatEnc, alonEnc, blatEnc, blonEnc, clatEnc, clonEnc);
+ byte[] b = new byte[7 * LatLonShape.BYTES];
+ LatLonShape.encodeTriangle(b, alatEnc, alonEnc, blatEnc, blonEnc, clatEnc, clonEnc);
+ int[] encoded = new int[6];
+ LatLonShape.decodeTriangle(b, encoded);
+ assertTrue(encoded[0] == alatEnc);
+ assertTrue(encoded[1] == alonEnc);
+ assertTrue(encoded[2] == blatEnc);
+ assertTrue(encoded[3] == blonEnc);
+ assertTrue(encoded[4] == clatEnc);
+ assertTrue(encoded[5] == clonEnc);
+ }
+
+ //One shared point with MBR -> MaxLat, MinLon
+ public void testPolygonEncodingMaxLatMinLon() {
+ double alat = 2.0;
+ double alon = 0.0;
+ double blat = 1.0;
+ double blon = 2.0;
+ double clat = 0.0;
+ double clon = 1.0;
+ int alatEnc = GeoEncodingUtils.encodeLatitude(alat);
+ int alonEnc = GeoEncodingUtils.encodeLongitude(alon);
+ int blatEnc = GeoEncodingUtils.encodeLatitude(clat);
+ int blonEnc = GeoEncodingUtils.encodeLongitude(clon);
+ int clatEnc = GeoEncodingUtils.encodeLatitude(blat);
+ int clonEnc = GeoEncodingUtils.encodeLongitude(blon);
+ verifyEncodingPermutations(alatEnc, alonEnc, blatEnc, blonEnc, clatEnc, clonEnc);
+ byte[] b = new byte[7 * LatLonShape.BYTES];
+ LatLonShape.encodeTriangle(b, alatEnc, alonEnc, blatEnc, blonEnc, clatEnc, clonEnc);
+ int[] encoded = new int[6];
+ LatLonShape.decodeTriangle(b, encoded);
+ assertTrue(encoded[0] == alatEnc);
+ assertTrue(encoded[1] == alonEnc);
+ assertTrue(encoded[2] == blatEnc);
+ assertTrue(encoded[3] == blonEnc);
+ assertTrue(encoded[4] == clatEnc);
+ assertTrue(encoded[5] == clonEnc);
+ }
+
+ //Two shared point with MBR -> [MinLat, MinLon], [MaxLat, MaxLon], third point below
+ public void testPolygonEncodingMinLatMinLonMaxLatMaxLonBelow() {
+ double alat = 0.0;
+ double alon = 0.0;
+ double blat = 0.25;
+ double blon = 0.75;
+ double clat = 2.0;
+ double clon = 2.0;
+ int alatEnc = GeoEncodingUtils.encodeLatitude(alat);
+ int alonEnc = GeoEncodingUtils.encodeLongitude(alon);
+ int blatEnc = GeoEncodingUtils.encodeLatitude(blat);
+ int blonEnc = GeoEncodingUtils.encodeLongitude(blon);
+ int clatEnc = GeoEncodingUtils.encodeLatitude(clat);
+ int clonEnc = GeoEncodingUtils.encodeLongitude(clon);
+ verifyEncodingPermutations(alatEnc, alonEnc, blatEnc, blonEnc, clatEnc, clonEnc);
+ byte[] b = new byte[7 * LatLonShape.BYTES];
+ LatLonShape.encodeTriangle(b, alatEnc, alonEnc, blatEnc, blonEnc, clatEnc, clonEnc);
+ int[] encoded = new int[6];
+ LatLonShape.decodeTriangle(b, encoded);
+ assertTrue(encoded[0] == alatEnc);
+ assertTrue(encoded[1] == alonEnc);
+ assertTrue(encoded[2] == blatEnc);
+ assertTrue(encoded[3] == blonEnc);
+ assertTrue(encoded[4] == clatEnc);
+ assertTrue(encoded[5] == clonEnc);
+ }
+
+ //Two shared point with MBR -> [MinLat, MinLon], [MaxLat, MaxLon], third point above
+ public void testPolygonEncodingMinLatMinLonMaxLatMaxLonAbove() {
+ double alat = 0.0;
+ double alon = 0.0;
+ double blat = 2.0;
+ double blon = 2.0;
+ double clat = 1.75;
+ double clon = 1.25;
+ int alatEnc = GeoEncodingUtils.encodeLatitude(alat);
+ int alonEnc = GeoEncodingUtils.encodeLongitude(alon);
+ int blatEnc = GeoEncodingUtils.encodeLatitude(blat);
+ int blonEnc = GeoEncodingUtils.encodeLongitude(blon);
+ int clatEnc = GeoEncodingUtils.encodeLatitude(clat);
+ int clonEnc = GeoEncodingUtils.encodeLongitude(clon);
+ verifyEncodingPermutations(alatEnc, alonEnc, blatEnc, blonEnc, clatEnc, clonEnc);
+ byte[] b = new byte[7 * LatLonShape.BYTES];
+ LatLonShape.encodeTriangle(b, alatEnc, alonEnc, blatEnc, blonEnc, clatEnc, clonEnc);
+ int[] encoded = new int[6];
+ LatLonShape.decodeTriangle(b, encoded);
+ assertTrue(encoded[0] == alatEnc);
+ assertTrue(encoded[1] == alonEnc);
+ assertTrue(encoded[2] == blatEnc);
+ assertTrue(encoded[3] == blonEnc);
+ assertTrue(encoded[4] == clatEnc);
+ assertTrue(encoded[5] == clonEnc);
+ }
+
+ //Two shared point with MBR -> [MinLat, MaxLon], [MaxLat, MinLon], third point below
+ public void testPolygonEncodingMinLatMaxLonMaxLatMinLonBelow() {
+ double alat = 2.0;
+ double alon = 0.0;
+ double blat = 0.25;
+ double blon = 0.75;
+ double clat = 0.0;
+ double clon = 2.0;
+ int alatEnc = GeoEncodingUtils.encodeLatitude(alat);
+ int alonEnc = GeoEncodingUtils.encodeLongitude(alon);
+ int blatEnc = GeoEncodingUtils.encodeLatitude(blat);
+ int blonEnc = GeoEncodingUtils.encodeLongitude(blon);
+ int clatEnc = GeoEncodingUtils.encodeLatitude(clat);
+ int clonEnc = GeoEncodingUtils.encodeLongitude(clon);
+ verifyEncodingPermutations(alatEnc, alonEnc, blatEnc, blonEnc, clatEnc, clonEnc);
+ byte[] b = new byte[7 * LatLonShape.BYTES];
+ LatLonShape.encodeTriangle(b, alatEnc, alonEnc, blatEnc, blonEnc, clatEnc, clonEnc);
+ int[] encoded = new int[6];
+ LatLonShape.decodeTriangle(b, encoded);
+ assertTrue(encoded[0] == alatEnc);
+ assertTrue(encoded[1] == alonEnc);
+ assertTrue(encoded[2] == blatEnc);
+ assertTrue(encoded[3] == blonEnc);
+ assertTrue(encoded[4] == clatEnc);
+ assertTrue(encoded[5] == clonEnc);
+ }
+
+ //Two shared point with MBR -> [MinLat, MaxLon], [MaxLat, MinLon], third point above
+ public void testPolygonEncodingMinLatMaxLonMaxLatMinLonAbove() {
+ double alat = 2.0;
+ double alon = 0.0;
+ double blat = 0.0;
+ double blon = 2.0;
+ double clat = 1.75;
+ double clon = 1.25;
+ int alatEnc = GeoEncodingUtils.encodeLatitude(alat);
+ int alonEnc = GeoEncodingUtils.encodeLongitude(alon);
+ int blatEnc = GeoEncodingUtils.encodeLatitude(blat);
+ int blonEnc = GeoEncodingUtils.encodeLongitude(blon);
+ int clatEnc = GeoEncodingUtils.encodeLatitude(clat);
+ int clonEnc = GeoEncodingUtils.encodeLongitude(clon);
+ verifyEncodingPermutations(alatEnc, alonEnc, blatEnc, blonEnc, clatEnc, clonEnc);
+ byte[] b = new byte[7 * LatLonShape.BYTES];
+ LatLonShape.encodeTriangle(b, alatEnc, alonEnc, blatEnc, blonEnc, clatEnc, clonEnc);
+ int[] encoded = new int[6];
+ LatLonShape.decodeTriangle(b, encoded);
+ assertTrue(encoded[0] == alatEnc);
+ assertTrue(encoded[1] == alonEnc);
+ assertTrue(encoded[2] == blatEnc);
+ assertTrue(encoded[3] == blonEnc);
+ assertTrue(encoded[4] == clatEnc);
+ assertTrue(encoded[5] == clonEnc);
+ }
+
+ //all points shared with MBR
+ public void testPolygonEncodingAllSharedAbove() {
+ double alat = 0.0;
+ double alon = 0.0;
+ double blat = 0.0;
+ double blon = 2.0;
+ double clat = 2.0;
+ double clon = 2.0;
+ int alatEnc = GeoEncodingUtils.encodeLatitude(alat);
+ int alonEnc = GeoEncodingUtils.encodeLongitude(alon);
+ int blatEnc = GeoEncodingUtils.encodeLatitude(blat);
+ int blonEnc = GeoEncodingUtils.encodeLongitude(blon);
+ int clatEnc = GeoEncodingUtils.encodeLatitude(clat);
+ int clonEnc = GeoEncodingUtils.encodeLongitude(clon);
+ verifyEncodingPermutations(alatEnc, alonEnc, blatEnc, blonEnc, clatEnc, clonEnc);
+ byte[] b = new byte[7 * LatLonShape.BYTES];
+ LatLonShape.encodeTriangle(b, alatEnc, alonEnc, blatEnc, blonEnc, clatEnc, clonEnc);
+ int[] encoded = new int[6];
+ LatLonShape.decodeTriangle(b, encoded);
+ assertTrue(encoded[0] == alatEnc);
+ assertTrue(encoded[1] == alonEnc);
+ assertTrue(encoded[2] == blatEnc);
+ assertTrue(encoded[3] == blonEnc);
+ assertTrue(encoded[4] == clatEnc);
+ assertTrue(encoded[5] == clonEnc);
+ }
+
+ //all points shared with MBR
+ public void testPolygonEncodingAllSharedBelow() {
+ double alat = 2.0;
+ double alon = 0.0;
+ double blat = 0.0;
+ double blon = 0.0;
+ double clat = 2.0;
+ double clon = 2.0;
+ int alatEnc = GeoEncodingUtils.encodeLatitude(alat);
+ int alonEnc = GeoEncodingUtils.encodeLongitude(alon);
+ int blatEnc = GeoEncodingUtils.encodeLatitude(blat);
+ int blonEnc = GeoEncodingUtils.encodeLongitude(blon);
+ int clatEnc = GeoEncodingUtils.encodeLatitude(clat);
+ int clonEnc = GeoEncodingUtils.encodeLongitude(clon);
+ byte[] b = new byte[7 * LatLonShape.BYTES];
+ LatLonShape.encodeTriangle(b, alatEnc, alonEnc, blatEnc, blonEnc, clatEnc, clonEnc);
+ int[] encoded = new int[6];
+ LatLonShape.decodeTriangle(b, encoded);
+ assertTrue(encoded[0] == alatEnc);
+ assertTrue(encoded[1] == alonEnc);
+ assertTrue(encoded[2] == blatEnc);
+ assertTrue(encoded[3] == blonEnc);
+ assertTrue(encoded[4] == clatEnc);
+ assertTrue(encoded[5] == clonEnc);
+ }
+
+ //[a,b,c] == [c,a,b] == [b,c,a] == [c,b,a] == [b,a,c] == [a,c,b]
+ public void verifyEncodingPermutations(int alatEnc, int alonEnc, int blatEnc, int blonEnc, int clatEnc, int clonEnc) {
+ //this is only valid when points are not co-planar
+ assertTrue(GeoUtils.orient(alatEnc, alonEnc, blatEnc, blonEnc, clatEnc, clonEnc) != 0);
+ byte[] b = new byte[7 * LatLonShape.BYTES];
+ //[a,b,c]
+ LatLonShape.encodeTriangle(b, alatEnc, alonEnc, blatEnc, blonEnc, clatEnc, clonEnc);
+ int[] encodedABC = new int[6];
+ LatLonShape.decodeTriangle(b, encodedABC);
+ //[c,a,b]
+ LatLonShape.encodeTriangle(b, clatEnc, clonEnc, alatEnc, alonEnc, blatEnc, blonEnc);
+ int[] encodedCAB = new int[6];
+ LatLonShape.decodeTriangle(b, encodedCAB);
+ assertTrue(Arrays.equals(encodedABC, encodedCAB));
+ //[b,c,a]
+ LatLonShape.encodeTriangle(b, blatEnc, blonEnc, clatEnc, clonEnc, alatEnc, alonEnc);
+ int[] encodedBCA = new int[6];
+ LatLonShape.decodeTriangle(b, encodedBCA);
+ assertTrue(Arrays.equals(encodedABC, encodedBCA));
+ //[c,b,a]
+ LatLonShape.encodeTriangle(b, clatEnc, clonEnc, blatEnc, blonEnc, alatEnc, alonEnc);
+ int[] encodedCBA= new int[6];
+ LatLonShape.decodeTriangle(b, encodedCBA);
+ assertTrue(Arrays.equals(encodedABC, encodedCBA));
+ //[b,a,c]
+ LatLonShape.encodeTriangle(b, blatEnc, blonEnc, alatEnc, alonEnc, clatEnc, clonEnc);
+ int[] encodedBAC= new int[6];
+ LatLonShape.decodeTriangle(b, encodedBAC);
+ assertTrue(Arrays.equals(encodedABC, encodedBAC));
+ //[a,c,b]
+ LatLonShape.encodeTriangle(b, alatEnc, alonEnc, clatEnc, clonEnc, blatEnc, blonEnc);
+ int[] encodedACB= new int[6];
+ LatLonShape.decodeTriangle(b, encodedACB);
+ assertTrue(Arrays.equals(encodedABC, encodedACB));
+ }
+
+ public void testPointEncoding() {
+ double lat = 45.0;
+ double lon = 45.0;
+ int latEnc = GeoEncodingUtils.encodeLatitude(lat);
+ int lonEnc = GeoEncodingUtils.encodeLongitude(lon);
+ byte[] b = new byte[7 * LatLonShape.BYTES];
+ LatLonShape.encodeTriangle(b, latEnc, lonEnc, latEnc, lonEnc, latEnc, lonEnc);
+ int[] encoded = new int[6];
+ LatLonShape.decodeTriangle(b, encoded);
+ assertTrue(encoded[0] == latEnc && encoded[2] == latEnc && encoded[4] == latEnc);
+ assertTrue(encoded[1] == lonEnc && encoded[3] == lonEnc && encoded[5] == lonEnc);
+ }
+
+ public void testLineEncodingSameLat() {
+ double lat = 2.0;
+ double alon = 0.0;
+ double blon = 2.0;
+ int latEnc = GeoEncodingUtils.encodeLatitude(lat);
+ int alonEnc = GeoEncodingUtils.encodeLongitude(alon);
+ int blonEnc = GeoEncodingUtils.encodeLongitude(blon);
+ byte[] b = new byte[7 * LatLonShape.BYTES];
+ LatLonShape.encodeTriangle(b, latEnc, alonEnc, latEnc, blonEnc, latEnc, alonEnc);
+ int[] encoded = new int[6];
+ LatLonShape.decodeTriangle(b, encoded);
+ assertTrue(encoded[0] == latEnc);
+ assertTrue(encoded[1] == alonEnc);
+ assertTrue(encoded[2] == latEnc);
+ assertTrue(encoded[3] == blonEnc);
+ assertTrue(encoded[4] == latEnc);
+ assertTrue(encoded[5] == alonEnc);
+ LatLonShape.encodeTriangle(b, latEnc, alonEnc, latEnc, alonEnc, latEnc, blonEnc);
+ encoded = new int[6];
+ LatLonShape.decodeTriangle(b, encoded);
+ assertTrue(encoded[0] == latEnc);
+ assertTrue(encoded[1] == alonEnc);
+ assertTrue(encoded[2] == latEnc);
+ assertTrue(encoded[3] == alonEnc);
+ assertTrue(encoded[4] == latEnc);
+ assertTrue(encoded[5] == blonEnc);
+ LatLonShape.encodeTriangle(b, latEnc, blonEnc, latEnc, alonEnc, latEnc, alonEnc);
+ encoded = new int[6];
+ LatLonShape.decodeTriangle(b, encoded);
+ assertTrue(encoded[0] == latEnc);
+ assertTrue(encoded[1] == alonEnc);
+ assertTrue(encoded[2] == latEnc);
+ assertTrue(encoded[3] == blonEnc);
+ assertTrue(encoded[4] == latEnc);
+ assertTrue(encoded[5] == alonEnc);
+ }
+
+ public void testLineEncodingSameLon() {
+ double alat = 0.0;
+ double blat = 2.0;
+ double lon = 2.0;
+ int alatEnc = GeoEncodingUtils.encodeLatitude(alat);
+ int blatEnc = GeoEncodingUtils.encodeLatitude(blat);
+ int lonEnc = GeoEncodingUtils.encodeLongitude(lon);
+ byte[] b = new byte[7 * LatLonShape.BYTES];
+ LatLonShape.encodeTriangle(b, alatEnc, lonEnc, blatEnc, lonEnc, alatEnc, lonEnc);
+ int[] encoded = new int[6];
+ LatLonShape.decodeTriangle(b, encoded);
+ assertTrue(encoded[0] == alatEnc);
+ assertTrue(encoded[1] == lonEnc);
+ assertTrue(encoded[2] == blatEnc);
+ assertTrue(encoded[3] == lonEnc);
+ assertTrue(encoded[4] == alatEnc);
+ assertTrue(encoded[5] == lonEnc);
+ LatLonShape.encodeTriangle(b, alatEnc, lonEnc, alatEnc, lonEnc, blatEnc, lonEnc);
+ encoded = new int[6];
+ LatLonShape.decodeTriangle(b, encoded);
+ assertTrue(encoded[0] == alatEnc);
+ assertTrue(encoded[1] == lonEnc);
+ assertTrue(encoded[2] == alatEnc);
+ assertTrue(encoded[3] == lonEnc);
+ assertTrue(encoded[4] == blatEnc);
+ assertTrue(encoded[5] == lonEnc);
+ LatLonShape.encodeTriangle(b, blatEnc, lonEnc, alatEnc, lonEnc, alatEnc, lonEnc);
+ encoded = new int[6];
+ LatLonShape.decodeTriangle(b, encoded);
+ assertTrue(encoded[0] == alatEnc);
+ assertTrue(encoded[1] == lonEnc);
+ assertTrue(encoded[2] == blatEnc);
+ assertTrue(encoded[3] == lonEnc);
+ assertTrue(encoded[4] == alatEnc);
+ assertTrue(encoded[5] == lonEnc);
+ }
+
+ public void testLineEncoding() {
+ double alat = 0.0;
+ double blat = 2.0;
+ double alon = 0.0;
+ double blon = 2.0;
+ int alatEnc = GeoEncodingUtils.encodeLatitude(alat);
+ int blatEnc = GeoEncodingUtils.encodeLatitude(blat);
+ int alonEnc = GeoEncodingUtils.encodeLongitude(alon);
+ int blonEnc = GeoEncodingUtils.encodeLongitude(blon);
+ byte[] b = new byte[7 * LatLonShape.BYTES];
+ LatLonShape.encodeTriangle(b, alatEnc, alonEnc, blatEnc, blonEnc, alatEnc, alonEnc);
+ int[] encoded = new int[6];
+ LatLonShape.decodeTriangle(b, encoded);
+ assertTrue(encoded[0] == alatEnc);
+ assertTrue(encoded[1] == alonEnc);
+ assertTrue(encoded[2] == blatEnc);
+ assertTrue(encoded[3] == blonEnc);
+ assertTrue(encoded[4] == alatEnc);
+ assertTrue(encoded[5] == alonEnc);
+ LatLonShape.encodeTriangle(b, alatEnc, alonEnc, alatEnc, alonEnc, blatEnc, blonEnc);
+ encoded = new int[6];
+ LatLonShape.decodeTriangle(b, encoded);
+ assertTrue(encoded[0] == alatEnc);
+ assertTrue(encoded[1] == alonEnc);
+ assertTrue(encoded[2] == alatEnc);
+ assertTrue(encoded[3] == alonEnc);
+ assertTrue(encoded[4] == blatEnc);
+ assertTrue(encoded[5] == blonEnc);
+ LatLonShape.encodeTriangle(b, blatEnc, blonEnc, alatEnc, alonEnc, alatEnc, alonEnc);
+ encoded = new int[6];
+ LatLonShape.decodeTriangle(b, encoded);
+ assertTrue(encoded[0] == alatEnc);
+ assertTrue(encoded[1] == alonEnc);
+ assertTrue(encoded[2] == blatEnc);
+ assertTrue(encoded[3] == blonEnc);
+ assertTrue(encoded[4] == alatEnc);
+ assertTrue(encoded[5] == alonEnc);
+ }
+
+ public void testRandomPointEncoding() {
+ double alat = GeoTestUtil.nextLatitude();
+ double alon = GeoTestUtil.nextLongitude();
+ verifyEncoding(alat, alon, alat, alon, alat, alon);
+ }
+
+ public void testRandomLineEncoding() {
+ double alat = GeoTestUtil.nextLatitude();
+ double alon = GeoTestUtil.nextLongitude();
+ double blat = GeoTestUtil.nextLatitude();
+ double blon = GeoTestUtil.nextLongitude();
+ verifyEncoding(alat, alon, blat, blon, alat, alon);
+ }
+
+ public void testRandomPolygonEncoding() {
+ double alat = GeoTestUtil.nextLatitude();
+ double alon = GeoTestUtil.nextLongitude();
+ double blat = GeoTestUtil.nextLatitude();
+ double blon = GeoTestUtil.nextLongitude();
+ double clat = GeoTestUtil.nextLatitude();
+ double clon = GeoTestUtil.nextLongitude();
+ verifyEncoding(alat, alon, blat, blon, clat, clon);
+ }
+
+ private void verifyEncoding(double alat, double alon, double blat, double blon, double clat, double clon) {
+ int[] original = new int[]{GeoEncodingUtils.encodeLatitude(alat),
+ GeoEncodingUtils.encodeLongitude(alon),
+ GeoEncodingUtils.encodeLatitude(blat),
+ GeoEncodingUtils.encodeLongitude(blon),
+ GeoEncodingUtils.encodeLatitude(clat),
+ GeoEncodingUtils.encodeLongitude(clon)};
+
+ //quantize the triangle
+ byte[] b = new byte[7 * LatLonShape.BYTES];
+ LatLonShape.encodeTriangle(b, original[0], original[1], original[2], original[3], original[4], original[5]);
+ int[] encoded = new int[6];
+ LatLonShape.decodeTriangle(b, encoded);
+ double[] encodedQuantize = new double[] {GeoEncodingUtils.decodeLatitude(encoded[0]),
+ GeoEncodingUtils.decodeLongitude(encoded[1]),
+ GeoEncodingUtils.decodeLatitude(encoded[2]),
+ GeoEncodingUtils.decodeLongitude(encoded[3]),
+ GeoEncodingUtils.decodeLatitude(encoded[4]),
+ GeoEncodingUtils.decodeLongitude(encoded[5])};
+
+ int orientation = GeoUtils.orient(original[1], original[0], original[3], original[2], original[5], original[4]);
+ //quantize original
+ double[] originalQuantize;
+ //we need to change the orientation if CW
+ if (orientation == -1) {
+ originalQuantize = new double[] {GeoEncodingUtils.decodeLatitude(original[4]),
+ GeoEncodingUtils.decodeLongitude(original[5]),
+ GeoEncodingUtils.decodeLatitude(original[2]),
+ GeoEncodingUtils.decodeLongitude(original[3]),
+ GeoEncodingUtils.decodeLatitude(original[0]),
+ GeoEncodingUtils.decodeLongitude(original[1])};
+ } else {
+ originalQuantize = new double[] {GeoEncodingUtils.decodeLatitude(original[0]),
+ GeoEncodingUtils.decodeLongitude(original[1]),
+ GeoEncodingUtils.decodeLatitude(original[2]),
+ GeoEncodingUtils.decodeLongitude(original[3]),
+ GeoEncodingUtils.decodeLatitude(original[4]),
+ GeoEncodingUtils.decodeLongitude(original[5])};
+ }
+
+ for (int i =0; i < 100; i ++) {
+ Polygon polygon = GeoTestUtil.nextPolygon();
+ Polygon2D polygon2D = Polygon2D.create(polygon);
+ PointValues.Relation originalRelation = polygon2D.relateTriangle(originalQuantize[1], originalQuantize[0], originalQuantize[3], originalQuantize[2], originalQuantize[5], originalQuantize[4]);
+ PointValues.Relation encodedRelation = polygon2D.relateTriangle(encodedQuantize[1], encodedQuantize[0], encodedQuantize[3], encodedQuantize[2], encodedQuantize[5], encodedQuantize[4]);
+ assertTrue(originalRelation == encodedRelation);
+ }
+ }
+
+ public void testDegeneratedTriangle() {
+ double alat = 1e-26d;
+ double alon = 0.0d;
+ double blat = -1.0d;
+ double blon = 0.0d;
+ double clat = 1.0d;
+ double clon = 0.0d;
+ int alatEnc = GeoEncodingUtils.encodeLatitude(alat);
+ int alonEnc = GeoEncodingUtils.encodeLongitude(alon);
+ int blatEnc = GeoEncodingUtils.encodeLatitude(blat);
+ int blonEnc = GeoEncodingUtils.encodeLongitude(blon);
+ int clatEnc = GeoEncodingUtils.encodeLatitude(clat);
+ int clonEnc = GeoEncodingUtils.encodeLongitude(clon);
+ byte[] b = new byte[7 * LatLonShape.BYTES];
+ LatLonShape.encodeTriangle(b, alatEnc, alonEnc, blatEnc, blonEnc, clatEnc, clonEnc);
+ int[] encoded = new int[6];
+ LatLonShape.decodeTriangle(b, encoded);
+ assertTrue(encoded[0] == blatEnc);
+ assertTrue(encoded[1] == blonEnc);
+ assertTrue(encoded[2] == clatEnc);
+ assertTrue(encoded[3] == clonEnc);
+ assertTrue(encoded[4] == alatEnc);
+ assertTrue(encoded[5] == alonEnc);
+ }
+
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/d185ba99/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
index 2714936..01a50e9 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/geo/TestRectangle2D.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/geo/TestRectangle2D.java
@@ -20,6 +20,7 @@ package org.apache.lucene.geo;
import org.apache.lucene.document.LatLonShape;
import org.apache.lucene.index.PointValues;
import org.apache.lucene.util.LuceneTestCase;
+import org.apache.lucene.util.NumericUtils;
import static org.apache.lucene.document.LatLonShape.BYTES;
@@ -82,10 +83,10 @@ public class TestRectangle2D extends LuceneTestCase {
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);
+ NumericUtils.intToSortableBytes(tMinY, triangle, 0);
+ NumericUtils.intToSortableBytes(tMinX, triangle, BYTES);
+ NumericUtils.intToSortableBytes(tMaxY, triangle, 2 * BYTES);
+ NumericUtils.intToSortableBytes(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) {