You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by nk...@apache.org on 2018/10/18 18:30:36 UTC
lucene-solr:master: LUCENE-8521: Change LatLonShape encoding to use
selective indexing
Repository: lucene-solr
Updated Branches:
refs/heads/master 947f82679 -> ed8a39594
LUCENE-8521: Change LatLonShape encoding to use selective indexing
This improvement changes LatLonShape encoding to 7 dimensions instead of 6. The first 4 are index dimensions defining the bounding box of the Triangle and the remaining 3 data dimensions define the vertices of the triangle.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/ed8a3959
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/ed8a3959
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/ed8a3959
Branch: refs/heads/master
Commit: ed8a395948f406aca7ac55fd3bd0f5348af353c3
Parents: 947f826
Author: Nicholas Knize <nk...@gmail.com>
Authored: Thu Oct 18 12:13:04 2018 -0500
Committer: Nicholas Knize <nk...@gmail.com>
Committed: Thu Oct 18 13:30:18 2018 -0500
----------------------------------------------------------------------
lucene/CHANGES.txt | 6 ++
.../org/apache/lucene/document/LatLonShape.java | 83 +++++++++++++-------
.../document/LatLonShapeBoundingBoxQuery.java | 75 +++++++++---------
.../document/LatLonShapePolygonQuery.java | 38 ++++++---
.../lucene/document/LatLonShapeQuery.java | 37 +--------
.../java/org/apache/lucene/geo/Tessellator.java | 41 +++-------
6 files changed, 134 insertions(+), 146 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/ed8a3959/lucene/CHANGES.txt
----------------------------------------------------------------------
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 82108a1..3ec6de3 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -210,6 +210,12 @@ New Features
may be used to determine how to split the inner nodes, and dimensions N+1 to D
are ignored and stored as data dimensions at the leaves. (Nick Knize)
+Improvements:
+
+* LUCENE-8521: Change LatLonShape encoding to 7 dimensions instead of 6; where the
+ first 4 are index dimensions defining the bounding box of the Triangle and the
+ remaining 3 data dimensions define the vertices of the triangle. (Nick Knize)
+
Other:
* LUCENE-8523: Correct typo in JapaneseNumberFilterFactory javadocs (Ankush Jhalani
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/ed8a3959/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 3ac171f9..1d17b10 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShape.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShape.java
@@ -54,11 +54,11 @@ import static org.apache.lucene.geo.GeoEncodingUtils.encodeLongitude;
* @lucene.experimental
*/
public class LatLonShape {
- public static final int BYTES = LatLonPoint.BYTES;
+ public static final int BYTES = 2 * LatLonPoint.BYTES;
protected static final FieldType TYPE = new FieldType();
static {
- TYPE.setDimensions(6, BYTES);
+ TYPE.setDimensions(7, 4, BYTES);
TYPE.freeze();
}
@@ -72,8 +72,7 @@ public class LatLonShape {
List<Triangle> tessellation = Tessellator.tessellate(polygon);
List<LatLonTriangle> fields = new ArrayList<>();
for (Triangle t : tessellation) {
- fields.add(new LatLonTriangle(fieldName, t.getEncodedX(0), t.getEncodedY(0),
- t.getEncodedX(1), t.getEncodedY(1), t.getEncodedX(2), t.getEncodedY(2)));
+ fields.add(new LatLonTriangle(fieldName, t));
}
return fields.toArray(new Field[fields.size()]);
}
@@ -83,21 +82,14 @@ public class LatLonShape {
int numPoints = line.numPoints();
List<LatLonTriangle> fields = new ArrayList<>(numPoints - 1);
- // encode the line vertices
- int[] encodedLats = new int[numPoints];
- int[] encodedLons = new int[numPoints];
- for (int i = 0; i < numPoints; ++i) {
- encodedLats[i] = encodeLatitude(line.getLat(i));
- encodedLons[i] = encodeLongitude(line.getLon(i));
- }
-
// create "flat" triangles
- int aLat, bLat, aLon, bLon, temp;
+ double aLat, bLat, aLon, bLon, temp;
+ double size;
for (int i = 0, j = 1; j < numPoints; ++i, ++j) {
- aLat = encodedLats[i];
- aLon = encodedLons[i];
- bLat = encodedLats[j];
- bLon = encodedLons[j];
+ aLat = line.getLat(i);
+ aLon = line.getLon(i);
+ bLat = line.getLat(j);
+ bLon = line.getLon(j);
if (aLat > bLat) {
temp = aLat;
aLat = bLat;
@@ -115,16 +107,15 @@ public class LatLonShape {
bLon = temp;
}
}
- fields.add(new LatLonTriangle(fieldName, aLon, aLat, bLon, bLat, aLon, aLat));
+ size = StrictMath.sqrt(StrictMath.pow(aLat - bLat, 2d) + StrictMath.pow(aLon - bLon, 2d));
+ fields.add(new LatLonTriangle(fieldName, aLat, aLon, bLat, bLon, aLat, aLon, size));
}
return fields.toArray(new Field[fields.size()]);
}
/** create indexable fields for point geometry */
public static Field[] createIndexableFields(String fieldName, double lat, double lon) {
- final int encodedLat = encodeLatitude(lat);
- final int encodedLon = encodeLongitude(lon);
- return new Field[] {new LatLonTriangle(fieldName, encodedLon, encodedLat, encodedLon, encodedLat, encodedLon, encodedLat)};
+ return new Field[] {new LatLonTriangle(fieldName, lat, lon, lat, lon, lat, lon, 0d)};
}
/** create a query to find all polygons that intersect a defined bounding box
@@ -144,28 +135,60 @@ public class LatLonShape {
*/
private static class LatLonTriangle extends Field {
- LatLonTriangle(String name, int ax, int ay, int bx, int by, int cx, int cy) {
+ LatLonTriangle(String name, double aLat, double aLon, double bLat, double bLon, double cLat, double cLon, double size) {
+ super(name, TYPE);
+ setTriangleValue(encodeLongitude(aLon), encodeLatitude(aLat), encodeLongitude(bLon), encodeLatitude(bLat), encodeLongitude(cLon), encodeLatitude(cLat));
+ }
+
+ LatLonTriangle(String name, Triangle t) {
super(name, TYPE);
- setTriangleValue(ax, ay, bx, by, cx, cy);
+ 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;
if (fieldsData == null) {
- bytes = new byte[24];
+ bytes = new byte[7 * BYTES];
fieldsData = new BytesRef(bytes);
} else {
bytes = ((BytesRef) fieldsData).bytes;
}
- NumericUtils.intToSortableBytes(aY, bytes, 0);
- NumericUtils.intToSortableBytes(aX, bytes, BYTES);
- NumericUtils.intToSortableBytes(bY, bytes, BYTES * 2);
- NumericUtils.intToSortableBytes(bX, bytes, BYTES * 3);
- NumericUtils.intToSortableBytes(cY, bytes, BYTES * 4);
- NumericUtils.intToSortableBytes(cX, bytes, BYTES * 5);
+ 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);
}
+
+ 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);
+ }
+ }
+
+ 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 int decodeTriangleBoxVal(byte[] encoded, int offset) {
+ long val = NumericUtils.sortableBytesToLong(encoded, offset);
+ int result = (int)(val & 0x00000000FFFFFFFF);
+ return result ^ 0x80000000;
}
/** Query Relation Types **/
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/ed8a3959/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 e797043..cb8f9a1 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java
@@ -24,6 +24,7 @@ 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.decodeLatitude;
import static org.apache.lucene.geo.GeoEncodingUtils.decodeLongitude;
import static org.apache.lucene.geo.GeoEncodingUtils.encodeLatitude;
@@ -52,32 +53,32 @@ final class LatLonShapeBoundingBoxQuery extends LatLonShapeQuery {
if (minLon > maxLon) {
throw new IllegalArgumentException("dateline crossing bounding box queries are not supported for [" + field + "]");
}
- this.bbox = new byte[4 * LatLonPoint.BYTES];
+ this.bbox = new byte[4 * LatLonShape.BYTES];
this.minX = encodeLongitudeCeil(minLon);
this.maxX = encodeLongitude(maxLon);
this.minY = encodeLatitudeCeil(minLat);
this.maxY = encodeLatitude(maxLat);
- NumericUtils.intToSortableBytes(this.minY, this.bbox, 0);
- NumericUtils.intToSortableBytes(this.minX, this.bbox, LatLonPoint.BYTES);
- NumericUtils.intToSortableBytes(this.maxY, this.bbox, 2 * LatLonPoint.BYTES);
- NumericUtils.intToSortableBytes(this.maxX, this.bbox, 3 * LatLonPoint.BYTES);
+ LatLonShape.encodeTriangleBoxVal(this.minY, bbox, 0);
+ LatLonShape.encodeTriangleBoxVal(this.minX, bbox, BYTES);
+ LatLonShape.encodeTriangleBoxVal(this.maxY, bbox, 2 * BYTES);
+ LatLonShape.encodeTriangleBoxVal(this.maxX, bbox, 3 * BYTES);
}
@Override
protected Relation relateRangeBBoxToQuery(int minXOffset, int minYOffset, byte[] minTriangle,
int maxXOffset, int maxYOffset, byte[] maxTriangle) {
// check bounding box (DISJOINT)
- if (FutureArrays.compareUnsigned(minTriangle, minXOffset, minXOffset + LatLonPoint.BYTES, bbox, 3 * LatLonPoint.BYTES, 4 * LatLonPoint.BYTES) > 0 ||
- FutureArrays.compareUnsigned(maxTriangle, maxXOffset, maxXOffset + LatLonPoint.BYTES, bbox, LatLonPoint.BYTES, 2 * LatLonPoint.BYTES) < 0 ||
- FutureArrays.compareUnsigned(minTriangle, minYOffset, minYOffset + LatLonPoint.BYTES, bbox, 2 * LatLonPoint.BYTES, 3 * LatLonPoint.BYTES) > 0 ||
- FutureArrays.compareUnsigned(maxTriangle, maxYOffset, maxYOffset + LatLonPoint.BYTES, bbox, 0, LatLonPoint.BYTES) < 0) {
+ 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 + LatLonPoint.BYTES, bbox, LatLonPoint.BYTES, 2 * LatLonPoint.BYTES) > 0 &&
- FutureArrays.compareUnsigned(maxTriangle, maxXOffset, maxXOffset + LatLonPoint.BYTES, bbox, 3 * LatLonPoint.BYTES, 4 * LatLonPoint.BYTES) < 0 &&
- FutureArrays.compareUnsigned(minTriangle, minYOffset, minYOffset + LatLonPoint.BYTES, bbox, 0, LatLonPoint.BYTES) > 0 &&
- FutureArrays.compareUnsigned(maxTriangle, maxYOffset, maxYOffset + LatLonPoint.BYTES, bbox, 2 * LatLonPoint.BYTES, 2 * LatLonPoint.BYTES) < 0) {
+ 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;
@@ -86,27 +87,37 @@ final class LatLonShapeBoundingBoxQuery extends LatLonShapeQuery {
/** returns true if the query matches the encoded triangle */
@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);
+
if (queryRelation == LatLonShape.QueryRelation.WITHIN) {
- return queryContains(t, 0) && queryContains(t, 1) && queryContains(t, 2);
+ return queryContains(aX, aY) && queryContains(bX, bY) && queryContains(cX, cY);
}
- return queryIntersects(t);
+ return queryMatches(aX, aY, bX, bY, cX, cY);
+ }
+
+ private boolean queryContains(int x, int y) {
+ return (x < minX || x > maxX || y < minY || y > maxY) == false;
}
- /** returns true if the query intersects the encoded triangle */
- protected boolean queryIntersects(byte[] t) {
+ private boolean queryContains(int ax, int ay, int bx, int by, int cx, int cy) {
+ return queryContains(ax, ay) || queryContains(bx, by) || queryContains(cx, cy);
+ }
+ protected boolean queryMatches(int aX, int aY, int bX, int bY, int cX, int cY) {
// 1. query contains any triangle points
- if (queryContains(t, 0) || queryContains(t, 1) || queryContains(t, 2)) {
+ if (queryContains(aX, aY, bX, bY, cX, cY)) {
return true;
}
- int aY = NumericUtils.sortableBytesToInt(t, 0);
- int aX = NumericUtils.sortableBytesToInt(t, LatLonPoint.BYTES);
- int bY = NumericUtils.sortableBytesToInt(t, 2 * LatLonPoint.BYTES);
- int bX = NumericUtils.sortableBytesToInt(t, 3 * LatLonPoint.BYTES);
- int cY = NumericUtils.sortableBytesToInt(t, 4 * LatLonPoint.BYTES);
- int cX = NumericUtils.sortableBytesToInt(t, 5 * LatLonPoint.BYTES);
-
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);
@@ -164,20 +175,6 @@ final class LatLonShapeBoundingBoxQuery extends LatLonShapeQuery {
return false;
}
- /** returns true if the query contains the triangle vertex */
- private boolean queryContains(byte[] t, int point) {
- final int yIdx = 2 * LatLonPoint.BYTES * point;
- final int xIdx = yIdx + LatLonPoint.BYTES;
-
- if (FutureArrays.compareUnsigned(t, yIdx, xIdx, bbox, 0, LatLonPoint.BYTES) < 0 || //minY
- FutureArrays.compareUnsigned(t, yIdx, xIdx, bbox, 2 * LatLonPoint.BYTES, 3 * LatLonPoint.BYTES) > 0 || //maxY
- FutureArrays.compareUnsigned(t, xIdx, xIdx + LatLonPoint.BYTES, bbox, LatLonPoint.BYTES, 2 * LatLonPoint.BYTES) < 0 || // minX
- FutureArrays.compareUnsigned(t, xIdx, xIdx + LatLonPoint.BYTES, bbox, 3 * LatLonPoint.BYTES, bbox.length) > 0) {
- return false;
- }
- return true;
- }
-
/** 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
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/ed8a3959/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 755946e..a587112 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapePolygonQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapePolygonQuery.java
@@ -23,6 +23,7 @@ import org.apache.lucene.geo.GeoEncodingUtils;
import org.apache.lucene.geo.Polygon;
import org.apache.lucene.geo.Polygon2D;
import org.apache.lucene.index.PointValues.Relation;
+import org.apache.lucene.util.NumericUtils;
/**
* Finds all previously indexed shapes that intersect the specified arbitrary.
@@ -61,29 +62,40 @@ 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(minTriangle, minYOffset);
- double minLon = GeoEncodingUtils.decodeLongitude(minTriangle, minXOffset);
- double maxLat = GeoEncodingUtils.decodeLatitude(maxTriangle, maxYOffset);
- double maxLon = GeoEncodingUtils.decodeLongitude(maxTriangle, maxXOffset);
+ 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));
// check internal node against query
return poly2D.relate(minLat, maxLat, minLon, maxLon);
}
@Override
- protected boolean queryMatches(byte[] triangle) {
- double ay = GeoEncodingUtils.decodeLatitude(triangle, 0);
- double ax = GeoEncodingUtils.decodeLongitude(triangle, LatLonPoint.BYTES);
- double by = GeoEncodingUtils.decodeLatitude(triangle, 2 * LatLonPoint.BYTES);
- double bx = GeoEncodingUtils.decodeLongitude(triangle, 3 * LatLonPoint.BYTES);
- double cy = GeoEncodingUtils.decodeLatitude(triangle, 4 * LatLonPoint.BYTES);
- double cx = GeoEncodingUtils.decodeLongitude(triangle, 5 * LatLonPoint.BYTES);
+ 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);
+
+ 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);
if (queryRelation == QueryRelation.WITHIN) {
- return poly2D.relateTriangle(ax, ay, bx, by, cx, cy) == Relation.CELL_INSIDE_QUERY;
+ return poly2D.relateTriangle(alon, alat, blon, blat, clon, clat) == Relation.CELL_INSIDE_QUERY;
}
// INTERSECTS
- return poly2D.relateTriangle(ax, ay, bx, by, cx, cy) != Relation.CELL_OUTSIDE_QUERY;
+ return poly2D.relateTriangle(alon, alat, blon, blat, clon, clat) != Relation.CELL_OUTSIDE_QUERY;
}
@Override
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/ed8a3959/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 c678941..be6b758 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeQuery.java
@@ -38,7 +38,6 @@ import org.apache.lucene.search.Weight;
import org.apache.lucene.util.BitSetIterator;
import org.apache.lucene.util.DocIdSetBuilder;
import org.apache.lucene.util.FixedBitSet;
-import org.apache.lucene.util.FutureArrays;
/**
* Base LatLonShape Query class providing common query logic for
@@ -79,41 +78,7 @@ abstract class LatLonShapeQuery extends Query {
/** relates a range of triangles (internal node) to the query */
protected Relation relateRangeToQuery(byte[] minTriangle, byte[] maxTriangle) {
// compute bounding box of internal node
- int minXOfs = 0;
- int minYOfs = 0;
- int maxXOfs = 0;
- int maxYOfs = 0;
- for (int d = 1; d < 3; ++d) {
- // check minX
- int aOfs = (minXOfs * 2 * LatLonPoint.BYTES) + LatLonPoint.BYTES;
- int bOfs = (d * 2 * LatLonPoint.BYTES) + LatLonPoint.BYTES;
- if (FutureArrays.compareUnsigned(minTriangle, bOfs, bOfs + LatLonPoint.BYTES, minTriangle, aOfs, aOfs + LatLonPoint.BYTES) < 0) {
- minXOfs = d;
- }
- // check maxX
- aOfs = (maxXOfs * 2 * LatLonPoint.BYTES) + LatLonPoint.BYTES;
- if (FutureArrays.compareUnsigned(maxTriangle, bOfs, bOfs + LatLonPoint.BYTES, maxTriangle, aOfs, aOfs + LatLonPoint.BYTES) > 0) {
- maxXOfs = d;
- }
- // check minY
- aOfs = minYOfs * 2 * LatLonPoint.BYTES;
- bOfs = d * 2 * LatLonPoint.BYTES;
- if (FutureArrays.compareUnsigned(minTriangle, bOfs, bOfs + LatLonPoint.BYTES, minTriangle, aOfs, aOfs + LatLonPoint.BYTES) < 0) {
- minYOfs = d;
- }
- // check maxY
- aOfs = maxYOfs * 2 * LatLonPoint.BYTES;
- if (FutureArrays.compareUnsigned(maxTriangle, bOfs, bOfs + LatLonPoint.BYTES, maxTriangle, aOfs, aOfs + LatLonPoint.BYTES) > 0) {
- maxYOfs = d;
- }
- }
- minXOfs = (minXOfs * 2 * LatLonPoint.BYTES) + LatLonPoint.BYTES;
- maxXOfs = (maxXOfs * 2 * LatLonPoint.BYTES) + LatLonPoint.BYTES;
- minYOfs *= 2 * LatLonPoint.BYTES;
- maxYOfs *= 2 * LatLonPoint.BYTES;
-
- Relation r = relateRangeBBoxToQuery(minXOfs, minYOfs, minTriangle, maxXOfs, maxYOfs, maxTriangle);
-
+ Relation r = relateRangeBBoxToQuery(LatLonShape.BYTES, 0, minTriangle, 3 * LatLonShape.BYTES, 2 * LatLonShape.BYTES, maxTriangle);
if (queryRelation == QueryRelation.DISJOINT) {
return transposeRelation(r);
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/ed8a3959/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 9a63ad2..c68a9df 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
@@ -17,6 +17,7 @@
package org.apache.lucene.geo;
import java.util.ArrayList;
+import java.util.Arrays;
import java.util.List;
import org.apache.lucene.geo.GeoUtils.WindingOrder;
@@ -819,13 +820,17 @@ final public class Tessellator {
}
/** compare nodes by y then x */
- public int compare(Node other) {
- if (this.getLat() > other.getLat()) {
+ 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 (this.getLat() == other.getLat()) {
- if (this.getLon() > other.getLon()) {
+ } else if (aX == bX) {
+ if (aY > bY) {
return 1;
- } else if (this.getLon() == other.getLon()) {
+ } else if (aY == bY) {
return 0;
}
}
@@ -850,32 +855,12 @@ final public class Tessellator {
/** Triangle in the tessellated mesh */
public final static class Triangle {
- Node[] vertex = new Node[3];
+ Node[] vertex;
protected Triangle(Node a, Node b, Node c) {
+ this.vertex = new Node[] {a, b, c};
// sort nodes by morton value
- Node tA = a;
- Node tB = b;
- Node tC = c;
- Node temp;
- if (a.compare(b) > 0) {
- temp = tA;
- tA = tB;
- tB = temp;
- }
- if (b.compare(c) > 0) {
- temp = tB;
- tB = tC;
- tC = temp;
- }
- if (a.compare(b) > 0) {
- temp = tA;
- tA = tB;
- tB = temp;
- }
- this.vertex[0] = tA;
- this.vertex[1] = tB;
- this.vertex[2] = tC;
+ Arrays.sort(this.vertex, (x, y) -> x.compareLat(y));
}
/** get quantized x value for the given vertex */