lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From mikemcc...@apache.org
Subject lucene-solr:branch_6x: LUCENE-7168: improve encode and quantization testing for geo3d
Date Wed, 06 Apr 2016 23:17:46 GMT
Repository: lucene-solr
Updated Branches:
  refs/heads/branch_6x a3ea71e04 -> 6868a8cd7


LUCENE-7168: improve encode and quantization testing for geo3d


Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/6868a8cd
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/6868a8cd
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/6868a8cd

Branch: refs/heads/branch_6x
Commit: 6868a8cd74d2d21dd679dfbb867d0823253ac2a5
Parents: a3ea71e
Author: Mike McCandless <mikemccand@apache.org>
Authored: Wed Apr 6 19:18:56 2016 -0400
Committer: Mike McCandless <mikemccand@apache.org>
Committed: Wed Apr 6 19:19:31 2016 -0400

----------------------------------------------------------------------
 lucene/CHANGES.txt                              |   3 +
 .../org/apache/lucene/document/LatLonPoint.java |   4 +-
 .../org/apache/lucene/spatial3d/Geo3DPoint.java |   5 +-
 .../org/apache/lucene/spatial3d/Geo3DUtil.java  |  75 +-
 .../spatial3d/PointInGeo3DShapeQuery.java       |  71 +-
 .../spatial3d/PointInShapeIntersectVisitor.java | 107 +++
 .../apache/lucene/spatial3d/TestGeo3DPoint.java | 682 +++++++++++++------
 7 files changed, 622 insertions(+), 325 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6868a8cd/lucene/CHANGES.txt
----------------------------------------------------------------------
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index da5be98..f28254d 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -63,6 +63,9 @@ Bug Fixes
 * LUCENE-7166: Fix corner case bugs in LatLonPoint/GeoPointField bounding box
   queries. (Robert Muir)
 
+* LUCENE-7168: Switch to stable encode for geo3d, remove quantization
+  test leniency, remove dead code (Mike McCandless)
+
 Other
 
 * LUCENE-7174: Upgrade randomizedtesting to 2.3.4. (Uwe Schindler, Dawid Weiss)

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6868a8cd/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPoint.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPoint.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPoint.java
index 107d83c..b2c39c2 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPoint.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPoint.java
@@ -199,7 +199,7 @@ public class LatLonPoint extends Field {
    */
   public static double decodeLatitude(int encoded) {
     double result = encoded * LATITUDE_DECODE;
-    assert result >= GeoUtils.MIN_LAT_INCL && result <= GeoUtils.MAX_LAT_INCL;
+    assert result >= GeoUtils.MIN_LAT_INCL && result < GeoUtils.MAX_LAT_INCL;
     return result;
   }
   
@@ -220,7 +220,7 @@ public class LatLonPoint extends Field {
    */  
   public static double decodeLongitude(int encoded) {
     double result = encoded * LONGITUDE_DECODE;
-    assert result >= GeoUtils.MIN_LON_INCL && result <= GeoUtils.MAX_LON_INCL;
+    assert result >= GeoUtils.MIN_LON_INCL && result < GeoUtils.MAX_LON_INCL;
     return result;
   }
 

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6868a8cd/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPoint.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPoint.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPoint.java
index be8990f..1e07aa7 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPoint.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPoint.java
@@ -24,7 +24,6 @@ import org.apache.lucene.document.FieldType;
 import org.apache.lucene.index.PointValues;
 import org.apache.lucene.geo.Polygon;
 import org.apache.lucene.geo.GeoUtils;
-import org.apache.lucene.spatial3d.geom.Vector;
 import org.apache.lucene.spatial3d.geom.GeoPoint;
 import org.apache.lucene.spatial3d.geom.GeoShape;
 import org.apache.lucene.spatial3d.geom.PlanetModel;
@@ -231,12 +230,12 @@ public final class Geo3DPoint extends Field {
   
   /** Encode single dimension */
   public static void encodeDimension(double value, byte bytes[], int offset) {
-    NumericUtils.intToSortableBytes(Geo3DUtil.encodeValue(PlanetModel.WGS84.getMaximumMagnitude(), value), bytes, offset);
+    NumericUtils.intToSortableBytes(Geo3DUtil.encodeValue(value), bytes, offset);
   }
   
   /** Decode single dimension */
   public static double decodeDimension(byte value[], int offset) {
-    return Geo3DUtil.decodeValueCenter(PlanetModel.WGS84.getMaximumMagnitude(), NumericUtils.sortableBytesToInt(value, offset));
+    return Geo3DUtil.decodeValue(NumericUtils.sortableBytesToInt(value, offset));
   }
 
   /** Returns a query matching all points inside the provided shape.

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6868a8cd/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DUtil.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DUtil.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DUtil.java
index 0a0bf30..cc11294 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DUtil.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DUtil.java
@@ -16,44 +16,59 @@
  */
 package org.apache.lucene.spatial3d;
 
+import org.apache.lucene.spatial3d.geom.PlanetModel;
+
 class Geo3DUtil {
 
-  /** Clips the incoming value to the allowed min/max range before encoding, instead of throwing an exception. */
-  public static int encodeValueLenient(double planetMax, double x) {
-    if (x > planetMax) {
-      x = planetMax;
-    } else if (x < -planetMax) {
-      x = -planetMax;
-    }
-    return encodeValue(planetMax, x);
-  }
+  private static final double MAX_VALUE = PlanetModel.WGS84.getMaximumMagnitude();
+  private static final int BITS = 32;
+  private static final double MUL = (0x1L<<BITS)/(2*MAX_VALUE);
+  static final double DECODE = getNextSafeDouble(1/MUL);
+  private static final int MIN_ENCODED_VALUE = encodeValue(-MAX_VALUE);
 
-  public static int encodeValue(double planetMax, double x) {
-    if (x > planetMax) {
-      throw new IllegalArgumentException("value=" + x + " is out-of-bounds (greater than planetMax=" + planetMax + ")");
+  public static int encodeValue(double x) {
+    if (x > MAX_VALUE) {
+      throw new IllegalArgumentException("value=" + x + " is out-of-bounds (greater than WGS84's planetMax=" + MAX_VALUE + ")");
     }
-    if (x < -planetMax) {
-      throw new IllegalArgumentException("value=" + x + " is out-of-bounds (less than than -planetMax=" + -planetMax + ")");
+    if (x < -MAX_VALUE) {
+      throw new IllegalArgumentException("value=" + x + " is out-of-bounds (less than than WGS84's -planetMax=" + -MAX_VALUE + ")");
     }
-    long y = Math.round (x * (Integer.MAX_VALUE / planetMax));
-    assert y >= Integer.MIN_VALUE;
-    assert y <= Integer.MAX_VALUE;
-
-    return (int) y;
+    long result = (long) Math.floor(x / DECODE);
+    //System.out.println("    enc: " + x + " -> " + result);
+    assert result >= Integer.MIN_VALUE;
+    assert result <= Integer.MAX_VALUE;
+    return (int) result;
   }
 
-  /** Center decode */
-  public static double decodeValueCenter(double planetMax, int x) {
-    return x * (planetMax / Integer.MAX_VALUE);
+  public static double decodeValue(int x) {
+    double result;
+    if (x == MIN_ENCODED_VALUE) {
+      // We must special case this, because -MAX_VALUE is not guaranteed to land precisely at a floor value, and we don't ever want to
+      // return a value outside of the planet's range (I think?).  The max value is "safe" because we floor during encode:
+      result = -MAX_VALUE;
+    } else {
+      result = x * DECODE;
+    }
+    assert result >= -MAX_VALUE && result <= MAX_VALUE;
+    return result;
   }
 
-  /** More negative decode, at bottom of cell */
-  public static double decodeValueMin(double planetMax, int x) {
-    return (((double)x) - 0.5) * (planetMax / Integer.MAX_VALUE);
-  }
-  
-  /** More positive decode, at top of cell  */
-  public static double decodeValueMax(double planetMax, int x) {
-    return (((double)x) + 0.5) * (planetMax / Integer.MAX_VALUE);
+  /** Returns a double value >= x such that if you multiply that value by an int, and then
+   *  divide it by that int again, you get precisely the same value back */
+  private static double getNextSafeDouble(double x) {
+
+    // Move to double space:
+    long bits = Double.doubleToLongBits(x);
+
+    // Make sure we are beyond the actual maximum value:
+    bits += Integer.MAX_VALUE;
+
+    // Clear the bottom 32 bits:
+    bits &= ~((long) Integer.MAX_VALUE);
+
+    // Convert back to double:
+    double result = Double.longBitsToDouble(bits);
+    assert result > x;
+    return result;
   }
 }

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6868a8cd/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/PointInGeo3DShapeQuery.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/PointInGeo3DShapeQuery.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/PointInGeo3DShapeQuery.java
index 3cc9530..ef0fe47 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/PointInGeo3DShapeQuery.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/PointInGeo3DShapeQuery.java
@@ -19,13 +19,9 @@ package org.apache.lucene.spatial3d;
 import java.io.IOException;
 
 import org.apache.lucene.spatial3d.geom.BasePlanetObject;
-import org.apache.lucene.spatial3d.geom.GeoArea;
-import org.apache.lucene.spatial3d.geom.GeoAreaFactory;
 import org.apache.lucene.spatial3d.geom.GeoShape;
 import org.apache.lucene.spatial3d.geom.PlanetModel;
-import org.apache.lucene.index.PointValues.IntersectVisitor;
 import org.apache.lucene.index.PointValues;
-import org.apache.lucene.index.PointValues.Relation;
 import org.apache.lucene.index.LeafReader;
 import org.apache.lucene.index.LeafReaderContext;
 import org.apache.lucene.search.ConstantScoreScorer;
@@ -35,7 +31,6 @@ import org.apache.lucene.search.Query;
 import org.apache.lucene.search.Scorer;
 import org.apache.lucene.search.Weight;
 import org.apache.lucene.util.DocIdSetBuilder;
-import org.apache.lucene.util.NumericUtils;
 
 /** Finds all previously indexed points that fall within the specified polygon.
  *
@@ -98,73 +93,9 @@ final class PointInGeo3DShapeQuery extends Query {
         assert xyzSolid.getRelationship(shape) == GeoArea.WITHIN || xyzSolid.getRelationship(shape) == GeoArea.OVERLAPS: "expected WITHIN (1) or OVERLAPS (2) but got " + xyzSolid.getRelationship(shape) + "; shape="+shape+"; XYZSolid="+xyzSolid;
         */
 
-        double planetMax = PlanetModel.WGS84.getMaximumMagnitude();
-
         DocIdSetBuilder result = new DocIdSetBuilder(reader.maxDoc());
 
-        values.intersect(field,
-                         new IntersectVisitor() {
-
-                           @Override
-                           public void visit(int docID) {
-                             result.add(docID);
-                           }
-
-                           @Override
-                           public void visit(int docID, byte[] packedValue) {
-                             assert packedValue.length == 12;
-                             double x = Geo3DPoint.decodeDimension(packedValue, 0);
-                             double y = Geo3DPoint.decodeDimension(packedValue, Integer.BYTES);
-                             double z = Geo3DPoint.decodeDimension(packedValue, 2 * Integer.BYTES);
-                             if (shape.isWithin(x, y, z)) {
-                               result.add(docID);
-                             }
-                           }
-
-                           @Override
-                           public Relation compare(byte[] minPackedValue, byte[] maxPackedValue) {
-                             // Because the dimensional format operates in quantized (64 bit -> 32 bit) space, and the cell bounds
-                             // here are inclusive, we need to extend the bounds to the largest un-quantized values that
-                             // could quantize into these bounds.  The encoding (Geo3DUtil.encodeValue) does
-                             // a Math.round from double to long, so e.g. 1.4 -> 1, and -1.4 -> -1:
-                             double xMin = Geo3DUtil.decodeValueMin(planetMax, NumericUtils.sortableBytesToInt(minPackedValue, 0));
-                             double xMax = Geo3DUtil.decodeValueMax(planetMax, NumericUtils.sortableBytesToInt(maxPackedValue, 0));
-                             double yMin = Geo3DUtil.decodeValueMin(planetMax, NumericUtils.sortableBytesToInt(minPackedValue, 1 * Integer.BYTES));
-                             double yMax = Geo3DUtil.decodeValueMax(planetMax, NumericUtils.sortableBytesToInt(maxPackedValue, 1 * Integer.BYTES));
-                             double zMin = Geo3DUtil.decodeValueMin(planetMax, NumericUtils.sortableBytesToInt(minPackedValue, 2 * Integer.BYTES));
-                             double zMax = Geo3DUtil.decodeValueMax(planetMax, NumericUtils.sortableBytesToInt(maxPackedValue, 2 * Integer.BYTES));
-
-                             //System.out.println("  compare: x=" + cellXMin + "-" + cellXMax + " y=" + cellYMin + "-" + cellYMax + " z=" + cellZMin + "-" + cellZMax);
-                             assert xMin <= xMax;
-                             assert yMin <= yMax;
-                             assert zMin <= zMax;
-
-                             GeoArea xyzSolid = GeoAreaFactory.makeGeoArea(PlanetModel.WGS84, xMin, xMax, yMin, yMax, zMin, zMax);
-
-                             switch(xyzSolid.getRelationship(shape)) {
-                             case GeoArea.CONTAINS:
-                               // Shape fully contains the cell
-                               //System.out.println("    inside");
-                               return Relation.CELL_INSIDE_QUERY;
-                             case GeoArea.OVERLAPS:
-                               // They do overlap but neither contains the other:
-                               //System.out.println("    crosses1");
-                               return Relation.CELL_CROSSES_QUERY;
-                             case GeoArea.WITHIN:
-                               // Cell fully contains the shape:
-                               //System.out.println("    crosses2");
-                               // return Relation.SHAPE_INSIDE_CELL;
-                               return Relation.CELL_CROSSES_QUERY;
-                             case GeoArea.DISJOINT:
-                               // They do not overlap at all
-                               //System.out.println("    outside");
-                               return Relation.CELL_OUTSIDE_QUERY;
-                             default:
-                               assert false;
-                               return Relation.CELL_CROSSES_QUERY;
-                             }
-                           }
-                         });
+        values.intersect(field, new PointInShapeIntersectVisitor(result, shape));
 
         return new ConstantScoreScorer(this, score(), result.build().iterator());
       }

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6868a8cd/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/PointInShapeIntersectVisitor.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/PointInShapeIntersectVisitor.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/PointInShapeIntersectVisitor.java
new file mode 100644
index 0000000..25dea72
--- /dev/null
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/PointInShapeIntersectVisitor.java
@@ -0,0 +1,107 @@
+/*
+ * 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.
+ */
+
+package org.apache.lucene.spatial3d;
+
+import org.apache.lucene.index.PointValues.IntersectVisitor;
+import org.apache.lucene.index.PointValues.Relation;
+import org.apache.lucene.spatial3d.geom.GeoArea;
+import org.apache.lucene.spatial3d.geom.GeoAreaFactory;
+import org.apache.lucene.spatial3d.geom.GeoShape;
+import org.apache.lucene.spatial3d.geom.PlanetModel;
+import org.apache.lucene.util.DocIdSetBuilder;
+import org.apache.lucene.util.NumericUtils;
+
+class PointInShapeIntersectVisitor implements IntersectVisitor {
+  private final DocIdSetBuilder hits;
+  private final GeoShape shape;
+
+  public PointInShapeIntersectVisitor(DocIdSetBuilder hits, GeoShape shape) {
+    this.hits = hits;
+    this.shape = shape;
+  }
+
+  @Override
+  public void visit(int docID) {
+    hits.add(docID);
+  }
+
+  @Override
+  public void visit(int docID, byte[] packedValue) {
+    assert packedValue.length == 12;
+    double x = Geo3DPoint.decodeDimension(packedValue, 0);
+    double y = Geo3DPoint.decodeDimension(packedValue, Integer.BYTES);
+    double z = Geo3DPoint.decodeDimension(packedValue, 2 * Integer.BYTES);
+    if (shape.isWithin(x, y, z)) {
+      hits.add(docID);
+    }
+  }
+  
+  @Override
+  public Relation compare(byte[] minPackedValue, byte[] maxPackedValue) {
+    // Because the dimensional format operates in quantized (64 bit -> 32 bit) space, and the cell bounds
+    // here are inclusive, we need to extend the bounds to the largest un-quantized values that
+    // could quantize into these bounds.  The encoding (Geo3DUtil.encodeValue) does
+    // a Math.round from double to long, so e.g. 1.4 -> 1, and -1.4 -> -1:
+    double xMin = decodeValueMin(NumericUtils.sortableBytesToInt(minPackedValue, 0));
+    double xMax = decodeValueMax(NumericUtils.sortableBytesToInt(maxPackedValue, 0));
+    double yMin = decodeValueMin(NumericUtils.sortableBytesToInt(minPackedValue, 1 * Integer.BYTES));
+    double yMax = decodeValueMax(NumericUtils.sortableBytesToInt(maxPackedValue, 1 * Integer.BYTES));
+    double zMin = decodeValueMin(NumericUtils.sortableBytesToInt(minPackedValue, 2 * Integer.BYTES));
+    double zMax = decodeValueMax(NumericUtils.sortableBytesToInt(maxPackedValue, 2 * Integer.BYTES));
+
+    //System.out.println("  compare: x=" + cellXMin + "-" + cellXMax + " y=" + cellYMin + "-" + cellYMax + " z=" + cellZMin + "-" + cellZMax);
+    assert xMin <= xMax;
+    assert yMin <= yMax;
+    assert zMin <= zMax;
+
+    GeoArea xyzSolid = GeoAreaFactory.makeGeoArea(PlanetModel.WGS84, xMin, xMax, yMin, yMax, zMin, zMax);
+
+    switch(xyzSolid.getRelationship(shape)) {
+    case GeoArea.CONTAINS:
+      // Shape fully contains the cell
+      //System.out.println("    inside");
+      return Relation.CELL_INSIDE_QUERY;
+    case GeoArea.OVERLAPS:
+      // They do overlap but neither contains the other:
+      //System.out.println("    crosses1");
+      return Relation.CELL_CROSSES_QUERY;
+    case GeoArea.WITHIN:
+      // Cell fully contains the shape:
+      //System.out.println("    crosses2");
+      // return Relation.SHAPE_INSIDE_CELL;
+      return Relation.CELL_CROSSES_QUERY;
+    case GeoArea.DISJOINT:
+      // They do not overlap at all
+      //System.out.println("    outside");
+      return Relation.CELL_OUTSIDE_QUERY;
+    default:
+      assert false;
+      return Relation.CELL_CROSSES_QUERY;
+    }
+  }
+
+  /** More negative decode, at bottom of cell */
+  static double decodeValueMin(int x) {
+    return (((double)x) - 0.5) * Geo3DUtil.DECODE;
+  }
+  
+  /** More positive decode, at top of cell  */
+  static double decodeValueMax(int x) {
+    return (((double)x) + 0.5) * Geo3DUtil.DECODE;
+  }
+}

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6868a8cd/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java
index d0d3388..b751125 100644
--- a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java
+++ b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java
@@ -20,11 +20,10 @@ import java.io.IOException;
 import java.io.PrintWriter;
 import java.io.StringWriter;
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Set;
-import java.util.concurrent.CountDownLatch;
-import java.util.concurrent.atomic.AtomicBoolean;
 
 import org.apache.lucene.codecs.Codec;
 import org.apache.lucene.codecs.FilterCodec;
@@ -36,55 +35,52 @@ import org.apache.lucene.codecs.lucene60.Lucene60PointsWriter;
 import org.apache.lucene.document.Document;
 import org.apache.lucene.document.Field;
 import org.apache.lucene.document.NumericDocValuesField;
-import org.apache.lucene.spatial3d.geom.GeoArea;
-import org.apache.lucene.spatial3d.geom.GeoAreaFactory;
-import org.apache.lucene.spatial3d.geom.GeoBBoxFactory;
-import org.apache.lucene.spatial3d.geom.GeoCircleFactory;
-import org.apache.lucene.spatial3d.geom.GeoPathFactory;
-import org.apache.lucene.spatial3d.geom.GeoPoint;
-import org.apache.lucene.spatial3d.geom.GeoPolygonFactory;
-import org.apache.lucene.spatial3d.geom.GeoShape;
-import org.apache.lucene.spatial3d.geom.PlanetModel;
-import org.apache.lucene.spatial3d.geom.XYZBounds;
-import org.apache.lucene.spatial3d.geom.SidedPlane;
-import org.apache.lucene.spatial3d.geom.Plane;
-import org.apache.lucene.spatial3d.geom.GeoPolygon;
+import org.apache.lucene.geo.GeoTestUtil;
+import org.apache.lucene.geo.Polygon;
 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.LeafReader;
 import org.apache.lucene.index.LeafReaderContext;
 import org.apache.lucene.index.MultiDocValues;
 import org.apache.lucene.index.NumericDocValues;
+import org.apache.lucene.index.PointValues.IntersectVisitor;
+import org.apache.lucene.index.PointValues.Relation;
+import org.apache.lucene.index.ReaderUtil;
 import org.apache.lucene.index.SegmentReadState;
 import org.apache.lucene.index.SegmentWriteState;
 import org.apache.lucene.index.Term;
 import org.apache.lucene.search.IndexSearcher;
 import org.apache.lucene.search.Query;
 import org.apache.lucene.search.SimpleCollector;
+import org.apache.lucene.spatial3d.geom.GeoArea;
+import org.apache.lucene.spatial3d.geom.GeoAreaFactory;
+import org.apache.lucene.spatial3d.geom.GeoBBoxFactory;
+import org.apache.lucene.spatial3d.geom.GeoCircleFactory;
+import org.apache.lucene.spatial3d.geom.GeoPathFactory;
+import org.apache.lucene.spatial3d.geom.GeoPoint;
+import org.apache.lucene.spatial3d.geom.GeoPolygon;
+import org.apache.lucene.spatial3d.geom.GeoPolygonFactory;
+import org.apache.lucene.spatial3d.geom.GeoShape;
+import org.apache.lucene.spatial3d.geom.Plane;
+import org.apache.lucene.spatial3d.geom.PlanetModel;
+import org.apache.lucene.spatial3d.geom.SidedPlane;
+import org.apache.lucene.spatial3d.geom.XYZBounds;
 import org.apache.lucene.store.Directory;
-import org.apache.lucene.geo.Polygon;
+import org.apache.lucene.util.DocIdSetBuilder;
 import org.apache.lucene.util.FixedBitSet;
 import org.apache.lucene.util.IOUtils;
 import org.apache.lucene.util.LuceneTestCase;
+import org.apache.lucene.util.NumericUtils;
+import org.apache.lucene.util.StringHelper;
 import org.apache.lucene.util.TestUtil;
-import org.junit.BeforeClass;
 import org.junit.Ignore;
 
 import com.carrotsearch.randomizedtesting.generators.RandomInts;
 
 public class TestGeo3DPoint extends LuceneTestCase {
 
-  private static boolean smallBBox;
-  
-  @BeforeClass
-  public static void beforeClass() {
-    smallBBox = random().nextBoolean();
-    if (VERBOSE) {
-      System.err.println("TEST: smallBBox=" + smallBBox);
-    }
-  }
-
   private static Codec getCodec() {
     if (Codec.getDefault().getName().equals("Lucene60")) {
       int maxPointsInLeafNode = TestUtil.nextInt(random(), 16, 2048);
@@ -133,22 +129,7 @@ public class TestGeo3DPoint extends LuceneTestCase {
   }
 
   private static double toRadians(double degrees) {
-    return Math.PI*(degrees/180.0);
-  }
-
-  private static PlanetModel getPlanetModel() {
-    if (random().nextBoolean()) {
-      // Use one of the earth models:
-      if (random().nextBoolean()) {
-        return PlanetModel.WGS84;
-      } else {
-        return PlanetModel.SPHERE;
-      }
-    } else {
-      // Make a randomly squashed planet:
-      double oblateness = random().nextDouble() * 0.5 - 0.25;
-      return new PlanetModel(1.0 + oblateness, 1.0 - oblateness);
-    }
+    return Math.toRadians(degrees);
   }
 
   private static class Cell {
@@ -178,10 +159,10 @@ public class TestGeo3DPoint extends LuceneTestCase {
     }
 
     /** Returns true if the quantized point lies within this cell, inclusive on all bounds. */
-    public boolean contains(double planetMax, GeoPoint point) {
-      int docX = Geo3DUtil.encodeValue(planetMax, point.x);
-      int docY = Geo3DUtil.encodeValue(planetMax, point.y);
-      int docZ = Geo3DUtil.encodeValue(planetMax, point.z);
+    public boolean contains(GeoPoint point) {
+      int docX = Geo3DUtil.encodeValue(point.x);
+      int docY = Geo3DUtil.encodeValue(point.y);
+      int docZ = Geo3DUtil.encodeValue(point.z);
 
       return docX >= xMinEnc && docX <= xMaxEnc &&
         docY >= yMinEnc && docY <= yMaxEnc && 
@@ -194,17 +175,17 @@ public class TestGeo3DPoint extends LuceneTestCase {
     }
   }
 
-  private static GeoPoint quantize(double planetMax, GeoPoint point) {
-    return new GeoPoint(Geo3DUtil.decodeValueCenter(planetMax, Geo3DUtil.encodeValue(planetMax, point.x)),
-                        Geo3DUtil.decodeValueCenter(planetMax, Geo3DUtil.encodeValue(planetMax, point.y)),
-                        Geo3DUtil.decodeValueCenter(planetMax, Geo3DUtil.encodeValue(planetMax, point.z)));
+  private static double quantize(double xyzValue) {
+    return Geo3DUtil.decodeValue(Geo3DUtil.encodeValue(xyzValue));
+  }
+
+  private static GeoPoint quantize(GeoPoint point) {
+    return new GeoPoint(quantize(point.x), quantize(point.y), quantize(point.z));
   }
 
   /** Tests consistency of GeoArea.getRelationship vs GeoShape.isWithin */
   public void testGeo3DRelations() throws Exception {
 
-    PlanetModel planetModel = getPlanetModel();
-
     int numDocs = atLeast(1000);
     if (VERBOSE) {
       System.out.println("TEST: " + numDocs + " docs");
@@ -212,14 +193,12 @@ public class TestGeo3DPoint extends LuceneTestCase {
 
     GeoPoint[] docs = new GeoPoint[numDocs];
     for(int docID=0;docID<numDocs;docID++) {
-      docs[docID] = new GeoPoint(planetModel, toRadians(randomLat()), toRadians(randomLon()));
+      docs[docID] = quantize(new GeoPoint(PlanetModel.WGS84, toRadians(GeoTestUtil.nextLatitude()), toRadians(GeoTestUtil.nextLongitude())));
       if (VERBOSE) {
         System.out.println("  doc=" + docID + ": " + docs[docID]);
       }
     }
 
-    double planetMax = planetModel.getMaximumMagnitude();
-
     int iters = atLeast(10);
 
     int recurseDepth = RandomInts.randomIntBetween(random(), 5, 15);
@@ -227,7 +206,7 @@ public class TestGeo3DPoint extends LuceneTestCase {
     iters = atLeast(50);
     
     for(int iter=0;iter<iters;iter++) {
-      GeoShape shape = randomShape(planetModel);
+      GeoShape shape = randomShape();
 
       StringWriter sw = new StringWriter();
       PrintWriter log = new PrintWriter(sw, true);
@@ -241,12 +220,12 @@ public class TestGeo3DPoint extends LuceneTestCase {
 
       // Start with the root cell that fully contains the shape:
       Cell root = new Cell(null,
-                           Geo3DUtil.encodeValueLenient(planetMax, bounds.getMinimumX()),
-                           Geo3DUtil.encodeValueLenient(planetMax, bounds.getMaximumX()),
-                           Geo3DUtil.encodeValueLenient(planetMax, bounds.getMinimumY()),
-                           Geo3DUtil.encodeValueLenient(planetMax, bounds.getMaximumY()),
-                           Geo3DUtil.encodeValueLenient(planetMax, bounds.getMinimumZ()),
-                           Geo3DUtil.encodeValueLenient(planetMax, bounds.getMaximumZ()),
+                           encodeValueLenient(bounds.getMinimumX()),
+                           encodeValueLenient(bounds.getMaximumX()),
+                           encodeValueLenient(bounds.getMinimumY()),
+                           encodeValueLenient(bounds.getMaximumY()),
+                           encodeValueLenient(bounds.getMinimumZ()),
+                           encodeValueLenient(bounds.getMaximumZ()),
                            0);
 
       if (VERBOSE) {
@@ -271,8 +250,8 @@ public class TestGeo3DPoint extends LuceneTestCase {
           // Leaf cell: brute force check all docs that fall within this cell:
           for(int docID=0;docID<numDocs;docID++) {
             GeoPoint point = docs[docID];
-            if (cell.contains(planetMax, point)) {
-              if (shape.isWithin(quantize(planetMax, point))) {
+            if (cell.contains(point)) {
+              if (shape.isWithin(point)) {
                 if (VERBOSE) {
                   log.println("    check doc=" + docID + ": match!");
                 }
@@ -286,15 +265,15 @@ public class TestGeo3DPoint extends LuceneTestCase {
           }
         } else {
           
-          GeoArea xyzSolid = GeoAreaFactory.makeGeoArea(planetModel,
-                                                        Geo3DUtil.decodeValueMin(planetMax, cell.xMinEnc), Geo3DUtil.decodeValueMax(planetMax, cell.xMaxEnc),
-                                                        Geo3DUtil.decodeValueMin(planetMax, cell.yMinEnc), Geo3DUtil.decodeValueMax(planetMax, cell.yMaxEnc),
-                                                        Geo3DUtil.decodeValueMin(planetMax, cell.zMinEnc), Geo3DUtil.decodeValueMax(planetMax, cell.zMaxEnc));
+          GeoArea xyzSolid = GeoAreaFactory.makeGeoArea(PlanetModel.WGS84,
+                                                        PointInShapeIntersectVisitor.decodeValueMin(cell.xMinEnc), PointInShapeIntersectVisitor.decodeValueMax(cell.xMaxEnc),
+                                                        PointInShapeIntersectVisitor.decodeValueMin(cell.yMinEnc), PointInShapeIntersectVisitor.decodeValueMax(cell.yMaxEnc),
+                                                        PointInShapeIntersectVisitor.decodeValueMin(cell.zMinEnc), PointInShapeIntersectVisitor.decodeValueMax(cell.zMaxEnc));
 
           if (VERBOSE) {
-            log.println("    minx="+Geo3DUtil.decodeValueMin(planetMax, cell.xMinEnc)+" maxx="+Geo3DUtil.decodeValueMax(planetMax, cell.xMaxEnc)+
-              " miny="+Geo3DUtil.decodeValueMin(planetMax, cell.yMinEnc)+" maxy="+Geo3DUtil.decodeValueMax(planetMax, cell.yMaxEnc)+
-              " minz="+Geo3DUtil.decodeValueMin(planetMax, cell.zMinEnc)+" maxz="+Geo3DUtil.decodeValueMax(planetMax, cell.zMaxEnc));
+            log.println("    minx="+PointInShapeIntersectVisitor.decodeValueMin(cell.xMinEnc)+" maxx="+PointInShapeIntersectVisitor.decodeValueMax(cell.xMaxEnc)+
+              " miny="+PointInShapeIntersectVisitor.decodeValueMin(cell.yMinEnc)+" maxy="+PointInShapeIntersectVisitor.decodeValueMax(cell.yMaxEnc)+
+              " minz="+PointInShapeIntersectVisitor.decodeValueMin(cell.zMinEnc)+" maxz="+PointInShapeIntersectVisitor.decodeValueMax(cell.zMaxEnc));
           }
 
           switch (xyzSolid.getRelationship(shape)) {          
@@ -304,7 +283,7 @@ public class TestGeo3DPoint extends LuceneTestCase {
               log.println("    GeoArea.CONTAINS: now addAll");
             }
             for(int docID=0;docID<numDocs;docID++) {
-              if (cell.contains(planetMax, docs[docID])) {
+              if (cell.contains(docs[docID])) {
                 if (VERBOSE) {
                   log.println("    addAll doc=" + docID);
                 }
@@ -332,7 +311,7 @@ public class TestGeo3DPoint extends LuceneTestCase {
             if (VERBOSE) {
               log.println("    GeoArea.DISJOINT: drop this cell");
               for(int docID=0;docID<numDocs;docID++) {
-                if (cell.contains(planetMax, docs[docID])) {
+                if (cell.contains(docs[docID])) {
                   if (VERBOSE) {
                     log.println("    skip doc=" + docID);
                   }
@@ -436,23 +415,15 @@ public class TestGeo3DPoint extends LuceneTestCase {
       boolean fail = false;
       for(int docID=0;docID<numDocs;docID++) {
         GeoPoint point = docs[docID];
-        GeoPoint quantized = quantize(planetMax, point);
-        boolean expected = shape.isWithin(quantized);
-
-        if (expected != shape.isWithin(point)) {
-          // Quantization changed the result; skip testing this doc:
-          continue;
-        }
-
+        boolean expected = shape.isWithin(point);
         boolean actual = hits.contains(docID);
         if (actual != expected) {
           if (actual) {
-            log.println("doc=" + docID + " matched but should not");
+            log.println("doc=" + docID + " should not have matched but did");
           } else {
-            log.println("doc=" + docID + " did not match but should");
+            log.println("doc=" + docID + " should match but did not");
           }
           log.println("  point=" + docs[docID]);
-          log.println("  quantized=" + quantize(planetMax, docs[docID]));
           fail = true;
         }
       }
@@ -513,13 +484,13 @@ public class TestGeo3DPoint extends LuceneTestCase {
         if (x == 0) {
           // Identical lat to old point
           lats[docID] = lats[oldDocID];
-          lons[docID] = randomLon();
+          lons[docID] = GeoTestUtil.nextLongitude();
           if (VERBOSE) {
             System.err.println("  doc=" + docID + " lat=" + lats[docID] + " lon=" + lons[docID] + " (same lat as doc=" + oldDocID + ")");
           }
         } else if (x == 1) {
           // Identical lon to old point
-          lats[docID] = randomLat();
+          lats[docID] = GeoTestUtil.nextLatitude();
           lons[docID] = lons[oldDocID];
           if (VERBOSE) {
             System.err.println("  doc=" + docID + " lat=" + lats[docID] + " lon=" + lons[docID] + " (same lon as doc=" + oldDocID + ")");
@@ -534,8 +505,8 @@ public class TestGeo3DPoint extends LuceneTestCase {
           }
         }
       } else {
-        lats[docID] = randomLat();
-        lons[docID] = randomLon();
+        lats[docID] = GeoTestUtil.nextLatitude();
+        lons[docID] = GeoTestUtil.nextLongitude();
         haveRealDoc = true;
         if (VERBOSE) {
           System.err.println("  doc=" + docID + " lat=" + lats[docID] + " lon=" + lons[docID]);
@@ -546,24 +517,8 @@ public class TestGeo3DPoint extends LuceneTestCase {
     verify(lats, lons);
   }
 
-  private static double randomLat() {
-    if (smallBBox) {
-      return 2.0 * (random().nextDouble()-0.5);
-    } else {
-      return -90 + 180.0 * random().nextDouble();
-    }
-  }
-
-  private static double randomLon() {
-    if (smallBBox) {
-      return 2.0 * (random().nextDouble()-0.5);
-    } else {
-      return -180 + 360.0 * random().nextDouble();
-    }
-  }
-
   // Poached from Geo3dRptTest.randomShape:
-  private static GeoShape randomShape(PlanetModel planetModel) {
+  private static GeoShape randomShape() {
     while (true) {
       final int shapeType = random().nextInt(4);
       switch (shapeType) {
@@ -572,12 +527,12 @@ public class TestGeo3DPoint extends LuceneTestCase {
         final int vertexCount = random().nextInt(3) + 3;
         final List<GeoPoint> geoPoints = new ArrayList<>();
         while (geoPoints.size() < vertexCount) {
-          final GeoPoint gPt = new GeoPoint(planetModel, toRadians(randomLat()), toRadians(randomLon()));
+          final GeoPoint gPt = new GeoPoint(PlanetModel.WGS84, toRadians(GeoTestUtil.nextLatitude()), toRadians(GeoTestUtil.nextLongitude()));
           geoPoints.add(gPt);
         }
         final int convexPointIndex = random().nextInt(vertexCount);       //If we get this wrong, hopefully we get IllegalArgumentException
         try {
-          return GeoPolygonFactory.makeGeoPolygon(planetModel, geoPoints, convexPointIndex);
+          return GeoPolygonFactory.makeGeoPolygon(PlanetModel.WGS84, geoPoints, convexPointIndex);
         } catch (IllegalArgumentException e) {
           // This is what happens when we create a shape that is invalid.  Although it is conceivable that there are cases where
           // the exception is thrown incorrectly, we aren't going to be able to do that in this random test.
@@ -588,18 +543,13 @@ public class TestGeo3DPoint extends LuceneTestCase {
       case 1: {
         // Circles
 
-        double lat = toRadians(randomLat());
-        double lon = toRadians(randomLon());
+        double lat = toRadians(GeoTestUtil.nextLatitude());
+        double lon = toRadians(GeoTestUtil.nextLongitude());
 
-        double angle;
-        if (smallBBox) {
-          angle = random().nextDouble() * Math.PI/360.0;
-        } else {
-          angle = random().nextDouble() * Math.PI/2.0;
-        }
+        double angle = random().nextDouble() * Math.PI/2.0;
 
         try {
-          return GeoCircleFactory.makeGeoCircle(planetModel, lat, lon, angle);
+          return GeoCircleFactory.makeGeoCircle(PlanetModel.WGS84, lat, lon, angle);
         } catch (IllegalArgumentException iae) {
           // angle is too small; try again:
           continue;
@@ -608,22 +558,22 @@ public class TestGeo3DPoint extends LuceneTestCase {
 
       case 2: {
         // Rectangles
-        double lat0 = toRadians(randomLat());
-        double lat1 = toRadians(randomLat());
+        double lat0 = toRadians(GeoTestUtil.nextLatitude());
+        double lat1 = toRadians(GeoTestUtil.nextLatitude());
         if (lat1 < lat0) {
           double x = lat0;
           lat0 = lat1;
           lat1 = x;
         }
-        double lon0 = toRadians(randomLon());
-        double lon1 = toRadians(randomLon());
+        double lon0 = toRadians(GeoTestUtil.nextLongitude());
+        double lon1 = toRadians(GeoTestUtil.nextLongitude());
         if (lon1 < lon0) {
           double x = lon0;
           lon0 = lon1;
           lon1 = x;
         }
 
-        return GeoBBoxFactory.makeGeoBBox(planetModel, lat1, lat0, lon0, lon1);
+        return GeoBBoxFactory.makeGeoBBox(PlanetModel.WGS84, lat1, lat0, lon0, lon1);
       }
 
       case 3: {
@@ -632,10 +582,10 @@ public class TestGeo3DPoint extends LuceneTestCase {
         final double width = toRadians(random().nextInt(89)+1);
         final GeoPoint[] points = new GeoPoint[pointCount];
         for (int i = 0; i < pointCount; i++) {
-          points[i] = new GeoPoint(planetModel, toRadians(randomLat()), toRadians(randomLon()));
+          points[i] = new GeoPoint(PlanetModel.WGS84, toRadians(GeoTestUtil.nextLatitude()), toRadians(GeoTestUtil.nextLongitude()));
         }
         try {
-          return GeoPathFactory.makeGeoPath(planetModel, width, points);
+          return GeoPathFactory.makeGeoPath(PlanetModel.WGS84, width, points);
         } catch (IllegalArgumentException e) {
           // This is what happens when we create a shape that is invalid.  Although it is conceivable that there are cases where
           // the exception is thrown incorrectly, we aren't going to be able to do that in this random test.
@@ -652,14 +602,24 @@ public class TestGeo3DPoint extends LuceneTestCase {
   private static void verify(double[] lats, double[] lons) throws Exception {
     IndexWriterConfig iwc = newIndexWriterConfig();
 
+    GeoPoint[] points = new GeoPoint[lats.length];
+
+    // Pre-quantize all lat/lons:
+    for(int i=0;i<lats.length;i++) {
+      if (Double.isNaN(lats[i]) == false) {
+        //System.out.println("lats[" + i + "] = " + lats[i]);
+        points[i] = quantize(new GeoPoint(PlanetModel.WGS84, toRadians(lats[i]), toRadians(lons[i])));
+      }
+    }
+
     // Else we can get O(N^2) merging:
     int mbd = iwc.getMaxBufferedDocs();
-    if (mbd != -1 && mbd < lats.length/100) {
-      iwc.setMaxBufferedDocs(lats.length/100);
+    if (mbd != -1 && mbd < points.length/100) {
+      iwc.setMaxBufferedDocs(points.length/100);
     }
     iwc.setCodec(getCodec());
     Directory dir;
-    if (lats.length > 100000) {
+    if (points.length > 100000) {
       dir = newFSDirectory(createTempDir("TestBKDTree"));
     } else {
       dir = getDirectory();
@@ -667,12 +627,13 @@ public class TestGeo3DPoint extends LuceneTestCase {
     Set<Integer> deleted = new HashSet<>();
     // RandomIndexWriter is too slow here:
     IndexWriter w = new IndexWriter(dir, iwc);
-    for(int id=0;id<lats.length;id++) {
+    for(int id=0;id<points.length;id++) {
       Document doc = new Document();
       doc.add(newStringField("id", ""+id, Field.Store.NO));
       doc.add(new NumericDocValuesField("id", id));
-      if (Double.isNaN(lats[id]) == false) {
-        doc.add(new Geo3DPoint("point", lats[id], lons[id]));
+      GeoPoint point = points[id];
+      if (point != null) {
+        doc.add(new Geo3DPoint("point", point.x, point.y, point.z));
       }
       w.addDocument(doc);
       if (id > 0 && random().nextInt(100) == 42) {
@@ -688,119 +649,89 @@ public class TestGeo3DPoint extends LuceneTestCase {
       w.forceMerge(1);
     }
     final IndexReader r = DirectoryReader.open(w);
+    if (VERBOSE) {
+      System.out.println("TEST: using reader " + r);
+    }
     w.close();
 
     // We can't wrap with "exotic" readers because the geo3d query must see the Geo3DDVFormat:
     IndexSearcher s = newSearcher(r, false);
 
-    int numThreads = TestUtil.nextInt(random(), 2, 5);
-
-    List<Thread> threads = new ArrayList<>();
     final int iters = atLeast(100);
 
-    final CountDownLatch startingGun = new CountDownLatch(1);
-    final AtomicBoolean failed = new AtomicBoolean();
-
-    for(int i=0;i<numThreads;i++) {
-      Thread thread = new Thread() {
-          @Override
-          public void run() {
-            try {
-              _run();
-            } catch (Exception e) {
-              failed.set(true);
-              throw new RuntimeException(e);
-            }
-          }
-
-          private void _run() throws Exception {
-            startingGun.await();
+    NumericDocValues docIDToID = MultiDocValues.getNumericValues(r, "id");
 
-            NumericDocValues docIDToID = MultiDocValues.getNumericValues(r, "id");
+    for (int iter=0;iter<iters;iter++) {
 
-            for (int iter=0;iter<iters && failed.get() == false;iter++) {
+      GeoShape shape = randomShape();
 
-              GeoShape shape = randomShape(PlanetModel.WGS84);
-
-              if (VERBOSE) {
-                System.err.println("\n" + Thread.currentThread() + ": TEST: iter=" + iter + " shape="+shape);
-              }
+      if (VERBOSE) {
+        System.err.println("\nTEST: iter=" + iter + " shape="+shape);
+      }
               
-              Query query = Geo3DPoint.newShapeQuery("point", shape);
+      Query query = Geo3DPoint.newShapeQuery("point", shape);
 
-              if (VERBOSE) {
-                System.err.println("  using query: " + query);
-              }
+      if (VERBOSE) {
+        System.err.println("  using query: " + query);
+      }
 
-              final FixedBitSet hits = new FixedBitSet(r.maxDoc());
+      final FixedBitSet hits = new FixedBitSet(r.maxDoc());
 
-              s.search(query, new SimpleCollector() {
+      s.search(query, new SimpleCollector() {
 
-                  private int docBase;
+          private int docBase;
 
-                  @Override
-                  public boolean needsScores() {
-                    return false;
-                  }
+          @Override
+          public boolean needsScores() {
+            return false;
+          }
 
-                  @Override
-                  protected void doSetNextReader(LeafReaderContext context) throws IOException {
-                    docBase = context.docBase;
-                  }
+          @Override
+          protected void doSetNextReader(LeafReaderContext context) throws IOException {
+            docBase = context.docBase;
+          }
 
-                  @Override
-                  public void collect(int doc) {
-                    hits.set(docBase+doc);
-                  }
-                });
+          @Override
+          public void collect(int doc) {
+            hits.set(docBase+doc);
+          }
+        });
 
-              if (VERBOSE) {
-                System.err.println("  hitCount: " + hits.cardinality());
-              }
+      if (VERBOSE) {
+        System.err.println("  hitCount: " + hits.cardinality());
+      }
       
-              for(int docID=0;docID<r.maxDoc();docID++) {
-                int id = (int) docIDToID.get(docID);
-                if (Double.isNaN(lats[id]) == false) {
-
-                  // Accurate point:
-                  GeoPoint point1 = new GeoPoint(PlanetModel.WGS84, toRadians(lats[id]), toRadians(lons[id]));
-
-                  // Quantized point (32 bits per dim):
-                  GeoPoint point2 = quantize(PlanetModel.WGS84.getMaximumMagnitude(), point1);
-
-                  if (shape.isWithin(point1) != shape.isWithin(point2)) {
-                    if (VERBOSE) {
-                      System.out.println("  skip checking docID=" + docID + " quantization changed the expected result from " + shape.isWithin(point1) + " to " + shape.isWithin(point2));
-                    }
-                    continue;
-                  }
-
-                  boolean expected = ((deleted.contains(id) == false) && shape.isWithin(point2));
-                  if (hits.get(docID) != expected) {
-                    fail(Thread.currentThread().getName() + ": iter=" + iter + " id=" + id + " docID=" + docID + " lat=" + lats[id] + " lon=" + lons[id] + " expected " + expected + " but got: " + hits.get(docID) + " deleted?=" + deleted.contains(id) + "\n  point1=" + point1 + ", iswithin="+shape.isWithin(point1)+"\n  point2=" + point2 + ", iswithin="+shape.isWithin(point2) + "\n  query=" + query);
-                  }
-                } else {
-                  assertFalse(hits.get(docID));
-                }
-
-              }
+      for(int docID=0;docID<r.maxDoc();docID++) {
+        int id = (int) docIDToID.get(docID);
+        GeoPoint point = points[id];
+        if (point != null) {
+          boolean expected = ((deleted.contains(id) == false) && shape.isWithin(point));
+          if (hits.get(docID) != expected) {
+            StringBuilder b = new StringBuilder();
+            if (expected) {
+              b.append("FAIL: id=" + id + " should have matched but did not\n");
+            } else {
+              b.append("FAIL: id=" + id + " should not have matched but did\n");
             }
+            b.append("  shape=" + shape + "\n");
+            b.append("  point=" + point + "\n");
+            b.append("  docID=" + docID + " deleted?=" + deleted.contains(id) + "\n");
+            b.append("  query=" + query + "\n");
+            b.append("  explanation:\n    " + explain("point", shape, r, docID).replace("\n", "\n  "));
+            fail(b.toString());
           }
-        };
-      thread.setName("T" + i);
-      thread.start();
-      threads.add(thread);
-    }
-    startingGun.countDown();
-    for(Thread thread : threads) {
-      thread.join();
+        } else {
+          assertFalse(hits.get(docID));
+        }
+      }
     }
+
     IOUtils.close(r, dir);
   }
 
   public void testToString() {
     Geo3DPoint point = new Geo3DPoint("point", 44.244272, 7.769736);
-    assertEquals("Geo3DPoint <point: x=0.709426313149037 y=0.09679758908863707 z=0.6973564619509093>", point.toString());
+    assertEquals("Geo3DPoint <point: x=0.7094263127744131 y=0.09679758888428691 z=0.6973564619016113>", point.toString());
   }
 
   public void testShapeQueryToString() {
@@ -813,7 +744,7 @@ public class TestGeo3DPoint extends LuceneTestCase {
   }
 
   public void testEquals() {
-    GeoShape shape = randomShape(PlanetModel.WGS84);
+    GeoShape shape = randomShape();
     Query q = Geo3DPoint.newShapeQuery("point", shape);
     assertEquals(q, Geo3DPoint.newShapeQuery("point", shape));
     assertFalse(q.equals(Geo3DPoint.newShapeQuery("point2", shape)));
@@ -821,7 +752,7 @@ public class TestGeo3DPoint extends LuceneTestCase {
     // make a different random shape:
     GeoShape shape2;
     do {
-      shape2 = randomShape(PlanetModel.WGS84);
+      shape2 = randomShape();
     } while (shape.equals(shape2));
 
     assertFalse(q.equals(Geo3DPoint.newShapeQuery("point", shape2)));
@@ -830,12 +761,11 @@ public class TestGeo3DPoint extends LuceneTestCase {
   public void testComplexPolygons() {
     final PlanetModel pm = PlanetModel.WGS84;
     // Pick a random pole
-    final GeoPoint randomPole = new GeoPoint(pm, Math.toRadians(randomLat()), Math.toRadians(randomLon()));
+    final GeoPoint randomPole = new GeoPoint(pm, Math.toRadians(GeoTestUtil.nextLatitude()), Math.toRadians(GeoTestUtil.nextLongitude()));
     // Create a polygon that's less than 180 degrees
     final Polygon clockWise = makePoly(pm, randomPole, true, true);
     // Create a polygon that's greater than 180 degrees
     final Polygon counterClockWise = makePoly(pm, randomPole, false, true);
-    
   }
   
   protected static double MINIMUM_EDGE_ANGLE = Math.toRadians(5.0);
@@ -911,7 +841,7 @@ public class TestGeo3DPoint extends LuceneTestCase {
         // Choose a pole.  The poly has to be within the polygon, but it also cannot be on the polygon edge.
         // If we can't find a good pole we have to give it up and not do the hole.
         for (int k = 0; k < 500; k++) {
-          final GeoPoint poleChoice = new GeoPoint(pm, toRadians(randomLat()), toRadians(randomLon()));
+          final GeoPoint poleChoice = new GeoPoint(pm, toRadians(GeoTestUtil.nextLatitude()), toRadians(GeoTestUtil.nextLongitude()));
           if (!poly.isWithin(poleChoice)) {
             continue;
           }
@@ -1053,4 +983,316 @@ public class TestGeo3DPoint extends LuceneTestCase {
     }
     return index;
   }
+
+  public void testEncodeDecodeCeil() throws Exception {
+
+    // just for testing quantization error
+    final double ENCODING_TOLERANCE = Geo3DUtil.DECODE;
+
+    int iters = atLeast(10000);
+    for(int iter=0;iter<iters;iter++) {
+      GeoPoint point = new GeoPoint(PlanetModel.WGS84, toRadians(GeoTestUtil.nextLatitude()), toRadians(GeoTestUtil.nextLongitude()));
+      double xEnc = Geo3DUtil.decodeValue(Geo3DUtil.encodeValue(point.x));
+      assertEquals("x=" + point.x + " xEnc=" + xEnc + " diff=" + (point.x - xEnc), point.x, xEnc, ENCODING_TOLERANCE);
+
+      double yEnc = Geo3DUtil.decodeValue(Geo3DUtil.encodeValue(point.y));
+      assertEquals("y=" + point.y + " yEnc=" + yEnc + " diff=" + (point.y - yEnc), point.y, yEnc, ENCODING_TOLERANCE);
+
+      double zEnc = Geo3DUtil.decodeValue(Geo3DUtil.encodeValue(point.z));
+      assertEquals("z=" + point.z + " zEnc=" + zEnc + " diff=" + (point.z - zEnc), point.z, zEnc, ENCODING_TOLERANCE);
+    }
+
+    // check edge/interesting cases explicitly
+    double planetMax = PlanetModel.WGS84.getMaximumMagnitude();
+    for (double value : new double[] {0.0, -planetMax, planetMax}) {
+      assertEquals(value, Geo3DUtil.decodeValue(Geo3DUtil.encodeValue(value)), ENCODING_TOLERANCE);
+    }
+  }
+
+  /** make sure values always go down: this is important for edge case consistency */
+  public void testEncodeDecodeRoundsDown() throws Exception {
+
+    int iters = atLeast(1000);
+    for(int iter=0;iter<iters;iter++) {
+      final double latBase = GeoTestUtil.nextLatitude();
+      final double lonBase = GeoTestUtil.nextLongitude();
+
+      // test above the value
+      double lat = latBase;
+      double lon = lonBase;
+      for (int i = 0; i < 1000; i++) {
+        lat = Math.min(90, Math.nextUp(lat));
+        lon = Math.min(180, Math.nextUp(lon));
+        GeoPoint point = new GeoPoint(PlanetModel.WGS84, toRadians(lat), toRadians(lon));
+        GeoPoint pointEnc = new GeoPoint(PointInShapeIntersectVisitor.decodeValueMin(Geo3DUtil.encodeValue(point.x)),
+                                         PointInShapeIntersectVisitor.decodeValueMin(Geo3DUtil.encodeValue(point.y)),
+                                         PointInShapeIntersectVisitor.decodeValueMin(Geo3DUtil.encodeValue(point.z)));
+        assertTrue(pointEnc.x <= point.x);
+        assertTrue(pointEnc.y <= point.y);
+        assertTrue(pointEnc.z <= point.z);
+      }
+
+      // test below the value
+      lat = latBase;
+      lon = lonBase;
+      for (int i = 0; i < 1000; i++) {
+        lat = Math.max(-90, Math.nextDown(lat));
+        lon = Math.max(-180, Math.nextDown(lon));
+        GeoPoint point = new GeoPoint(PlanetModel.WGS84, toRadians(lat), toRadians(lon));
+        GeoPoint pointEnc = new GeoPoint(PointInShapeIntersectVisitor.decodeValueMin(Geo3DUtil.encodeValue(point.x)),
+                                         PointInShapeIntersectVisitor.decodeValueMin(Geo3DUtil.encodeValue(point.y)),
+                                         PointInShapeIntersectVisitor.decodeValueMin(Geo3DUtil.encodeValue(point.z)));
+        assertTrue(pointEnc.x <= point.x);
+        assertTrue(pointEnc.y <= point.y);
+        assertTrue(pointEnc.z <= point.z);
+      }
+    }
+  }
+
+  public void testEncodeDecodeIsStable() throws Exception {
+
+    int iters = atLeast(1000);
+    for(int iter=0;iter<iters;iter++) {
+      double lat = GeoTestUtil.nextLatitude();
+      double lon = GeoTestUtil.nextLongitude();
+
+      GeoPoint point = new GeoPoint(PlanetModel.WGS84, toRadians(lat), toRadians(lon));
+
+      // encode point
+      GeoPoint pointEnc = new GeoPoint(Geo3DUtil.decodeValue(Geo3DUtil.encodeValue(point.x)),
+                                       Geo3DUtil.decodeValue(Geo3DUtil.encodeValue(point.y)),
+                                       Geo3DUtil.decodeValue(Geo3DUtil.encodeValue(point.z)));
+
+      // encode it again (double encode)
+      GeoPoint pointEnc2 = new GeoPoint(Geo3DUtil.decodeValue(Geo3DUtil.encodeValue(pointEnc.x)),
+                                        Geo3DUtil.decodeValue(Geo3DUtil.encodeValue(pointEnc.y)),
+                                        Geo3DUtil.decodeValue(Geo3DUtil.encodeValue(pointEnc.z)));
+      //System.out.println("TEST " + iter + ":\n  point    =" + point + "\n  pointEnc =" + pointEnc + "\n  pointEnc2=" + pointEnc2);
+    
+      assertEquals(pointEnc.x, pointEnc2.x, 0.0);
+      assertEquals(pointEnc.y, pointEnc2.y, 0.0);
+      assertEquals(pointEnc.z, pointEnc2.z, 0.0);
+    }
+  }
+
+  // Takes ~35 seconds on modern-ish 2015 dev box:
+  @Nightly
+  public void testEncodeIsStableFromIntSide() throws Exception {
+    double max = PlanetModel.WGS84.getMaximumMagnitude();
+
+    // We can't test the full space of ints (Integer.MIN_VALUE to Integer.MAX_VALUE) because not all ints are allowed:
+    int start = Geo3DUtil.encodeValue(-max);
+    int end = Geo3DUtil.encodeValue(max);
+    // This prints: 99.99997175764292
+    //System.out.println("PCTG INT SPACE USED: " + 100.*(((long) end)-(long) start)/(1L<<32));
+    for (int i=start;i<=end;i++) {
+      double x = Geo3DUtil.decodeValue(i);
+      assertEquals(i, Geo3DUtil.encodeValue(x));
+      if (i > start+1) {
+        assertEquals(Geo3DUtil.DECODE, x - Geo3DUtil.decodeValue(i-1), 0.0d);
+      }
+    }
+  }
+
+  /** Clips the incoming value to the allowed min/max range before encoding, instead of throwing an exception. */
+  private static int encodeValueLenient(double x) {
+    double planetMax = PlanetModel.WGS84.getMaximumMagnitude();
+    if (x > planetMax) {
+      x = planetMax;
+    } else if (x < -planetMax) {
+      x = -planetMax;
+    }
+    return Geo3DUtil.encodeValue(x);
+  }
+
+  private static class ExplainingVisitor implements IntersectVisitor {
+
+    final IntersectVisitor in;
+    final List<Cell> stack = new ArrayList<>();
+    private List<Cell> stackToTargetDoc;
+    final int targetDocID;
+    final int numDims;
+    final int bytesPerDim;
+    private int targetStackUpto;
+    final StringBuilder b;
+
+    // In the first phase, we always return CROSSES to do a full scan of the BKD tree to see which leaf block the document lives in
+    boolean firstPhase = true;
+
+    public ExplainingVisitor(IntersectVisitor in, int targetDocID, int numDims, int bytesPerDim, StringBuilder b) {
+      this.in = in;
+      this.targetDocID = targetDocID;
+      this.numDims = numDims;
+      this.bytesPerDim = bytesPerDim;
+      this.b = b;
+    }
+
+    public void startSecondPhase() {
+      if (firstPhase == false) {
+        throw new IllegalStateException("already started second phase");
+      }
+      if (stackToTargetDoc == null) {
+        b.append("target docID=" + targetDocID + " was never seen in points!\n");
+      }
+      firstPhase = false;
+      stack.clear();
+    }
+
+    @Override
+    public void visit(int docID) throws IOException {
+      assert firstPhase == false;
+      if (docID == targetDocID) {
+        b.append("leaf visit docID=" + docID + "\n");
+      }
+    }
+
+    @Override
+    public void visit(int docID, byte[] packedValue) throws IOException {
+      if (firstPhase) {
+        if (docID == targetDocID) {
+          assert stackToTargetDoc == null;
+          stackToTargetDoc = new ArrayList<>(stack);
+          b.append("  full BKD path to target doc:\n");
+          for(Cell cell : stack) {
+            b.append("    " + cell + "\n");
+          }
+        }
+      } else {
+        if (docID == targetDocID) {
+          double x = Geo3DPoint.decodeDimension(packedValue, 0);
+          double y = Geo3DPoint.decodeDimension(packedValue, Integer.BYTES);
+          double z = Geo3DPoint.decodeDimension(packedValue, 2 * Integer.BYTES);
+          b.append("leaf visit docID=" + docID + " x=" + x + " y=" + y + " z=" + z + "\n");
+          in.visit(docID, packedValue);
+        }
+      }
+    }
+
+    @Override
+    public Relation compare(byte[] minPackedValue, byte[] maxPackedValue) {
+      Cell cell = new Cell(minPackedValue, maxPackedValue);
+      //System.out.println("compare: " + cell);
+
+      // TODO: this is a bit hacky, having to reverse-engineer where we are in the BKD tree's recursion ... but it's the lesser evil vs e.g.
+      // polluting this visitor API, or implementing this "under the hood" in BKDReader instead?
+      if (firstPhase) {
+
+        // Pop stack:
+        while (stack.size() > 0 && stack.get(stack.size()-1).contains(cell)) {
+          stack.remove(stack.size()-1);
+          //System.out.println("  pop");
+        }
+
+        // Push stack:
+        stack.add(cell);
+        //System.out.println("  push");
+
+        return Relation.CELL_CROSSES_QUERY;
+      } else {
+        Relation result = in.compare(minPackedValue, maxPackedValue);
+        if (targetStackUpto < stackToTargetDoc.size() && cell.equals(stackToTargetDoc.get(targetStackUpto))) {
+          b.append("  on cell " + stackToTargetDoc.get(targetStackUpto) + ", wrapped visitor returned " + result);
+          targetStackUpto++;
+        }
+        return result;
+      }
+    }
+
+    private class Cell {
+      private final byte[] minPackedValue;
+      private final byte[] maxPackedValue;
+
+      public Cell(byte[] minPackedValue, byte[] maxPackedValue) {
+        this.minPackedValue = minPackedValue.clone();
+        this.maxPackedValue = maxPackedValue.clone();
+      }
+
+      /** Returns true if this cell fully contains the other one */
+      public boolean contains(Cell other) {
+        for(int dim=0;dim<numDims;dim++) {
+          int offset = bytesPerDim * dim;
+          // other.min < this.min?
+          if (StringHelper.compare(bytesPerDim, other.minPackedValue, offset, minPackedValue, offset) < 0) {
+            return false;
+          }
+          // other.max < this.max?
+          if (StringHelper.compare(bytesPerDim, other.maxPackedValue, offset, maxPackedValue, offset) > 0) {
+            return false;
+          }
+        }
+
+        return true;
+      }
+
+      @Override
+      public String toString() {
+        double xMin = PointInShapeIntersectVisitor.decodeValueMin(NumericUtils.sortableBytesToInt(minPackedValue, 0));
+        double xMax = PointInShapeIntersectVisitor.decodeValueMax(NumericUtils.sortableBytesToInt(maxPackedValue, 0));
+        double yMin = PointInShapeIntersectVisitor.decodeValueMin(NumericUtils.sortableBytesToInt(minPackedValue, 1 * Integer.BYTES));
+        double yMax = PointInShapeIntersectVisitor.decodeValueMax(NumericUtils.sortableBytesToInt(maxPackedValue, 1 * Integer.BYTES));
+        double zMin = PointInShapeIntersectVisitor.decodeValueMin(NumericUtils.sortableBytesToInt(minPackedValue, 2 * Integer.BYTES));
+        double zMax = PointInShapeIntersectVisitor.decodeValueMax(NumericUtils.sortableBytesToInt(maxPackedValue, 2 * Integer.BYTES));
+        return "Cell(x=" + xMin + " TO " + xMax + " y=" + yMin + " TO " + yMax + " z=" + zMin + " TO " + zMax + ")";
+      }
+
+      @Override
+      public boolean equals(Object other) {
+        if (other instanceof Cell == false) {
+          return false;
+        }
+
+        Cell otherCell = (Cell) other;
+        return Arrays.equals(minPackedValue, otherCell.minPackedValue) && Arrays.equals(maxPackedValue, otherCell.maxPackedValue);
+      }
+
+      @Override
+      public int hashCode() {
+        return Arrays.hashCode(minPackedValue) + Arrays.hashCode(maxPackedValue);
+      }
+    }
+  }
+
+  public static String explain(String fieldName, GeoShape shape, IndexReader reader, int docID) throws Exception {
+
+    // First find the leaf reader that owns this doc:
+    int subIndex = ReaderUtil.subIndex(docID, reader.leaves());
+    LeafReader leafReader = reader.leaves().get(subIndex).reader();
+
+    StringBuilder b = new StringBuilder();
+    b.append("target is in leaf " + leafReader + " of full reader " + reader + "\n");
+
+    DocIdSetBuilder hits = new DocIdSetBuilder(leafReader.maxDoc());
+    ExplainingVisitor visitor = new ExplainingVisitor(new PointInShapeIntersectVisitor(hits, shape), docID - reader.leaves().get(subIndex).docBase, 3, Integer.BYTES, b);
+
+    // Do first phase, where we just figure out the "path" that leads to the target docID:
+    leafReader.getPointValues().intersect(fieldName, visitor);
+
+    // Do second phase, where we we see how the wrapped visitor responded along that path:
+    visitor.startSecondPhase();
+    leafReader.getPointValues().intersect(fieldName, visitor);
+
+    return b.toString();
+  }
+
+  @Ignore("https://issues.apache.org/jira/browse/LUCENE-7168")
+  public void testCuriousFailure() throws Exception {
+    GeoShape shape = GeoCircleFactory.makeGeoCircle(PlanetModel.WGS84, -0.8971654677124566, -0.3398482030102755, 1.4775317506492547);
+    GeoPoint point = new GeoPoint(0.8653002868649471, 0.50134342478497, 0.046203414829601996);
+
+    // point is inside our circle shape:
+    assertTrue(shape.isWithin(point));
+
+    double xMin = 0.8653002866318559;
+    double xMax = 0.8653002870980383;
+    double yMin = 0.5013434245518787;
+    double yMax = 0.5013434250180612;
+    double zMin = 0.04620341459651078;
+    double zMax = 0.04620341506269321;
+    GeoArea xyzSolid = GeoAreaFactory.makeGeoArea(PlanetModel.WGS84, xMin, xMax, yMin, yMax, zMin, zMax);
+
+    // point is also inside our wee tiny box:
+    assertTrue(xyzSolid.isWithin(point));
+
+    assertTrue(xyzSolid.getRelationship(shape) != GeoArea.DISJOINT);
+  }
 }


Mime
View raw message