lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ctarg...@apache.org
Subject [38/50] [abbrv] lucene-solr:jira/solr-12746: LUCENE-8521: Change LatLonShape encoding to use selective indexing
Date Mon, 22 Oct 2018 23:35:23 GMT
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/02a65ac6
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/02a65ac6
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/02a65ac6

Branch: refs/heads/jira/solr-12746
Commit: 02a65ac6861a48e9400c68997b4ca126c2c01161
Parents: 802f59e
Author: Nicholas Knize <nknize@gmail.com>
Authored: Thu Oct 18 12:13:04 2018 -0500
Committer: Cassandra Targett <ctargett@apache.org>
Committed: Sun Oct 21 15:46:48 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/02a65ac6/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/02a65ac6/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/02a65ac6/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/02a65ac6/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/02a65ac6/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/02a65ac6/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 */


Mime
View raw message