lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From nkn...@apache.org
Subject [1/5] lucene-solr git commit: LUCENE-6930: Decouples GeoPointField from NumericType by using a custom GeoPointTokenStream and TermEnum designed for GeoPoint prefix terms
Date Sun, 07 Feb 2016 04:27:24 GMT
Repository: lucene-solr
Updated Branches:
  refs/heads/branch_5x aacda06b8 -> cc052491c


http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/74a08c08/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointTermsEnum.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointTermsEnum.java
b/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointTermsEnum.java
index 2dd6cb4..626003a 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointTermsEnum.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/search/GeoPointTermsEnum.java
@@ -16,173 +16,60 @@
  */
 package org.apache.lucene.spatial.search;
 
-import java.util.Collections;
-import java.util.LinkedList;
-import java.util.List;
-
-import org.apache.lucene.spatial.document.GeoPointField;
 import org.apache.lucene.index.FilteredTermsEnum;
 import org.apache.lucene.index.TermsEnum;
 import org.apache.lucene.util.BytesRef;
 import org.apache.lucene.util.BytesRefBuilder;
-import org.apache.lucene.util.NumericUtils;
-import org.apache.lucene.spatial.util.GeoRelationUtils;
-import org.apache.lucene.spatial.util.GeoUtils;
+import org.apache.lucene.spatial.document.GeoPointField.TermEncoding;
+import org.apache.lucene.spatial.search.GeoPointMultiTermQuery.CellComparator;
 
 /**
- * computes all ranges along a space-filling curve that represents
- * the given bounding box and enumerates all terms contained within those ranges
+ * Base class for {@link GeoPointNumericTermsEnum} and {@link GeoPointPrefixTermsEnum} which
compares
+ * candidate GeoPointField encoded terms against terms matching the defined query criteria.
  *
  *  @lucene.experimental
  */
 abstract class GeoPointTermsEnum extends FilteredTermsEnum {
-  protected final double minLon;
-  protected final double minLat;
-  protected final double maxLon;
-  protected final double maxLat;
-
-  protected Range currentRange;
-  private final BytesRefBuilder currentCell = new BytesRefBuilder();
-  private final BytesRefBuilder nextSubRange = new BytesRefBuilder();
+  protected final short maxShift;
 
-  private final List<Range> rangeBounds = new LinkedList<>();
+  protected BaseRange currentRange;
+  protected BytesRef currentCell;
+  protected final BytesRefBuilder currentCellBRB = new BytesRefBuilder();
+  protected final BytesRefBuilder nextSubRangeBRB = new BytesRefBuilder();
 
-  // detail level should be a factor of PRECISION_STEP limiting the depth of recursion (and
number of ranges)
-  protected final short DETAIL_LEVEL;
+  protected final CellComparator relationImpl;
 
-  GeoPointTermsEnum(final TermsEnum tenum, final double minLon, final double minLat,
-                    final double maxLon, final double maxLat) {
+  GeoPointTermsEnum(final TermsEnum tenum, final GeoPointMultiTermQuery query) {
     super(tenum);
-    final long rectMinHash = GeoUtils.mortonHash(minLon, minLat);
-    final long rectMaxHash = GeoUtils.mortonHash(maxLon, maxLat);
-    this.minLon = GeoUtils.mortonUnhashLon(rectMinHash);
-    this.minLat = GeoUtils.mortonUnhashLat(rectMinHash);
-    this.maxLon = GeoUtils.mortonUnhashLon(rectMaxHash);
-    this.maxLat = GeoUtils.mortonUnhashLat(rectMaxHash);
-    DETAIL_LEVEL = (short)(((GeoUtils.BITS<<1)-computeMaxShift())/2);
-
-    computeRange(0L, (short) ((GeoUtils.BITS << 1) - 1));
-    assert rangeBounds.isEmpty() == false;
-    Collections.sort(rangeBounds);
-  }
-
-  /**
-   * entry point for recursively computing ranges
-   */
-  private final void computeRange(long term, final short shift) {
-    final long split = term | (0x1L<<shift);
-    assert shift < 64;
-    final long upperMax;
-    if (shift < 63) {
-      upperMax = term | ((1L << (shift+1))-1);
-    } else {
-      upperMax = 0xffffffffffffffffL;
-    }
-    final long lowerMax = split-1;
-
-    relateAndRecurse(term, lowerMax, shift);
-    relateAndRecurse(split, upperMax, shift);
+    this.maxShift = query.maxShift;
+    this.relationImpl = query.cellComparator;
   }
 
-  /**
-   * recurse to higher level precision cells to find ranges along the space-filling curve
that fall within the
-   * query box
-   *
-   * @param start starting value on the space-filling curve for a cell at a given res
-   * @param end ending value on the space-filling curve for a cell at a given res
-   * @param res spatial res represented as a bit shift (MSB is lower res)
-   */
-  private void relateAndRecurse(final long start, final long end, final short res) {
-    final double minLon = GeoUtils.mortonUnhashLon(start);
-    final double minLat = GeoUtils.mortonUnhashLat(start);
-    final double maxLon = GeoUtils.mortonUnhashLon(end);
-    final double maxLat = GeoUtils.mortonUnhashLat(end);
-
-    final short level = (short)((GeoUtils.BITS<<1)-res>>>1);
-
-    // if cell is within and a factor of the precision step, or it crosses the edge of the
shape add the range
-    final boolean within = res % GeoPointField.PRECISION_STEP == 0 && cellWithin(minLon,
minLat, maxLon, maxLat);
-    if (within || (level == DETAIL_LEVEL && cellIntersectsShape(minLon, minLat, maxLon,
maxLat))) {
-      final short nextRes = (short)(res-1);
-      if (nextRes % GeoPointField.PRECISION_STEP == 0) {
-        rangeBounds.add(new Range(start, nextRes, !within));
-        rangeBounds.add(new Range(start|(1L<<nextRes), nextRes, !within));
-      } else {
-        rangeBounds.add(new Range(start, res, !within));
-      }
-    } else if (level < DETAIL_LEVEL && cellIntersectsMBR(minLon, minLat, maxLon,
maxLat)) {
-      computeRange(start, (short) (res - 1));
+  static GeoPointTermsEnum newInstance(final TermsEnum terms, final GeoPointMultiTermQuery
query) {
+    if (query.termEncoding == TermEncoding.PREFIX) {
+      return new GeoPointPrefixTermsEnum(terms, query);
+    } else if (query.termEncoding == TermEncoding.NUMERIC) {
+      return new GeoPointNumericTermsEnum(terms, query);
     }
-  }
-
-  protected short computeMaxShift() {
-    // in this case a factor of 4 brings the detail level to ~0.002/0.001 degrees lon/lat
respectively (or ~222m/111m)
-    return GeoPointField.PRECISION_STEP * 4;
-  }
-
-  /**
-   * Determine whether the quad-cell crosses the shape
-   */
-  protected abstract boolean cellCrosses(final double minLon, final double minLat, final
double maxLon, final double maxLat);
-
-  /**
-   * Determine whether quad-cell is within the shape
-   */
-  protected abstract boolean cellWithin(final double minLon, final double minLat, final double
maxLon, final double maxLat);
-
-  /**
-   * Default shape is a rectangle, so this returns the same as {@code cellIntersectsMBR}
-   */
-  protected abstract boolean cellIntersectsShape(final double minLon, final double minLat,
final double maxLon, final double maxLat);
-
-  /**
-   * Primary driver for cells intersecting shape boundaries
-   */
-  protected boolean cellIntersectsMBR(final double minLon, final double minLat, final double
maxLon, final double maxLat) {
-    return GeoRelationUtils.rectIntersects(minLon, minLat, maxLon, maxLat, this.minLon, this.minLat,
this.maxLon, this.maxLat);
-  }
-
-  /**
-   * Return whether quad-cell contains the bounding box of this shape
-   */
-  protected boolean cellContains(final double minLon, final double minLat, final double maxLon,
final double maxLat) {
-    return GeoRelationUtils.rectWithin(this.minLon, this.minLat, this.maxLon, this.maxLat,
minLon, minLat, maxLon, maxLat);
+    throw new IllegalArgumentException("Invalid GeoPoint TermEncoding " + query.termEncoding);
   }
 
   public boolean boundaryTerm() {
-    if (currentRange == null) {
+    if (currentCell == null) {
       throw new IllegalStateException("GeoPointTermsEnum empty or not initialized");
     }
     return currentRange.boundary;
   }
 
-  private void nextRange() {
-    currentRange = rangeBounds.remove(0);
-    currentRange.fillBytesRef(currentCell);
+  protected BytesRef peek() {
+    return nextSubRangeBRB.get();
   }
 
-  @Override
-  protected final BytesRef nextSeekTerm(BytesRef term) {
-    while (!rangeBounds.isEmpty()) {
-      if (currentRange == null) {
-        nextRange();
-      }
-
-      // if the new upper bound is before the term parameter, the sub-range is never a hit
-      if (term != null && term.compareTo(currentCell.get()) > 0) {
-        nextRange();
-        if (!rangeBounds.isEmpty()) {
-          continue;
-        }
-      }
-      // never seek backwards, so use current term if lower bound is smaller
-      return (term != null && term.compareTo(currentCell.get()) > 0) ?
-          term : currentCell.get();
-    }
+  abstract protected boolean hasNext();
 
-    // no more sub-range enums available
-    assert rangeBounds.isEmpty();
-    return null;
+  protected void nextRange() {
+    currentRange.fillBytesRef(currentCellBRB);
+    currentCell = currentCellBRB.get();
   }
 
   /**
@@ -196,13 +83,12 @@ abstract class GeoPointTermsEnum extends FilteredTermsEnum {
   @Override
   protected AcceptStatus accept(BytesRef term) {
     // validate value is in range
-    while (currentCell == null || term.compareTo(currentCell.get()) > 0) {
-      if (rangeBounds.isEmpty()) {
+    while (currentCell == null || term.compareTo(currentCell) > 0) {
+      if (hasNext() == false) {
         return AcceptStatus.END;
       }
       // peek next sub-range, only seek if the current term is smaller than next lower bound
-      rangeBounds.get(0).fillBytesRef(this.nextSubRange);
-      if (term.compareTo(this.nextSubRange.get()) < 0) {
+      if (term.compareTo(peek()) < 0) {
         return AcceptStatus.NO_AND_SEEK;
       }
       // step forward to next range without seeking, as next range is less or equal current
term
@@ -212,17 +98,19 @@ abstract class GeoPointTermsEnum extends FilteredTermsEnum {
     return AcceptStatus.YES;
   }
 
-  protected abstract boolean postFilter(final double lon, final double lat);
+  protected boolean postFilter(final double lon, final double lat) {
+    return relationImpl.postFilter(lon, lat);
+  }
 
   /**
    * Internal class to represent a range along the space filling curve
    */
-  protected final class Range implements Comparable<Range> {
-    final short shift;
-    final long start;
-    final boolean boundary;
+  abstract class BaseRange implements Comparable<BaseRange> {
+    protected short shift;
+    protected long start;
+    protected boolean boundary;
 
-    Range(final long lower, final short shift, boolean boundary) {
+    BaseRange(final long lower, final short shift, boolean boundary) {
       this.boundary = boundary;
       this.start = lower;
       this.shift = shift;
@@ -232,18 +120,21 @@ abstract class GeoPointTermsEnum extends FilteredTermsEnum {
      * Encode as a BytesRef using a reusable object. This allows us to lazily create the
BytesRef (which is
      * quite expensive), only when we need it.
      */
-    private void fillBytesRef(BytesRefBuilder result) {
-      assert result != null;
-      NumericUtils.longToPrefixCoded(start, shift, result);
-    }
+    abstract protected void fillBytesRef(BytesRefBuilder result);
 
     @Override
-    public int compareTo(Range other) {
+    public int compareTo(BaseRange other) {
       final int result = Short.compare(this.shift, other.shift);
       if (result == 0) {
         return Long.compare(this.start, other.start);
       }
       return result;
     }
+
+    protected void set(BaseRange other) {
+      this.start = other.start;
+      this.shift = other.shift;
+      this.boundary = other.boundary;
+    }
   }
 }

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/74a08c08/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoEncodingUtils.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoEncodingUtils.java
b/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoEncodingUtils.java
new file mode 100644
index 0000000..de62318
--- /dev/null
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoEncodingUtils.java
@@ -0,0 +1,157 @@
+package org.apache.lucene.spatial.util;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import org.apache.lucene.util.BitUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.BytesRefBuilder;
+
+import static org.apache.lucene.spatial.util.GeoUtils.MIN_LON_INCL;
+import static org.apache.lucene.spatial.util.GeoUtils.MIN_LAT_INCL;
+
+/**
+ * Basic reusable geopoint encoding methods
+ *
+ * @lucene.experimental
+ */
+public final class GeoEncodingUtils {
+  /** number of bits used for quantizing latitude and longitude values */
+  public static final short BITS = 31;
+  private static final double LON_SCALE = (0x1L<<BITS)/360.0D;
+  private static final double LAT_SCALE = (0x1L<<BITS)/180.0D;
+
+  /**
+   * The maximum term length (used for <code>byte[]</code> buffer size)
+   * for encoding <code>geoEncoded</code> values.
+   * @see #geoCodedToPrefixCodedBytes(long, int, BytesRefBuilder)
+   */
+  public static final int BUF_SIZE_LONG = 28/8 + 1;
+
+  /** rounding error for quantized latitude and longitude values */
+  public static final double TOLERANCE = 1E-6;
+
+  // No instance:
+  private GeoEncodingUtils() {
+  }
+
+  public static final Long mortonHash(final double lon, final double lat) {
+    return BitUtil.interleave(scaleLon(lon), scaleLat(lat));
+  }
+
+  public static final double mortonUnhashLon(final long hash) {
+    return unscaleLon(BitUtil.deinterleave(hash));
+  }
+
+  public static final double mortonUnhashLat(final long hash) {
+    return unscaleLat(BitUtil.deinterleave(hash >>> 1));
+  }
+
+  protected static final long scaleLon(final double val) {
+    return (long) ((val-MIN_LON_INCL) * LON_SCALE);
+  }
+
+  protected static final long scaleLat(final double val) {
+    return (long) ((val-MIN_LAT_INCL) * LAT_SCALE);
+  }
+
+  protected static final double unscaleLon(final long val) {
+    return (val / LON_SCALE) + MIN_LON_INCL;
+  }
+
+  protected static final double unscaleLat(final long val) {
+    return (val / LAT_SCALE) + MIN_LAT_INCL;
+  }
+
+  /**
+   * Compare two position values within a {@link GeoEncodingUtils#TOLERANCE} factor
+   */
+  public static double compare(final double v1, final double v2) {
+    final double delta = v1-v2;
+    return Math.abs(delta) <= TOLERANCE ? 0 : delta;
+  }
+
+  /**
+   * Convert a geocoded morton long into a prefix coded geo term
+   */
+  public static void geoCodedToPrefixCoded(long hash, int shift, BytesRefBuilder bytes) {
+    geoCodedToPrefixCodedBytes(hash, shift, bytes);
+  }
+
+  /**
+   * Convert a prefix coded geo term back into the geocoded morton long
+   */
+  public static long prefixCodedToGeoCoded(final BytesRef val) {
+    final long result = fromBytes((byte)0, (byte)0, (byte)0, (byte)0,
+        val.bytes[val.offset+0], val.bytes[val.offset+1], val.bytes[val.offset+2], val.bytes[val.offset+3]);
+    return result << 32;
+  }
+
+  /**
+   * GeoTerms are coded using 4 prefix bytes + 1 byte to record number of prefix bits
+   *
+   * example prefix at shift 54 (yields 10 significant prefix bits):
+   *  pppppppp pp000000 00000000 00000000 00001010
+   *  (byte 1) (byte 2) (byte 3) (byte 4) (sigbits)
+   */
+  private static void geoCodedToPrefixCodedBytes(final long hash, final int shift, final
BytesRefBuilder bytes) {
+    // ensure shift is 32..63
+    if (shift < 32 || shift > 63) {
+      throw new IllegalArgumentException("Illegal shift value, must be 32..63; got shift="
+ shift);
+    }
+    int nChars = BUF_SIZE_LONG + 1; // one extra for the byte that contains the number of
significant bits
+    bytes.setLength(nChars);
+    bytes.grow(nChars--);
+    final int sigBits = 64 - shift;
+    bytes.setByteAt(BUF_SIZE_LONG, (byte)(sigBits));
+    long sortableBits = hash;
+    sortableBits >>>= shift;
+    sortableBits <<= 32 - sigBits;
+    do {
+      bytes.setByteAt(--nChars, (byte)(sortableBits));
+      sortableBits >>>= 8;
+    } while (nChars > 0);
+  }
+
+  /** Get the prefix coded geo term shift value */
+  public static int getPrefixCodedShift(final BytesRef val) {
+    final int shift = val.bytes[val.offset + BUF_SIZE_LONG];
+    if (shift > 63 || shift < 0)
+      throw new NumberFormatException("Invalid shift value (" + shift + ") in prefixCoded
bytes (is encoded value really a geo point?)");
+    return shift;
+  }
+
+  /** Converts 8 bytes to a long value */
+  protected static long fromBytes(byte b1, byte b2, byte b3, byte b4, byte b5, byte b6, byte
b7, byte b8) {
+    return ((long)b1 & 255L) << 56 | ((long)b2 & 255L) << 48 | ((long)b3
& 255L) << 40
+        | ((long)b4 & 255L) << 32 | ((long)b5 & 255L) << 24 | ((long)b6
& 255L) << 16
+        | ((long)b7 & 255L) << 8 | (long)b8 & 255L;
+  }
+
+  /** Converts a long value into a bit string (useful for debugging) */
+  public static String geoTermToString(long term) {
+    StringBuilder s = new StringBuilder(64);
+    final int numberOfLeadingZeros = Long.numberOfLeadingZeros(term);
+    for (int i = 0; i < numberOfLeadingZeros; i++) {
+      s.append('0');
+    }
+    if (term != 0) {
+      s.append(Long.toBinaryString(term));
+    }
+    return s.toString();
+  }
+}

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/74a08c08/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoHashUtils.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoHashUtils.java b/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoHashUtils.java
index 9450c1e..49a7571 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoHashUtils.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoHashUtils.java
@@ -40,7 +40,7 @@ public class GeoHashUtils {
 
   /** maximum precision for geohash strings */
   public static final int PRECISION = 12;
-  private static final short MORTON_OFFSET = (GeoUtils.BITS<<1) - (PRECISION*5);
+  private static final short MORTON_OFFSET = (GeoEncodingUtils.BITS<<1) - (PRECISION*5);
 
   // No instance:
   private GeoHashUtils() {
@@ -52,7 +52,7 @@ public class GeoHashUtils {
   public static final long longEncode(final double lon, final double lat, final int level)
{
     // shift to appropriate level
     final short msf = (short)(((12 - level) * 5) + MORTON_OFFSET);
-    return ((BitUtil.flipFlop(GeoUtils.mortonHash(lon, lat)) >>> msf) << 4)
| level;
+    return ((BitUtil.flipFlop(GeoEncodingUtils.mortonHash(lon, lat)) >>> msf) <<
4) | level;
   }
 
   /**
@@ -118,7 +118,7 @@ public class GeoHashUtils {
    */
   public static final String stringEncode(final double lon, final double lat, final int level)
{
     // convert to geohashlong
-    final long ghLong = fromMorton(GeoUtils.mortonHash(lon, lat), level);
+    final long ghLong = fromMorton(GeoEncodingUtils.mortonHash(lon, lat), level);
     return stringEncode(ghLong);
 
   }
@@ -139,7 +139,7 @@ public class GeoHashUtils {
 
     StringBuilder geoHash = new StringBuilder();
     short precision = 0;
-    final short msf = (GeoUtils.BITS<<1)-5;
+    final short msf = (GeoEncodingUtils.BITS<<1)-5;
     long mask = 31L<<msf;
     do {
       geoHash.append(BASE_32[(int)((mask & hashedVal)>>>(msf-(precision*5)))]);

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/74a08c08/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoRelationUtils.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoRelationUtils.java
b/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoRelationUtils.java
index 1911720..32e30bd 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoRelationUtils.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoRelationUtils.java
@@ -174,14 +174,14 @@ public class GeoRelationUtils {
           c2 = a2*shapeX[p+1] + b2*shapeY[p+1];
           s = (1/d)*(b2*c1 - b1*c2);
           t = (1/d)*(a1*c2 - a2*c1);
-          x00 = StrictMath.min(bbox[b][0], bbox[b+1][0]) - GeoUtils.TOLERANCE;
-          x01 = StrictMath.max(bbox[b][0], bbox[b+1][0]) + GeoUtils.TOLERANCE;
-          y00 = StrictMath.min(bbox[b][1], bbox[b+1][1]) - GeoUtils.TOLERANCE;
-          y01 = StrictMath.max(bbox[b][1], bbox[b+1][1]) + GeoUtils.TOLERANCE;
-          x10 = StrictMath.min(shapeX[p], shapeX[p+1]) - GeoUtils.TOLERANCE;
-          x11 = StrictMath.max(shapeX[p], shapeX[p+1]) + GeoUtils.TOLERANCE;
-          y10 = StrictMath.min(shapeY[p], shapeY[p+1]) - GeoUtils.TOLERANCE;
-          y11 = StrictMath.max(shapeY[p], shapeY[p+1]) + GeoUtils.TOLERANCE;
+          x00 = StrictMath.min(bbox[b][0], bbox[b+1][0]) - GeoEncodingUtils.TOLERANCE;
+          x01 = StrictMath.max(bbox[b][0], bbox[b+1][0]) + GeoEncodingUtils.TOLERANCE;
+          y00 = StrictMath.min(bbox[b][1], bbox[b+1][1]) - GeoEncodingUtils.TOLERANCE;
+          y01 = StrictMath.max(bbox[b][1], bbox[b+1][1]) + GeoEncodingUtils.TOLERANCE;
+          x10 = StrictMath.min(shapeX[p], shapeX[p+1]) - GeoEncodingUtils.TOLERANCE;
+          x11 = StrictMath.max(shapeX[p], shapeX[p+1]) + GeoEncodingUtils.TOLERANCE;
+          y10 = StrictMath.min(shapeY[p], shapeY[p+1]) - GeoEncodingUtils.TOLERANCE;
+          y11 = StrictMath.max(shapeY[p], shapeY[p+1]) + GeoEncodingUtils.TOLERANCE;
           // check whether the intersection point is touching one of the line segments
           boolean touching = ((x00 == s && y00 == t) || (x01 == s && y01
== t))
               || ((x10 == s && y10 == t) || (x11 == s && y11 == t));

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/74a08c08/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoUtils.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoUtils.java b/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoUtils.java
index 8899170..5becef7 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoUtils.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoUtils.java
@@ -18,8 +18,6 @@ package org.apache.lucene.spatial.util;
 
 import java.util.ArrayList;
 
-import org.apache.lucene.util.BitUtil;
-
 import static java.lang.Math.max;
 import static java.lang.Math.min;
 import static java.lang.Math.PI;
@@ -30,6 +28,7 @@ import static org.apache.lucene.util.SloppyMath.cos;
 import static org.apache.lucene.util.SloppyMath.sin;
 import static org.apache.lucene.util.SloppyMath.TO_DEGREES;
 import static org.apache.lucene.util.SloppyMath.TO_RADIANS;
+import static org.apache.lucene.spatial.util.GeoEncodingUtils.TOLERANCE;
 import static org.apache.lucene.spatial.util.GeoProjectionUtils.MAX_LAT_RADIANS;
 import static org.apache.lucene.spatial.util.GeoProjectionUtils.MAX_LON_RADIANS;
 import static org.apache.lucene.spatial.util.GeoProjectionUtils.MIN_LAT_RADIANS;
@@ -43,13 +42,6 @@ import static org.apache.lucene.spatial.util.GeoProjectionUtils.SEMIMAJOR_AXIS;
  * @lucene.experimental
  */
 public final class GeoUtils {
-  /** number of bits used for quantizing latitude and longitude values */
-  public static final short BITS = 31;
-  private static final double LON_SCALE = (0x1L<<BITS)/360.0D;
-  private static final double LAT_SCALE = (0x1L<<BITS)/180.0D;
-  /** rounding error for quantized latitude and longitude values */
-  public static final double TOLERANCE = 1E-6;
-
   /** Minimum longitude value. */
   public static final double MIN_LON_INCL = -180.0D;
 
@@ -66,44 +58,14 @@ public final class GeoUtils {
   private GeoUtils() {
   }
 
-  /**
-   * encode longitude, latitude geopoint values using morton encoding method
-   * https://en.wikipedia.org/wiki/Z-order_curve
-   */
-  public static final Long mortonHash(final double lon, final double lat) {
-    return BitUtil.interleave(scaleLon(lon), scaleLat(lat));
-  }
-
-  /** decode longitude value from morton encoded geo point */
-  public static final double mortonUnhashLon(final long hash) {
-    return unscaleLon(BitUtil.deinterleave(hash));
-  }
-
-  /** decode latitude value from morton encoded geo point */
-  public static final double mortonUnhashLat(final long hash) {
-    return unscaleLat(BitUtil.deinterleave(hash >>> 1));
-  }
-
-  private static final long scaleLon(final double val) {
-    return (long) ((val-MIN_LON_INCL) * LON_SCALE);
-  }
-
-  private static final long scaleLat(final double val) {
-    return (long) ((val-MIN_LAT_INCL) * LAT_SCALE);
-  }
-
-  private static final double unscaleLon(final long val) {
-    return (val / LON_SCALE) + MIN_LON_INCL;
-  }
-
-  private static final double unscaleLat(final long val) {
-    return (val / LAT_SCALE) + MIN_LAT_INCL;
+  /** validates latitude value is within standard +/-90 coordinate bounds */
+  public static boolean isValidLat(double lat) {
+    return Double.isNaN(lat) == false && lat >= MIN_LAT_INCL && lat <=
MAX_LAT_INCL;
   }
 
-  /** Compare two position values within a {@link GeoUtils#TOLERANCE} factor */
-  public static double compare(final double v1, final double v2) {
-    final double delta = v1-v2;
-    return abs(delta) <= TOLERANCE ? 0 : delta;
+  /** validates longitude value is within standard +/-180 coordinate bounds */
+  public static boolean isValidLon(double lon) {
+    return Double.isNaN(lon) == false && lon >= MIN_LON_INCL && lon <=
MAX_LON_INCL;
   }
 
   /** Puts longitude in range of -180 to +180. */
@@ -130,28 +92,15 @@ public final class GeoUtils {
     return (off <= 180 ? off : 360-off) - 90;
   }
 
-  /** Converts long value to bit string (useful for debugging) */
-  public static String geoTermToString(long term) {
-    StringBuilder s = new StringBuilder(64);
-    final int numberOfLeadingZeros = Long.numberOfLeadingZeros(term);
-    for (int i = 0; i < numberOfLeadingZeros; i++) {
-      s.append('0');
-    }
-    if (term != 0) {
-      s.append(Long.toBinaryString(term));
-    }
-    return s.toString();
-  }
-
   /**
    * Converts a given circle (defined as a point/radius) to an approximated line-segment
polygon
    *
-   * @param lon longitudinal center of circle (in degrees)
-   * @param lat latitudinal center of circle (in degrees)
+   * @param lon          longitudinal center of circle (in degrees)
+   * @param lat          latitudinal center of circle (in degrees)
    * @param radiusMeters distance radius of circle (in meters)
    * @return a list of lon/lat points representing the circle
    */
-  @SuppressWarnings({"unchecked","rawtypes"})
+  @SuppressWarnings({"unchecked", "rawtypes"})
   public static ArrayList<double[]> circleToPoly(final double lon, final double lat,
final double radiusMeters) {
     double angle;
     // a little under-sampling (to limit the number of polygonal points): using archimedes
estimation of pi
@@ -161,9 +110,9 @@ public final class GeoUtils {
     double[] lats = new double[sides];
 
     double[] pt = new double[2];
-    final int sidesLen = sides-1;
-    for (int i=0; i<sidesLen; ++i) {
-      angle = (i*360/sides);
+    final int sidesLen = sides - 1;
+    for (int i = 0; i < sidesLen; ++i) {
+      angle = (i * 360 / sides);
       pt = pointFromLonLatBearingGreatCircle(lon, lat, angle, radiusMeters, pt);
       lons[i] = pt[0];
       lats[i] = pt[1];
@@ -235,14 +184,4 @@ public final class GeoUtils {
     return new GeoRect(max(minLon - TOLERANCE, MIN_LON_INCL), min(maxLon + TOLERANCE, MAX_LON_INCL),
         max(minLat - TOLERANCE, MIN_LAT_INCL), min(maxLat + TOLERANCE, MAX_LAT_INCL));
   }
-
-  /** validates latitude value is within standard +/-90 coordinate bounds */
-  public static boolean isValidLat(double lat) {
-    return Double.isNaN(lat) == false && lat >= MIN_LAT_INCL && lat <=
MAX_LAT_INCL;
-  }
-
-  /** validates longitude value is within standard +/-180 coordinate bounds */
-  public static boolean isValidLon(double lon) {
-    return Double.isNaN(lon) == false && lon >= MIN_LON_INCL && lon <=
MAX_LON_INCL;
-  }
 }

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/74a08c08/lucene/spatial/src/test/org/apache/lucene/spatial/search/TestGeoPointQuery.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/test/org/apache/lucene/spatial/search/TestGeoPointQuery.java
b/lucene/spatial/src/test/org/apache/lucene/spatial/search/TestGeoPointQuery.java
index cfd51af..083b28a 100644
--- a/lucene/spatial/src/test/org/apache/lucene/spatial/search/TestGeoPointQuery.java
+++ b/lucene/spatial/src/test/org/apache/lucene/spatial/search/TestGeoPointQuery.java
@@ -27,7 +27,9 @@ import org.apache.lucene.search.IndexSearcher;
 import org.apache.lucene.search.Query;
 import org.apache.lucene.search.TopDocs;
 import org.apache.lucene.store.Directory;
+import org.apache.lucene.spatial.util.GeoEncodingUtils;
 import org.apache.lucene.spatial.document.GeoPointField;
+import org.apache.lucene.spatial.document.GeoPointField.TermEncoding;
 import org.apache.lucene.spatial.util.BaseGeoPointTestCase;
 import org.apache.lucene.spatial.util.GeoRect;
 import org.apache.lucene.spatial.util.GeoRelationUtils;
@@ -50,61 +52,63 @@ public class TestGeoPointQuery extends BaseGeoPointTestCase {
   private static Directory directory = null;
   private static IndexReader reader = null;
   private static IndexSearcher searcher = null;
+  private static TermEncoding termEncoding = null;
+  private static FieldType fieldType = null;
 
   @Override
   protected void addPointToDoc(String field, Document doc, double lat, double lon) {
-    doc.add(new GeoPointField(field, lon, lat, Field.Store.NO));
+    doc.add(new GeoPointField(field, lon, lat, fieldType));
   }
 
   @Override
   protected Query newBBoxQuery(String field, GeoRect rect) {
-    return new GeoPointInBBoxQuery(field, rect.minLon, rect.minLat, rect.maxLon, rect.maxLat);
+    return new GeoPointInBBoxQuery(field, termEncoding, rect.minLon, rect.minLat, rect.maxLon,
rect.maxLat);
   }
 
   @Override
   protected Query newDistanceQuery(String field, double centerLat, double centerLon, double
radiusMeters) {
-    return new GeoPointDistanceQuery(field, centerLon, centerLat, radiusMeters);
+    return new GeoPointDistanceQuery(field, termEncoding, centerLon, centerLat, radiusMeters);
   }
 
   @Override
   protected Query newDistanceRangeQuery(String field, double centerLat, double centerLon,
double minRadiusMeters, double radiusMeters) {
-    return new GeoPointDistanceRangeQuery(field, centerLon, centerLat, minRadiusMeters, radiusMeters);
+    return new GeoPointDistanceRangeQuery(field, termEncoding, centerLon, centerLat, minRadiusMeters,
radiusMeters);
   }
 
   @Override
   protected Query newPolygonQuery(String field, double[] lats, double[] lons) {
-    return new GeoPointInPolygonQuery(field, lons, lats);
+    return new GeoPointInPolygonQuery(field, termEncoding, lons, lats);
   }
 
   @BeforeClass
   public static void beforeClass() throws Exception {
     directory = newDirectory();
+    termEncoding = TermEncoding.PREFIX;// randomTermEncoding();
+    fieldType = randomFieldType();
 
     RandomIndexWriter writer = new RandomIndexWriter(random(), directory,
         newIndexWriterConfig(new MockAnalyzer(random()))
             .setMaxBufferedDocs(TestUtil.nextInt(random(), 100, 1000))
             .setMergePolicy(newLogMergePolicy()));
 
-    // create some simple geo points
-    final FieldType storedPoint = new FieldType(GeoPointField.TYPE_STORED);
     // this is a simple systematic test
     GeoPointField[] pts = new GeoPointField[] {
-        new GeoPointField(FIELD_NAME, -96.774, 32.763420, storedPoint),
-        new GeoPointField(FIELD_NAME, -96.7759895324707, 32.7559529921407, storedPoint),
-        new GeoPointField(FIELD_NAME, -96.77701950073242, 32.77866942010977, storedPoint),
-        new GeoPointField(FIELD_NAME, -96.7706036567688, 32.7756745755423, storedPoint),
-        new GeoPointField(FIELD_NAME, -139.73458170890808, 27.703618681345585, storedPoint),
-        new GeoPointField(FIELD_NAME, -96.4538113027811, 32.94823588839368, storedPoint),
-        new GeoPointField(FIELD_NAME, -96.65084838867188, 33.06047141970814, storedPoint),
-        new GeoPointField(FIELD_NAME, -96.7772, 32.778650, storedPoint),
-        new GeoPointField(FIELD_NAME, -177.23537676036358, -88.56029371730983, storedPoint),
-        new GeoPointField(FIELD_NAME, -26.779373834241003, 33.541429799076354, storedPoint),
-        new GeoPointField(FIELD_NAME, -77.35379276106497, 26.774024500421728, storedPoint),
-        new GeoPointField(FIELD_NAME, -14.796283808944777, -90.0, storedPoint),
-        new GeoPointField(FIELD_NAME, -178.8538113027811, 32.94823588839368, storedPoint),
-        new GeoPointField(FIELD_NAME, 178.8538113027811, 32.94823588839368, storedPoint),
-        new GeoPointField(FIELD_NAME, -73.998776, 40.720611, storedPoint),
-        new GeoPointField(FIELD_NAME, -179.5, -44.5, storedPoint)};
+        new GeoPointField(FIELD_NAME, -96.774, 32.763420, fieldType),
+        new GeoPointField(FIELD_NAME, -96.7759895324707, 32.7559529921407, fieldType),
+        new GeoPointField(FIELD_NAME, -96.77701950073242, 32.77866942010977, fieldType),
+        new GeoPointField(FIELD_NAME, -96.7706036567688, 32.7756745755423, fieldType),
+        new GeoPointField(FIELD_NAME, -139.73458170890808, 27.703618681345585, fieldType),
+        new GeoPointField(FIELD_NAME, -96.4538113027811, 32.94823588839368, fieldType),
+        new GeoPointField(FIELD_NAME, -96.65084838867188, 33.06047141970814, fieldType),
+        new GeoPointField(FIELD_NAME, -96.7772, 32.778650, fieldType),
+        new GeoPointField(FIELD_NAME, -177.23537676036358, -88.56029371730983, fieldType),
+        new GeoPointField(FIELD_NAME, -26.779373834241003, 33.541429799076354, fieldType),
+        new GeoPointField(FIELD_NAME, -77.35379276106497, 26.774024500421728, fieldType),
+        new GeoPointField(FIELD_NAME, -14.796283808944777, -90.0, fieldType),
+        new GeoPointField(FIELD_NAME, -178.8538113027811, 32.94823588839368, fieldType),
+        new GeoPointField(FIELD_NAME, 178.8538113027811, 32.94823588839368, fieldType),
+        new GeoPointField(FIELD_NAME, -73.998776, 40.720611, fieldType),
+        new GeoPointField(FIELD_NAME, -179.5, -44.5, fieldType)};
 
     for (GeoPointField p : pts) {
       Document doc = new Document();
@@ -141,27 +145,38 @@ public class TestGeoPointQuery extends BaseGeoPointTestCase {
     directory = null;
   }
 
+  private static TermEncoding randomTermEncoding() {
+    return random().nextBoolean() ? TermEncoding.NUMERIC : TermEncoding.PREFIX;
+  }
+
+  private static FieldType randomFieldType() {
+    if (termEncoding == TermEncoding.PREFIX) {
+      return GeoPointField.PREFIX_TYPE_NOT_STORED;
+    }
+    return GeoPointField.NUMERIC_TYPE_NOT_STORED;
+  }
+
   private TopDocs bboxQuery(double minLon, double minLat, double maxLon, double maxLat, int
limit) throws Exception {
-    GeoPointInBBoxQuery q = new GeoPointInBBoxQuery(FIELD_NAME, minLon, minLat, maxLon, maxLat);
+    GeoPointInBBoxQuery q = new GeoPointInBBoxQuery(FIELD_NAME, termEncoding, minLon, minLat,
maxLon, maxLat);
     return searcher.search(q, limit);
   }
 
   private TopDocs polygonQuery(double[] lon, double[] lat, int limit) throws Exception {
-    GeoPointInPolygonQuery q = new GeoPointInPolygonQuery(FIELD_NAME, lon, lat);
+    GeoPointInPolygonQuery q = new GeoPointInPolygonQuery(FIELD_NAME, termEncoding, lon,
lat);
     return searcher.search(q, limit);
   }
 
   private TopDocs geoDistanceQuery(double lon, double lat, double radius, int limit) throws
Exception {
-    GeoPointDistanceQuery q = new GeoPointDistanceQuery(FIELD_NAME, lon, lat, radius);
+    GeoPointDistanceQuery q = new GeoPointDistanceQuery(FIELD_NAME, termEncoding, lon, lat,
radius);
     return searcher.search(q, limit);
   }
 
   @Override
   protected Boolean rectContainsPoint(GeoRect rect, double pointLat, double pointLon) {
-    if (GeoUtils.compare(pointLon, rect.minLon) == 0.0 ||
-        GeoUtils.compare(pointLon, rect.maxLon) == 0.0 ||
-        GeoUtils.compare(pointLat, rect.minLat) == 0.0 ||
-        GeoUtils.compare(pointLat, rect.maxLat) == 0.0) {
+    if (GeoEncodingUtils.compare(pointLon, rect.minLon) == 0.0 ||
+        GeoEncodingUtils.compare(pointLon, rect.maxLon) == 0.0 ||
+        GeoEncodingUtils.compare(pointLat, rect.minLat) == 0.0 ||
+        GeoEncodingUtils.compare(pointLat, rect.maxLat) == 0.0) {
       // Point is very close to rect boundary
       return null;
     }
@@ -202,12 +217,12 @@ public class TestGeoPointQuery extends BaseGeoPointTestCase {
 
   private static boolean radiusQueryCanBeWrong(double centerLat, double centerLon, double
ptLon, double ptLat,
                                                final double radius) {
-    final long hashedCntr = GeoUtils.mortonHash(centerLon, centerLat);
-    centerLon = GeoUtils.mortonUnhashLon(hashedCntr);
-    centerLat = GeoUtils.mortonUnhashLat(hashedCntr);
-    final long hashedPt = GeoUtils.mortonHash(ptLon, ptLat);
-    ptLon = GeoUtils.mortonUnhashLon(hashedPt);
-    ptLat = GeoUtils.mortonUnhashLat(hashedPt);
+    final long hashedCntr = GeoEncodingUtils.mortonHash(centerLon, centerLat);
+    centerLon = GeoEncodingUtils.mortonUnhashLon(hashedCntr);
+    centerLat = GeoEncodingUtils.mortonUnhashLat(hashedCntr);
+    final long hashedPt = GeoEncodingUtils.mortonHash(ptLon, ptLat);
+    ptLon = GeoEncodingUtils.mortonUnhashLon(hashedPt);
+    ptLat = GeoEncodingUtils.mortonUnhashLat(hashedPt);
 
     double ptDistance = SloppyMath.haversin(centerLat, centerLon, ptLat, ptLon)*1000.0;
     double delta = StrictMath.abs(ptDistance - radius);
@@ -222,7 +237,7 @@ public class TestGeoPointQuery extends BaseGeoPointTestCase {
 
   private TopDocs geoDistanceRangeQuery(double lon, double lat, double minRadius, double
maxRadius, int limit)
       throws Exception {
-    GeoPointDistanceRangeQuery q = new GeoPointDistanceRangeQuery(FIELD_NAME, lon, lat, minRadius,
maxRadius);
+    GeoPointDistanceRangeQuery q = new GeoPointDistanceRangeQuery(FIELD_NAME, termEncoding,
lon, lat, minRadius, maxRadius);
     return searcher.search(q, limit);
   }
 
@@ -342,9 +357,9 @@ public class TestGeoPointQuery extends BaseGeoPointTestCase {
   }
 
   public void testMortonEncoding() throws Exception {
-    long hash = GeoUtils.mortonHash(180, 90);
-    assertEquals(180.0, GeoUtils.mortonUnhashLon(hash), 0);
-    assertEquals(90.0, GeoUtils.mortonUnhashLat(hash), 0);
+    long hash = GeoEncodingUtils.mortonHash(180, 90);
+    assertEquals(180.0, GeoEncodingUtils.mortonUnhashLon(hash), 0);
+    assertEquals(90.0, GeoEncodingUtils.mortonUnhashLat(hash), 0);
   }
 
   public void testEncodeDecode() throws Exception {
@@ -354,12 +369,12 @@ public class TestGeoPointQuery extends BaseGeoPointTestCase {
       double lat = randomLat(small);
       double lon = randomLon(small);
 
-      long enc = GeoUtils.mortonHash(lon, lat);
-      double latEnc = GeoUtils.mortonUnhashLat(enc);
-      double lonEnc = GeoUtils.mortonUnhashLon(enc);
+      long enc = GeoEncodingUtils.mortonHash(lon, lat);
+      double latEnc = GeoEncodingUtils.mortonUnhashLat(enc);
+      double lonEnc = GeoEncodingUtils.mortonUnhashLon(enc);
 
-      assertEquals("lat=" + lat + " latEnc=" + latEnc + " diff=" + (lat - latEnc), lat, latEnc,
GeoUtils.TOLERANCE);
-      assertEquals("lon=" + lon + " lonEnc=" + lonEnc + " diff=" + (lon - lonEnc), lon, lonEnc,
GeoUtils.TOLERANCE);
+      assertEquals("lat=" + lat + " latEnc=" + latEnc + " diff=" + (lat - latEnc), lat, latEnc,
GeoEncodingUtils.TOLERANCE);
+      assertEquals("lon=" + lon + " lonEnc=" + lonEnc + " diff=" + (lon - lonEnc), lon, lonEnc,
GeoEncodingUtils.TOLERANCE);
     }
   }
 
@@ -370,13 +385,13 @@ public class TestGeoPointQuery extends BaseGeoPointTestCase {
       double lat = randomLat(small);
       double lon = randomLon(small);
 
-      long enc = GeoUtils.mortonHash(lon, lat);
-      double latEnc = GeoUtils.mortonUnhashLat(enc);
-      double lonEnc = GeoUtils.mortonUnhashLon(enc);
+      long enc = GeoEncodingUtils.mortonHash(lon, lat);
+      double latEnc = GeoEncodingUtils.mortonUnhashLat(enc);
+      double lonEnc = GeoEncodingUtils.mortonUnhashLon(enc);
 
-      long enc2 = GeoUtils.mortonHash(lon, lat);
-      double latEnc2 = GeoUtils.mortonUnhashLat(enc2);
-      double lonEnc2 = GeoUtils.mortonUnhashLon(enc2);
+      long enc2 = GeoEncodingUtils.mortonHash(lon, lat);
+      double latEnc2 = GeoEncodingUtils.mortonUnhashLat(enc2);
+      double lonEnc2 = GeoEncodingUtils.mortonUnhashLon(enc2);
       assertEquals(latEnc, latEnc2, 0.0);
       assertEquals(lonEnc, lonEnc2, 0.0);
     }

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/74a08c08/lucene/spatial/src/test/org/apache/lucene/spatial/util/BaseGeoPointTestCase.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/test/org/apache/lucene/spatial/util/BaseGeoPointTestCase.java
b/lucene/spatial/src/test/org/apache/lucene/spatial/util/BaseGeoPointTestCase.java
index cf26b88..2691ff8 100644
--- a/lucene/spatial/src/test/org/apache/lucene/spatial/util/BaseGeoPointTestCase.java
+++ b/lucene/spatial/src/test/org/apache/lucene/spatial/util/BaseGeoPointTestCase.java
@@ -57,8 +57,8 @@ public abstract class BaseGeoPointTestCase extends LuceneTestCase {
 
   protected static final String FIELD_NAME = "point";
 
-  private static final double LON_SCALE = (0x1L<<GeoUtils.BITS)/360.0D;
-  private static final double LAT_SCALE = (0x1L<<GeoUtils.BITS)/180.0D;
+  private static final double LON_SCALE = (0x1L<< GeoEncodingUtils.BITS)/360.0D;
+  private static final double LAT_SCALE = (0x1L<< GeoEncodingUtils.BITS)/180.0D;
 
   private static double originLat;
   private static double originLon;

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/74a08c08/lucene/spatial/src/test/org/apache/lucene/spatial/util/TestGeoUtils.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/test/org/apache/lucene/spatial/util/TestGeoUtils.java b/lucene/spatial/src/test/org/apache/lucene/spatial/util/TestGeoUtils.java
index c5480c7..8f7a391 100644
--- a/lucene/spatial/src/test/org/apache/lucene/spatial/util/TestGeoUtils.java
+++ b/lucene/spatial/src/test/org/apache/lucene/spatial/util/TestGeoUtils.java
@@ -24,6 +24,7 @@ import java.util.HashSet;
 import java.util.List;
 import java.util.Set;
 
+import org.apache.lucene.util.BytesRefBuilder;
 import org.apache.lucene.util.LuceneTestCase;
 import org.junit.BeforeClass;
 
@@ -38,8 +39,8 @@ import static org.apache.lucene.spatial.util.GeoDistanceUtils.DISTANCE_PCT_ERR;
  */
 public class TestGeoUtils extends LuceneTestCase {
 
-  private static final double LON_SCALE = (0x1L<<GeoUtils.BITS)/360.0D;
-  private static final double LAT_SCALE = (0x1L<<GeoUtils.BITS)/180.0D;
+  private static final double LON_SCALE = (0x1L<<GeoEncodingUtils.BITS)/360.0D;
+  private static final double LAT_SCALE = (0x1L<<GeoEncodingUtils.BITS)/180.0D;
 
   // Global bounding box we will "cover" in the random test; we have to make this "smallish"
else the queries take very long:
   private static double originLat;
@@ -77,7 +78,7 @@ public class TestGeoUtils extends LuceneTestCase {
 
       // compute geohash straight from lat/lon and from morton encoded value to ensure they're
the same
       randomGeoHashString = GeoHashUtils.stringEncode(lon, lat, randomLevel = random().nextInt(12
- 1) + 1);
-      mortonGeoHash = GeoHashUtils.stringEncodeFromMortonLong(GeoUtils.mortonHash(lon, lat),
randomLevel);
+      mortonGeoHash = GeoHashUtils.stringEncodeFromMortonLong(GeoEncodingUtils.mortonHash(lon,
lat), randomLevel);
       assertEquals(randomGeoHashString, mortonGeoHash);
 
       // v&v conversion from lat/lon or geohashstring to geohash long and back to geohash
string
@@ -90,8 +91,8 @@ public class TestGeoUtils extends LuceneTestCase {
       assertEquals(mortonLongFromGHLong, mortonLongFromGHString);
 
       // v&v lat/lon from geohash string and geohash long
-      assertEquals(GeoUtils.mortonUnhashLat(mortonLongFromGHString), GeoUtils.mortonUnhashLat(mortonLongFromGHLong),
0);
-      assertEquals(GeoUtils.mortonUnhashLon(mortonLongFromGHString), GeoUtils.mortonUnhashLon(mortonLongFromGHLong),
0);
+      assertEquals(GeoEncodingUtils.mortonUnhashLat(mortonLongFromGHString), GeoEncodingUtils.mortonUnhashLat(mortonLongFromGHLong),
0);
+      assertEquals(GeoEncodingUtils.mortonUnhashLon(mortonLongFromGHString), GeoEncodingUtils.mortonUnhashLon(mortonLongFromGHLong),
0);
     }
   }
 
@@ -115,8 +116,8 @@ public class TestGeoUtils extends LuceneTestCase {
     final String geohash = GeoHashUtils.stringEncode(4.8909347, 52.3738007);
     final long hash = GeoHashUtils.mortonEncode(geohash);
 
-    assertEquals(52.3738007, GeoUtils.mortonUnhashLat(hash), 0.00001D);
-    assertEquals(4.8909347, GeoUtils.mortonUnhashLon(hash), 0.00001D);
+    assertEquals(52.3738007, GeoEncodingUtils.mortonUnhashLat(hash), 0.00001D);
+    assertEquals(4.8909347, GeoEncodingUtils.mortonUnhashLon(hash), 0.00001D);
   }
 
   /**
@@ -128,18 +129,18 @@ public class TestGeoUtils extends LuceneTestCase {
 
     final long hash = GeoHashUtils.mortonEncode(geohash);
 
-    assertEquals(84.6, GeoUtils.mortonUnhashLat(hash), 0.00001D);
-    assertEquals(10.5, GeoUtils.mortonUnhashLon(hash), 0.00001D);
+    assertEquals(84.6, GeoEncodingUtils.mortonUnhashLat(hash), 0.00001D);
+    assertEquals(10.5, GeoEncodingUtils.mortonUnhashLon(hash), 0.00001D);
   }
 
   public void testDecodeEncode() {
     final String geoHash = "u173zq37x014";
     assertEquals(geoHash, GeoHashUtils.stringEncode(4.8909347, 52.3738007));
     final long mortonHash = GeoHashUtils.mortonEncode(geoHash);
-    final double lon = GeoUtils.mortonUnhashLon(mortonHash);
-    final double lat = GeoUtils.mortonUnhashLat(mortonHash);
-    assertEquals(52.37380061d, GeoUtils.mortonUnhashLat(mortonHash), 0.000001d);
-    assertEquals(4.8909343d, GeoUtils.mortonUnhashLon(mortonHash), 0.000001d);
+    final double lon = GeoEncodingUtils.mortonUnhashLon(mortonHash);
+    final double lat = GeoEncodingUtils.mortonUnhashLat(mortonHash);
+    assertEquals(52.37380061d, GeoEncodingUtils.mortonUnhashLat(mortonHash), 0.000001d);
+    assertEquals(4.8909343d, GeoEncodingUtils.mortonUnhashLon(mortonHash), 0.000001d);
 
     assertEquals(geoHash, GeoHashUtils.stringEncode(lon, lat));
   }
@@ -416,7 +417,7 @@ public class TestGeoUtils extends LuceneTestCase {
     }
   }
 
-  /** Tests consistency of GeoUtils.rectWithinCircle, .rectCrossesCircle, .rectWithin and
SloppyMath.haversine distance check */
+  /** Tests consistency of GeoEncodingUtils.rectWithinCircle, .rectCrossesCircle, .rectWithin
and SloppyMath.haversine distance check */
   public void testGeoRelations() throws Exception {
 
     int numDocs = atLeast(1000);
@@ -543,4 +544,22 @@ public class TestGeoUtils extends LuceneTestCase {
       }
     }
   }
+
+  /**
+   * Tests stability of {@link GeoEncodingUtils#geoCodedToPrefixCoded}
+   */
+  public void testGeoPrefixCoding() throws Exception {
+    int numIters = atLeast(1000);
+    long hash;
+    long decodedHash;
+    BytesRefBuilder brb = new BytesRefBuilder();
+    while (numIters-- >= 0) {
+      hash = GeoEncodingUtils.mortonHash(randomLon(false), randomLat(false));
+      for (int i=32; i<64; ++i) {
+        GeoEncodingUtils.geoCodedToPrefixCoded(hash, i, brb);
+        decodedHash = GeoEncodingUtils.prefixCodedToGeoCoded(brb.get());
+        assertEquals((hash >>> i) << i, decodedHash);
+      }
+    }
+  }
 }


Mime
View raw message