lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From iv...@apache.org
Subject lucene-solr:branch_7x: LUCENE-8581: Change LatLonShape encoding to use 4 bytes Per Dimension
Date Tue, 18 Dec 2018 15:53:57 GMT
Repository: lucene-solr
Updated Branches:
  refs/heads/branch_7x 462adbc7f -> 84fcfae3d


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/84fcfae3
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/84fcfae3
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/84fcfae3

Branch: refs/heads/branch_7x
Commit: 84fcfae3dc501e9fb1c777565aab0f9ca30cba18
Parents: 462adbc
Author: iverase <ivera@apache.org>
Authored: Tue Dec 18 16:53:14 2018 +0100
Committer: iverase <ivera@apache.org>
Committed: Tue Dec 18 16:53:14 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/84fcfae3/lucene/CHANGES.txt
----------------------------------------------------------------------
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index fe14ed1..2636b4e 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -45,6 +45,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/84fcfae3/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/84fcfae3/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/84fcfae3/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/84fcfae3/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/84fcfae3/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 87212c1..e85b1cd 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeQuery.java
@@ -72,7 +72,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) {
@@ -92,6 +92,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
@@ -106,7 +107,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);
             }
           }
@@ -121,7 +122,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) {
@@ -135,7 +136,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/84fcfae3/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/84fcfae3/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/84fcfae3/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 4c505b2..737e5f3 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/BaseLatLonShapeTestCase.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/BaseLatLonShapeTestCase.java
@@ -93,26 +93,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/84fcfae3/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/84fcfae3/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/84fcfae3/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/84fcfae3/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) {


Mime
View raw message