lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From da...@apache.org
Subject [27/48] lucene-solr:jira/http2: LUCENE-8435: Add new LatLonShapePolygonQuery for querying indexed LatLonShape fields by arbitrary polygons
Date Mon, 06 Aug 2018 04:16:00 GMT
LUCENE-8435: Add new LatLonShapePolygonQuery for querying indexed LatLonShape fields by arbitrary polygons


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

Branch: refs/heads/jira/http2
Commit: 18c2300fd61c369b87ce01b6201b95a53f89e115
Parents: 679b4aa
Author: Nicholas Knize <nknize@gmail.com>
Authored: Sat Jul 28 12:55:35 2018 -0500
Committer: Nicholas Knize <nknize@gmail.com>
Committed: Wed Aug 1 12:53:36 2018 -0500

----------------------------------------------------------------------
 lucene/CHANGES.txt                              |   2 +
 .../src/java/org/apache/lucene/geo/Polygon.java |  30 ++
 .../java/org/apache/lucene/geo/Polygon2D.java   | 147 ++++++-
 .../org/apache/lucene/geo/TestPolygon2D.java    |  43 ++
 .../org/apache/lucene/document/LatLonShape.java |   4 +
 .../document/LatLonShapePolygonQuery.java       | 271 +++++++++++++
 .../document/TestLatLonPolygonShapeQueries.java | 393 +++++++++++++++++++
 .../lucene/document/TestLatLonShapeQueries.java | 276 -------------
 8 files changed, 886 insertions(+), 280 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/18c2300f/lucene/CHANGES.txt
----------------------------------------------------------------------
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index b76cc6f..9b9bcc8 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -213,6 +213,8 @@ Changes in Runtime Behavior:
 
 Improvements
 
+* LUCENE-8435: Add new LatLonShapePolygonQuery for querying indexed LatLonShape fields by arbitrary polygons (Nick Knize)
+
 * LUCENE-8367: Make per-dimension drill down optional for each facet dimension (Mike McCandless)
 
 * LUCENE-8396: Add Points Based Shape Indexing and Search that decomposes shapes

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/18c2300f/lucene/core/src/java/org/apache/lucene/geo/Polygon.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/geo/Polygon.java b/lucene/core/src/java/org/apache/lucene/geo/Polygon.java
index 39ba9b7..5e14286 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Polygon.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Polygon.java
@@ -202,6 +202,36 @@ public final class Polygon {
     return sb.toString();
   }
 
+  private String verticesToGeoJSON(final double[] lats, final double[] lons) {
+    StringBuilder sb = new StringBuilder();
+    sb.append('[');
+    for (int i = 0; i < lats.length; i++) {
+      sb.append("[")
+          .append(lons[i])
+          .append(", ")
+          .append(lats[i])
+          .append("]");
+      if (i != lats.length - 1) {
+        sb.append(", ");
+      }
+    }
+    sb.append(']');
+    return sb.toString();
+  }
+
+  /** prints polygons as geojson */
+  public String toGeoJSON() {
+    StringBuilder sb = new StringBuilder();
+    sb.append("[");
+    sb.append(verticesToGeoJSON(polyLats, polyLons));
+    for (Polygon hole : holes) {
+      sb.append(",");
+      sb.append(verticesToGeoJSON(hole.polyLats, hole.polyLons));
+    }
+    sb.append("]");
+    return sb.toString();
+  }
+
   /** Parses a standard GeoJSON polygon string.  The type of the incoming GeoJSON object must be a Polygon or MultiPolygon, optionally
    *  embedded under a "type: Feature".  A Polygon will return as a length 1 array, while a MultiPolygon will be 1 or more in length.
    *

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/18c2300f/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java b/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
index 3feb012..64a3784 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
@@ -19,7 +19,6 @@ package org.apache.lucene.geo;
 import java.util.Arrays;
 import java.util.Comparator;
 
-import org.apache.lucene.geo.Polygon;
 import org.apache.lucene.index.PointValues.Relation;
 import org.apache.lucene.util.ArrayUtil;
 
@@ -123,7 +122,35 @@ public final class Polygon2D {
     
     return false;
   }
-  
+
+  /** Returns relation to the provided triangle */
+  public Relation relateTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
+    // compute bounding box of triangle
+    double minLat = StrictMath.min(StrictMath.min(ay, by), cy);
+    double minLon = StrictMath.min(StrictMath.min(ax, bx), cx);
+    double maxLat = StrictMath.max(StrictMath.max(ay, by), cy);
+    double maxLon = StrictMath.max(StrictMath.max(ax, bx), cx);
+    if (minLat <= maxY && minLon <= maxX) {
+      Relation relation = componentRelateTriangle(ax, ay, bx, by, cx, cy);
+      if (relation != Relation.CELL_OUTSIDE_QUERY) {
+        return relation;
+      }
+      if (left != null) {
+        relation = left.relateTriangle(ax, ay, bx, by, cx, cy);
+        if (relation != Relation.CELL_OUTSIDE_QUERY) {
+          return relation;
+        }
+      }
+      if (right != null && ((splitX == false && maxLat >= this.minLat) || (splitX && maxLon >= this.minLon))) {
+        relation = right.relateTriangle(ax, ay, bx, by, cx, cy);
+        if (relation != Relation.CELL_OUTSIDE_QUERY) {
+          return relation;
+        }
+      }
+    }
+    return Relation.CELL_OUTSIDE_QUERY;
+  }
+
   /** Returns relation to the provided rectangle */
   public Relation relate(double minLat, double maxLat, double minLon, double maxLon) {
     if (minLat <= maxY && minLon <= maxX) {
@@ -147,6 +174,42 @@ public final class Polygon2D {
     return Relation.CELL_OUTSIDE_QUERY;
   }
 
+  private Relation componentRelateTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
+    // compute bounding box of triangle
+    double minLat = StrictMath.min(StrictMath.min(ay, by), cy);
+    double minLon = StrictMath.min(StrictMath.min(ax, bx), cx);
+    double maxLat = StrictMath.max(StrictMath.max(ay, by), cy);
+    double maxLon = StrictMath.max(StrictMath.max(ax, bx), cx);
+    if (maxLon < this.minLon || minLon > this.maxLon || maxLat < this.minLat || minLat > this.maxLat) {
+      return Relation.CELL_OUTSIDE_QUERY;
+    }
+    // check any holes
+    if (holes != null) {
+      Relation holeRelation = holes.relateTriangle(ax, ay, bx, by, cx, cy);
+      if (holeRelation == Relation.CELL_CROSSES_QUERY) {
+        return Relation.CELL_CROSSES_QUERY;
+      } else if (holeRelation == Relation.CELL_INSIDE_QUERY) {
+        return Relation.CELL_OUTSIDE_QUERY;
+      }
+    }
+    // check each corner: if < 3 are present, its cheaper than crossesSlowly
+    int numCorners = numberOfTriangleCorners(ax, ay, bx, by, cx, cy);
+    if (numCorners == 3) {
+      if (tree.crossesTriangle(ax, ay, bx, by, cx, cy)) {
+        return Relation.CELL_CROSSES_QUERY;
+      }
+      return Relation.CELL_INSIDE_QUERY;
+    } else if (numCorners > 0) {
+      return Relation.CELL_CROSSES_QUERY;
+    }
+
+    // we cross
+    if (tree.crossesTriangle(ax, ay, bx, by, cx, cy)) {
+      return Relation.CELL_CROSSES_QUERY;
+    }
+    return Relation.CELL_OUTSIDE_QUERY;
+  }
+
   /** Returns relation to the provided rectangle for this component */
   private Relation componentRelate(double minLat, double maxLat, double minLon, double maxLon) {
     // if the bounding boxes are disjoint then the shape does not cross
@@ -184,7 +247,24 @@ public final class Polygon2D {
     
     return Relation.CELL_OUTSIDE_QUERY;
   }
-  
+
+  private int numberOfTriangleCorners(double ax, double ay, double bx, double by, double cx, double cy) {
+    int containsCount = 0;
+    if (componentContains(ay, ax)) {
+      containsCount++;
+    }
+    if (componentContains(by, bx)) {
+      containsCount++;
+    }
+    if (containsCount == 1) {
+      return containsCount;
+    }
+    if (componentContains(cy, cx)) {
+      containsCount++;
+    }
+    return containsCount;
+  }
+
   // returns 0, 4, or something in between
   private int numberOfCorners(double minLat, double maxLat, double minLon, double maxLon) {
     int containsCount = 0;
@@ -345,7 +425,66 @@ public final class Polygon2D {
       }
       return res;
     }
-    
+
+    /** Returns true if the triangle crosses any edge in this edge subtree */
+    boolean crossesTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
+      // compute bounding box of triangle
+      double minLat = StrictMath.min(StrictMath.min(ay, by), cy);
+      double minLon = StrictMath.min(StrictMath.min(ax, bx), cx);
+      double maxLat = StrictMath.max(StrictMath.max(ay, by), cy);
+      double maxLon = StrictMath.max(StrictMath.max(ax, bx), cx);
+
+      if (minLat <= max) {
+        double dy = lat1;
+        double ey = lat2;
+        double dx = lon1;
+        double ex = lon2;
+
+        // optimization: see if the rectangle is outside of the "bounding box" of the polyline at all
+        // if not, don't waste our time trying more complicated stuff
+        boolean outside = (dy < minLat && ey < minLat) ||
+            (dy > maxLat && ey > maxLat) ||
+            (dx < minLon && ex < minLon) ||
+            (dx > maxLon && ex > maxLon);
+
+        if (outside == false) {
+          // does triangle's first edge intersect polyline?
+          // ax, ay -> bx, by
+          if (orient(dx, dy, ex, ey, ax, ay) * orient(dx, dy, ex, ey, bx, by) <= 0 &&
+              orient(ax, ay, bx, by, dx, dy) * orient(ax, ay, bx, by, ex, ey) <= 0) {
+            return true;
+          }
+
+          // does triangle's second edge intersect polyline?
+          // bx, by -> cx, cy
+          if (orient(dx, dy, ex, ey, bx, by) * orient(dx, dy, ex, ey, cx, cy) <= 0 &&
+              orient(bx, by, cx, cy, dx, dy) * orient(bx, by, cx, cy, ex, ey) <= 0) {
+            return true;
+          }
+
+          // does triangle's third edge intersect polyline?
+          // cx, cy -> ax, ay
+          if (orient(dx, dy, ex, ey, cx, cy) * orient(dx, dy, ex, ey, ax, ay) <= 0 &&
+              orient(cx, cy, ax, ay, dx, dy) * orient(cx, cy, ax, ay, ex, ey) <= 0) {
+            return true;
+          }
+        }
+
+        if (left != null) {
+          if (left.crossesTriangle(ax, ay, bx, by, cx, cy)) {
+            return true;
+          }
+        }
+
+        if (right != null && maxLat >= low) {
+          if (right.crossesTriangle(ax, ay, bx, by, cx, cy)) {
+            return true;
+          }
+        }
+      }
+      return false;
+    }
+
     /** Returns true if the box crosses any edge in this edge subtree */
     boolean crosses(double minLat, double maxLat, double minLon, double maxLon) {
       // we just have to cross one edge to answer the question, so we descend the tree and return when we do.

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/18c2300f/lucene/core/src/test/org/apache/lucene/geo/TestPolygon2D.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/test/org/apache/lucene/geo/TestPolygon2D.java b/lucene/core/src/test/org/apache/lucene/geo/TestPolygon2D.java
index 31a42c0..053f008 100644
--- a/lucene/core/src/test/org/apache/lucene/geo/TestPolygon2D.java
+++ b/lucene/core/src/test/org/apache/lucene/geo/TestPolygon2D.java
@@ -16,10 +16,13 @@
  */
 package org.apache.lucene.geo;
 
+import static org.apache.lucene.geo.GeoTestUtil.createRegularPolygon;
 import static org.apache.lucene.geo.GeoTestUtil.nextLatitude;
 import static org.apache.lucene.geo.GeoTestUtil.nextLongitude;
+import static org.apache.lucene.geo.GeoTestUtil.nextPointNear;
 import static org.apache.lucene.geo.GeoTestUtil.nextPolygon;
 
+import com.carrotsearch.randomizedtesting.generators.RandomNumbers;
 import org.apache.lucene.index.PointValues.Relation;
 import org.apache.lucene.util.LuceneTestCase;
 
@@ -289,4 +292,44 @@ public class TestPolygon2D extends LuceneTestCase {
       }
     }
   }
+
+  // targets the polygon directly
+  public void testRelateTriangle() {
+    for (int i = 0; i < 100; ++i) {
+      Polygon polygon = nextPolygon();
+      Polygon2D impl = Polygon2D.create(polygon);
+
+      for (int j = 0; j < 100; j++) {
+        double[] a = nextPointNear(polygon);
+        double[] b = nextPointNear(polygon);
+        double[] c = nextPointNear(polygon);
+
+        // if the point is within poly, then triangle should not intersect
+        if (impl.contains(a[0], a[1]) || impl.contains(b[0], b[1]) || impl.contains(c[0], c[1])) {
+          assertTrue(impl.relateTriangle(a[1], a[0], b[1], b[0], c[1], c[0]) != Relation.CELL_OUTSIDE_QUERY);
+        }
+      }
+    }
+  }
+
+  // test
+  public void testRelateTriangleEdgeCases() {
+    for (int i = 0; i < 100; ++i) {
+      // random radius between 1Km and 100Km
+      int randomRadius = RandomNumbers.randomIntBetween(random(), 1000, 100000);
+      // random number of vertices
+      int numVertices = RandomNumbers.randomIntBetween(random(), 100, 1000);
+      Polygon polygon = createRegularPolygon(0, 0, randomRadius, numVertices);
+      Polygon2D impl = Polygon2D.create(polygon);
+
+      // create and test a simple tessellation
+      for (int j = 1; j < numVertices; ++j) {
+        double[] a = new double[] {0d, 0d};  // center of poly
+        double[] b = new double[] {polygon.getPolyLat(j - 1), polygon.getPolyLon(j - 1)};
+        // occassionally test pancake triangles
+        double[] c = random().nextBoolean() ? new double[] {polygon.getPolyLat(j), polygon.getPolyLon(j)} : new double[] {a[0], a[1]};
+        assertTrue(impl.relateTriangle(a[0], a[1], b[0], b[1], c[0], c[1]) != Relation.CELL_OUTSIDE_QUERY);
+      }
+    }
+  }
 }

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/18c2300f/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShape.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShape.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShape.java
index eabc326..28c95e4 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShape.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShape.java
@@ -80,6 +80,10 @@ public class LatLonShape {
     return new LatLonShapeBoundingBoxQuery(field, minLatitude, maxLatitude, minLongitude, maxLongitude);
   }
 
+  public static Query newPolygonQuery(String field, Polygon... polygons) {
+    return new LatLonShapePolygonQuery(field, polygons);
+  }
+
   /** polygons are decomposed into tessellated triangles using {@link org.apache.lucene.geo.Tessellator}
    * these triangles are encoded and inserted as separate indexed POINT fields
    */

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/18c2300f/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapePolygonQuery.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapePolygonQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapePolygonQuery.java
new file mode 100644
index 0000000..9a9b890
--- /dev/null
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapePolygonQuery.java
@@ -0,0 +1,271 @@
+/*
+ * 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.document;
+
+import java.io.IOException;
+import java.util.Arrays;
+import java.util.Objects;
+
+import org.apache.lucene.geo.GeoEncodingUtils;
+import org.apache.lucene.geo.Polygon;
+import org.apache.lucene.geo.Polygon2D;
+import org.apache.lucene.geo.Rectangle;
+import org.apache.lucene.index.FieldInfo;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.index.PointValues.IntersectVisitor;
+import org.apache.lucene.index.PointValues.Relation;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.DocIdSetBuilder;
+import org.apache.lucene.util.FutureArrays;
+import org.apache.lucene.util.NumericUtils;
+
+import static org.apache.lucene.geo.GeoEncodingUtils.encodeLatitude;
+import static org.apache.lucene.geo.GeoEncodingUtils.encodeLatitudeCeil;
+import static org.apache.lucene.geo.GeoEncodingUtils.encodeLongitude;
+import static org.apache.lucene.geo.GeoEncodingUtils.encodeLongitudeCeil;
+
+/**
+ * Finds all previously indexed shapes that intersect the specified arbitrary.
+ *
+ * <p>The field must be indexed using
+ * {@link org.apache.lucene.document.LatLonShape#createIndexableFields(String, Polygon)} added per document.
+ *
+ *  @lucene.experimental
+ **/
+public class LatLonShapePolygonQuery extends Query {
+  final String field;
+  final Polygon[] polygons;
+
+
+  public LatLonShapePolygonQuery(String field, Polygon... polygons) {
+    if (field == null) {
+      throw new IllegalArgumentException("field must not be null");
+    }
+    if (polygons == null) {
+      throw new IllegalArgumentException("polygons must not be null");
+    }
+    if (polygons.length == 0) {
+      throw new IllegalArgumentException("polygons must not be empty");
+    }
+    for (int i = 0; i < polygons.length; i++) {
+      if (polygons[i] == null) {
+        throw new IllegalArgumentException("polygon[" + i + "] must not be null");
+      }
+    }
+    this.field = field;
+    this.polygons = polygons.clone();
+  }
+
+  @Override
+  public final Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost) throws IOException {
+    final Rectangle box = Rectangle.fromPolygon(polygons);
+    final byte minLat[] = new byte[Integer.BYTES];
+    final byte maxLat[] = new byte[Integer.BYTES];
+    final byte minLon[] = new byte[Integer.BYTES];
+    final byte maxLon[] = new byte[Integer.BYTES];
+    NumericUtils.intToSortableBytes(encodeLatitudeCeil(box.minLat), minLat, 0);
+    NumericUtils.intToSortableBytes(encodeLatitude(box.maxLat), maxLat, 0);
+    NumericUtils.intToSortableBytes(encodeLongitudeCeil(box.minLon), minLon, 0);
+    NumericUtils.intToSortableBytes(encodeLongitude(box.maxLon), maxLon, 0);
+
+    final Polygon2D polygon = Polygon2D.create(polygons);
+
+    return new ConstantScoreWeight(this, boost) {
+
+      private Relation relateRangeToQuery(byte[] minTriangle, byte[] maxTriangle) {
+        // compute bounding box
+        int minXOfs = 0;
+        int minYOfs = 0;
+        int maxXOfs = 0;
+        int maxYOfs = 0;
+        for (int d = 1; d < 3; ++d) {
+          // check minX
+          int aOfs = (minXOfs * 2 * LatLonPoint.BYTES) + LatLonPoint.BYTES;
+          int bOfs = (d * 2 * LatLonPoint.BYTES) + LatLonPoint.BYTES;
+          if (FutureArrays.compareUnsigned(minTriangle, bOfs, bOfs + LatLonPoint.BYTES, minTriangle, aOfs, aOfs + LatLonPoint.BYTES) < 0) {
+            minXOfs = d;
+          }
+          // check maxX
+          aOfs = (maxXOfs * 2 * LatLonPoint.BYTES) + LatLonPoint.BYTES;
+          if (FutureArrays.compareUnsigned(maxTriangle, bOfs, bOfs + LatLonPoint.BYTES, maxTriangle, aOfs, aOfs + LatLonPoint.BYTES) > 0) {
+            maxXOfs = d;
+          }
+          // check minY
+          aOfs = minYOfs * 2 * LatLonPoint.BYTES;
+          bOfs = d * 2 * LatLonPoint.BYTES;
+          if (FutureArrays.compareUnsigned(minTriangle, bOfs, bOfs + LatLonPoint.BYTES, minTriangle, aOfs, aOfs + LatLonPoint.BYTES) < 0) {
+            minYOfs = d;
+          }
+          // check maxY
+          aOfs = maxYOfs * 2 * LatLonPoint.BYTES;
+          if (FutureArrays.compareUnsigned(maxTriangle, bOfs, bOfs + LatLonPoint.BYTES, maxTriangle, aOfs, aOfs + LatLonPoint.BYTES) > 0) {
+            maxYOfs = d;
+          }
+        }
+        minXOfs = (minXOfs * 2 * LatLonPoint.BYTES) + LatLonPoint.BYTES;
+        maxXOfs = (maxXOfs * 2 * LatLonPoint.BYTES) + LatLonPoint.BYTES;
+        minYOfs *= 2 * LatLonPoint.BYTES;
+        maxYOfs *= 2 * LatLonPoint.BYTES;
+
+        double minLat = GeoEncodingUtils.decodeLatitude(minTriangle, minYOfs);
+        double minLon = GeoEncodingUtils.decodeLongitude(minTriangle, minXOfs);
+        double maxLat = GeoEncodingUtils.decodeLatitude(maxTriangle, maxYOfs);
+        double maxLon = GeoEncodingUtils.decodeLongitude(maxTriangle, maxXOfs);
+
+        // check internal node against query
+        return polygon.relate(minLat, maxLat, minLon, maxLon);
+      }
+
+      private boolean queryCrossesTriangle(byte[] t) {
+        double ay = GeoEncodingUtils.decodeLatitude(t, 0);
+        double ax = GeoEncodingUtils.decodeLongitude(t, LatLonPoint.BYTES);
+        double by = GeoEncodingUtils.decodeLatitude(t, 2 * LatLonPoint.BYTES);
+        double bx = GeoEncodingUtils.decodeLongitude(t, 3 * LatLonPoint.BYTES);
+        double cy = GeoEncodingUtils.decodeLatitude(t, 4 * LatLonPoint.BYTES);
+        double cx = GeoEncodingUtils.decodeLongitude(t, 5 * LatLonPoint.BYTES);
+        return polygon.relateTriangle(ax, ay, bx, by, cx, cy) != Relation.CELL_OUTSIDE_QUERY;
+      }
+
+      private IntersectVisitor getIntersectVisitor(DocIdSetBuilder result) {
+        return new IntersectVisitor() {
+
+          DocIdSetBuilder.BulkAdder adder;
+
+          @Override
+          public void grow(int count) {
+            adder = result.grow(count);
+          }
+
+          @Override
+          public void visit(int docID) throws IOException {
+            adder.add(docID);
+          }
+
+          @Override
+          public void visit(int docID, byte[] t) throws IOException {
+            if (queryCrossesTriangle(t)) {
+              adder.add(docID);
+            }
+          }
+
+          @Override
+          public Relation compare(byte[] minTriangle, byte[] maxTriangle) {
+            return relateRangeToQuery(minTriangle, maxTriangle);
+          }
+        };
+      }
+
+      @Override
+      public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+        LeafReader reader = context.reader();
+        PointValues values = reader.getPointValues(field);
+        if (values == null) {
+          // No docs in this segment had any points fields
+          return null;
+        }
+        FieldInfo fieldInfo = reader.getFieldInfos().fieldInfo(field);
+        if (fieldInfo == null) {
+          // No docs in this segment indexed this field at all
+          return null;
+        }
+
+        final Weight weight = this;
+        return new ScorerSupplier() {
+          final DocIdSetBuilder result = new DocIdSetBuilder(reader.maxDoc(), values, field);
+          final PointValues.IntersectVisitor visitor = getIntersectVisitor(result);
+          long cost = -1;
+
+          @Override
+          public Scorer get(long leadCost) throws IOException {
+            values.intersect(visitor);
+            DocIdSetIterator iterator = result.build().iterator();
+            return new ConstantScoreScorer(weight, score(), iterator);
+          }
+
+          @Override
+          public long cost() {
+            if (cost == -1) {
+              // Computing the cost may be expensive, so only do it if necessary
+              cost = values.estimatePointCount(visitor);
+              assert cost >= 0;
+            }
+            return cost;
+          }
+        };
+      }
+
+      @Override
+      public Scorer scorer(LeafReaderContext context) throws IOException {
+        ScorerSupplier scorerSupplier = scorerSupplier(context);
+        if (scorerSupplier == null) {
+          return null;
+        }
+        return scorerSupplier.get(Long.MAX_VALUE);
+      }
+
+      @Override
+      public boolean isCacheable(LeafReaderContext ctx) {
+        return true;
+      }
+    };
+  }
+
+  public String getField() {
+    return field;
+  }
+
+  @Override
+  public String toString(String field) {
+    final StringBuilder sb = new StringBuilder();
+    sb.append(getClass().getSimpleName());
+    sb.append(':');
+    if (this.field.equals(field) == false) {
+      sb.append(" field=");
+      sb.append(this.field);
+      sb.append(':');
+    }
+    sb.append("Polygon(" + polygons[0].toGeoJSON() + ")");
+    return sb.toString();
+  }
+
+  @Override
+  public boolean equals(Object o) {
+    return sameClassAs(o) && equalsTo(getClass().cast(o));
+  }
+
+  private boolean equalsTo(LatLonShapePolygonQuery o) {
+    return Objects.equals(field, o.field) && Arrays.equals(polygons, o.polygons);
+  }
+
+  @Override
+  public int hashCode() {
+    int hash = classHash();
+    hash = 31 * hash + field.hashCode();
+    hash = 31 * hash + Arrays.hashCode(polygons);
+    return hash;
+  }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/18c2300f/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPolygonShapeQueries.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPolygonShapeQueries.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPolygonShapeQueries.java
new file mode 100644
index 0000000..25d4888
--- /dev/null
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPolygonShapeQueries.java
@@ -0,0 +1,393 @@
+/*
+ * 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.document;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+import org.apache.lucene.geo.GeoTestUtil;
+import org.apache.lucene.geo.Polygon;
+import org.apache.lucene.geo.Polygon2D;
+import org.apache.lucene.geo.Rectangle;
+import org.apache.lucene.geo.Tessellator;
+import org.apache.lucene.index.DirectoryReader;
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.index.IndexWriter;
+import org.apache.lucene.index.IndexWriterConfig;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.MultiDocValues;
+import org.apache.lucene.index.MultiFields;
+import org.apache.lucene.index.NumericDocValues;
+import org.apache.lucene.index.PointValues.Relation;
+import org.apache.lucene.index.SerialMergeScheduler;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.SimpleCollector;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.IOUtils;
+import org.apache.lucene.util.LuceneTestCase;
+
+import static org.apache.lucene.geo.GeoEncodingUtils.decodeLatitude;
+import static org.apache.lucene.geo.GeoEncodingUtils.decodeLongitude;
+import static org.apache.lucene.geo.GeoEncodingUtils.encodeLatitude;
+import static org.apache.lucene.geo.GeoEncodingUtils.encodeLatitudeCeil;
+import static org.apache.lucene.geo.GeoEncodingUtils.encodeLongitude;
+import static org.apache.lucene.geo.GeoEncodingUtils.encodeLongitudeCeil;
+
+/** base Test case for {@link LatLonShape} indexing and search */
+public class TestLatLonPolygonShapeQueries extends LuceneTestCase {
+  protected static final String FIELD_NAME = "shape";
+
+  private Polygon quantizePolygon(Polygon polygon) {
+    double[] lats = new double[polygon.numPoints()];
+    double[] lons = new double[polygon.numPoints()];
+    for (int i = 0; i < lats.length; ++i) {
+      lats[i] = quantizeLat(polygon.getPolyLat(i));
+      lons[i] = quantizeLon(polygon.getPolyLon(i));
+    }
+    return new Polygon(lats, lons);
+  }
+
+  protected double quantizeLat(double rawLat) {
+    return decodeLatitude(encodeLatitude(rawLat));
+  }
+
+  protected double quantizeLatCeil(double rawLat) {
+    return decodeLatitude(encodeLatitudeCeil(rawLat));
+  }
+
+  protected double quantizeLon(double rawLon) {
+    return decodeLongitude(encodeLongitude(rawLon));
+  }
+
+  protected double quantizeLonCeil(double rawLon) {
+    return decodeLongitude(encodeLongitudeCeil(rawLon));
+  }
+
+  protected void addPolygonsToDoc(String field, Document doc, Polygon polygon) {
+    Field[] fields = LatLonShape.createIndexableFields(field, polygon);
+    for (Field f : fields) {
+      doc.add(f);
+    }
+  }
+
+  protected Query newRectQuery(String field, double minLat, double maxLat, double minLon, double maxLon) {
+    return LatLonShape.newBoxQuery(field, minLat, maxLat, minLon, maxLon);
+  }
+
+  protected Query newPolygonQuery(String field, Polygon... polygons) {
+    return LatLonShape.newPolygonQuery(field, polygons);
+  }
+
+  public void testRandomTiny() throws Exception {
+    // Make sure single-leaf-node case is OK:
+    doTestRandom(10);
+  }
+
+  public void testRandomMedium() throws Exception {
+    doTestRandom(10000);
+  }
+
+  @Nightly
+  public void testRandomBig() throws Exception {
+    doTestRandom(50000);
+  }
+
+  private void doTestRandom(int count) throws Exception {
+    int numPolygons = atLeast(count);
+
+    if (VERBOSE) {
+      System.out.println("TEST: numPolygons=" + numPolygons);
+    }
+
+    Polygon[] polygons = new Polygon[numPolygons];
+    for (int id = 0; id < numPolygons; ++id) {
+      int x = random().nextInt(20);
+      if (x == 17) {
+        polygons[id] = null;
+        if (VERBOSE) {
+          System.out.println("  id=" + id + " is missing");
+        }
+      } else {
+        // create a polygon that does not cross the dateline
+        polygons[id] = GeoTestUtil.nextPolygon();
+      }
+    }
+    verify(polygons);
+  }
+
+  private void verify(Polygon... polygons) throws Exception {
+    ArrayList<Polygon2D> poly2d = new ArrayList<>();
+    poly2d.ensureCapacity(polygons.length);
+    // index random polygons; poly2d will contain the Polygon2D objects needed for verification
+    IndexWriter w = indexRandomPolygons(poly2d, polygons);
+    Directory dir = w.getDirectory();
+    final IndexReader reader = DirectoryReader.open(w);
+    // test random bbox queries
+    verifyRandomBBoxQueries(reader, poly2d, polygons);
+    // test random polygon queires
+    verifyRandomPolygonQueries(reader, poly2d, polygons);
+    IOUtils.close(w, reader, dir);
+  }
+
+  protected IndexWriter indexRandomPolygons(List<Polygon2D> poly2d, Polygon... polygons) throws Exception {
+    IndexWriterConfig iwc = newIndexWriterConfig();
+    iwc.setMergeScheduler(new SerialMergeScheduler());
+    int mbd = iwc.getMaxBufferedDocs();
+    if (mbd != -1 && mbd < polygons.length / 100) {
+      iwc.setMaxBufferedDocs(polygons.length / 100);
+    }
+    Directory dir;
+    if (polygons.length > 1000) {
+      dir = newFSDirectory(createTempDir(getClass().getSimpleName()));
+    } else {
+      dir = newDirectory();
+    }
+
+    Set<Integer> deleted = new HashSet<>();
+    IndexWriter w = new IndexWriter(dir, iwc);
+    for (int id = 0; id < polygons.length; ++id) {
+      Document doc = new Document();
+      doc.add(newStringField("id", "" + id, Field.Store.NO));
+      doc.add(new NumericDocValuesField("id", id));
+      if (polygons[id] != null) {
+        try {
+          addPolygonsToDoc(FIELD_NAME, doc, polygons[id]);
+        } catch (IllegalArgumentException e) {
+          // GeoTestUtil will occassionally create invalid polygons
+          // invalid polygons will not tessellate
+          // we skip those polygons that will not tessellate, relying on the TestTessellator class
+          // to ensure the Tessellator correctly identified a malformed shape and its not a bug
+          if (VERBOSE) {
+            System.out.println("  id=" + id + " could not tessellate. Malformed shape " + polygons[id] + " detected");
+          }
+          // remove and skip the malformed shape
+          polygons[id] = null;
+          poly2d.add(id, null);
+          continue;
+        }
+        poly2d.add(id, Polygon2D.create(quantizePolygon(polygons[id])));
+      } else {
+        poly2d.add(id, null);
+      }
+      w.addDocument(doc);
+      if (id > 0 && random().nextInt(100) == 42) {
+        int idToDelete = random().nextInt(id);
+        w.deleteDocuments(new Term("id", ""+idToDelete));
+        deleted.add(idToDelete);
+        if (VERBOSE) {
+          System.out.println("   delete id=" + idToDelete);
+        }
+      }
+    }
+
+    if (random().nextBoolean()) {
+      w.forceMerge(1);
+    }
+
+    return w;
+  }
+
+  protected void verifyRandomBBoxQueries(IndexReader reader, List<Polygon2D> poly2d, Polygon... polygons) throws Exception {
+    IndexSearcher s = newSearcher(reader);
+
+    final int iters = atLeast(75);
+
+    Bits liveDocs = MultiFields.getLiveDocs(s.getIndexReader());
+    int maxDoc = s.getIndexReader().maxDoc();
+
+    for (int iter = 0; iter < iters; ++iter) {
+      if (VERBOSE) {
+        System.out.println("\nTEST: iter=" + (iter+1) + " of " + iters + " s=" + s);
+      }
+
+      // BBox
+      Rectangle rect = GeoTestUtil.nextBoxNotCrossingDateline();
+      Query query = newRectQuery(FIELD_NAME, rect.minLat, rect.maxLat, rect.minLon, rect.maxLon);
+
+      if (VERBOSE) {
+        System.out.println("  query=" + query);
+      }
+
+      final FixedBitSet hits = new FixedBitSet(maxDoc);
+      s.search(query, new SimpleCollector() {
+
+        private int docBase;
+
+        @Override
+        public ScoreMode scoreMode() {
+          return ScoreMode.COMPLETE_NO_SCORES;
+        }
+
+        @Override
+        protected void doSetNextReader(LeafReaderContext context) throws IOException {
+          docBase = context.docBase;
+        }
+
+        @Override
+        public void collect(int doc) throws IOException {
+          hits.set(docBase+doc);
+        }
+      });
+
+      boolean fail = false;
+      NumericDocValues docIDToID = MultiDocValues.getNumericValues(reader, "id");
+      for (int docID = 0; docID < maxDoc; ++docID) {
+        assertEquals(docID, docIDToID.nextDoc());
+        int id = (int) docIDToID.longValue();
+        boolean expected;
+        if (liveDocs != null && liveDocs.get(docID) == false) {
+          // document is deleted
+          expected = false;
+        } else if (polygons[id] == null) {
+          expected = false;
+        } else {
+          // check quantized poly against quantized query
+          expected = poly2d.get(id).relate(quantizeLatCeil(rect.minLat), quantizeLat(rect.maxLat),
+              quantizeLonCeil(rect.minLon), quantizeLon(rect.maxLon)) != Relation.CELL_OUTSIDE_QUERY;
+        }
+
+        if (hits.get(docID) != expected) {
+          StringBuilder b = new StringBuilder();
+
+          if (expected) {
+            b.append("FAIL: id=" + id + " should match but did not\n");
+          } else {
+            b.append("FAIL: id=" + id + " should not match but did\n");
+          }
+          b.append("  query=" + query + " docID=" + docID + "\n");
+          b.append("  polygon=" + quantizePolygon(polygons[id]) + "\n");
+          b.append("  deleted?=" + (liveDocs != null && liveDocs.get(docID) == false));
+          b.append("  rect=Rectangle(" + quantizeLatCeil(rect.minLat) + " TO " + quantizeLat(rect.maxLat) + " lon=" + quantizeLonCeil(rect.minLon) + " TO " + quantizeLon(rect.maxLon) + ")");
+          if (true) {
+            fail("wrong hit (first of possibly more):\n\n" + b);
+          } else {
+            System.out.println(b.toString());
+            fail = true;
+          }
+        }
+      }
+      if (fail) {
+        fail("some hits were wrong");
+      }
+    }
+  }
+
+  protected void verifyRandomPolygonQueries(IndexReader reader, List<Polygon2D> poly2d, Polygon... polygons) throws Exception {
+    IndexSearcher s = newSearcher(reader);
+
+    final int iters = atLeast(75);
+
+    Bits liveDocs = MultiFields.getLiveDocs(s.getIndexReader());
+    int maxDoc = s.getIndexReader().maxDoc();
+
+    for (int iter = 0; iter < iters; ++iter) {
+      if (VERBOSE) {
+        System.out.println("\nTEST: iter=" + (iter+1) + " of " + iters + " s=" + s);
+      }
+
+      // Polygon
+      Polygon queryPolygon = GeoTestUtil.nextPolygon();
+      Polygon2D queryPoly2D = Polygon2D.create(queryPolygon);
+      Query query = newPolygonQuery(FIELD_NAME, queryPolygon);
+
+      if (VERBOSE) {
+        System.out.println("  query=" + query);
+      }
+
+      final FixedBitSet hits = new FixedBitSet(maxDoc);
+      s.search(query, new SimpleCollector() {
+
+        private int docBase;
+
+        @Override
+        public ScoreMode scoreMode() {
+          return ScoreMode.COMPLETE_NO_SCORES;
+        }
+
+        @Override
+        protected void doSetNextReader(LeafReaderContext context) throws IOException {
+          docBase = context.docBase;
+        }
+
+        @Override
+        public void collect(int doc) throws IOException {
+          hits.set(docBase+doc);
+        }
+      });
+
+      boolean fail = false;
+      NumericDocValues docIDToID = MultiDocValues.getNumericValues(reader, "id");
+      for (int docID = 0; docID < maxDoc; ++docID) {
+        assertEquals(docID, docIDToID.nextDoc());
+        int id = (int) docIDToID.longValue();
+        boolean expected;
+        if (liveDocs != null && liveDocs.get(docID) == false) {
+          // document is deleted
+          expected = false;
+        } else if (polygons[id] == null) {
+          expected = false;
+        } else {
+          expected = false;
+          try {
+            // check poly (quantized the same way as indexed) against query polygon
+            List<Tessellator.Triangle> tesselation = Tessellator.tessellate(quantizePolygon(polygons[id]));
+            for (Tessellator.Triangle t : tesselation) {
+              if (queryPoly2D.relateTriangle(t.getLon(0), t.getLat(0),
+                  t.getLon(1), t.getLat(1), t.getLon(2), t.getLat(2)) != Relation.CELL_OUTSIDE_QUERY) {
+                expected = true;
+                break;
+              }
+            }
+          } catch (IllegalArgumentException e) {
+            continue;
+          }
+        }
+
+        if (hits.get(docID) != expected) {
+          StringBuilder b = new StringBuilder();
+
+          if (expected) {
+            b.append("FAIL: id=" + id + " should match but did not\n");
+          } else {
+            b.append("FAIL: id=" + id + " should not match but did\n");
+          }
+          b.append("  query=" + query + " docID=" + docID + "\n");
+          b.append("  polygon=" + quantizePolygon(polygons[id]).toGeoJSON() + "\n");
+          b.append("  deleted?=" + (liveDocs != null && liveDocs.get(docID) == false));
+          b.append("  queryPolygon=" + queryPolygon.toGeoJSON());
+          if (true) {
+            fail("wrong hit (first of possibly more):\n\n" + b);
+          } else {
+            System.out.println(b.toString());
+            fail = true;
+          }
+        }
+      }
+      if (fail) {
+        fail("some hits were wrong");
+      }
+    }
+  }
+}

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/18c2300f/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShapeQueries.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShapeQueries.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShapeQueries.java
deleted file mode 100644
index 2bb207e..0000000
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShapeQueries.java
+++ /dev/null
@@ -1,276 +0,0 @@
-/*
- * 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.document;
-
-import java.io.IOException;
-import java.util.HashSet;
-import java.util.Set;
-
-import org.apache.lucene.geo.GeoTestUtil;
-import org.apache.lucene.geo.Polygon;
-import org.apache.lucene.geo.Polygon2D;
-import org.apache.lucene.geo.Rectangle;
-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.LeafReaderContext;
-import org.apache.lucene.index.MultiDocValues;
-import org.apache.lucene.index.MultiFields;
-import org.apache.lucene.index.NumericDocValues;
-import org.apache.lucene.index.PointValues.Relation;
-import org.apache.lucene.index.SerialMergeScheduler;
-import org.apache.lucene.index.Term;
-import org.apache.lucene.search.IndexSearcher;
-import org.apache.lucene.search.Query;
-import org.apache.lucene.search.ScoreMode;
-import org.apache.lucene.search.SimpleCollector;
-import org.apache.lucene.store.Directory;
-import org.apache.lucene.util.Bits;
-import org.apache.lucene.util.FixedBitSet;
-import org.apache.lucene.util.IOUtils;
-import org.apache.lucene.util.LuceneTestCase;
-
-import static org.apache.lucene.geo.GeoEncodingUtils.decodeLatitude;
-import static org.apache.lucene.geo.GeoEncodingUtils.decodeLongitude;
-import static org.apache.lucene.geo.GeoEncodingUtils.encodeLatitude;
-import static org.apache.lucene.geo.GeoEncodingUtils.encodeLatitudeCeil;
-import static org.apache.lucene.geo.GeoEncodingUtils.encodeLongitude;
-import static org.apache.lucene.geo.GeoEncodingUtils.encodeLongitudeCeil;
-
-/** base Test case for {@link LatLonShape} indexing and search */
-public class TestLatLonShapeQueries extends LuceneTestCase {
-  protected static final String FIELD_NAME = "shape";
-
-  private Polygon quantizePolygon(Polygon polygon) {
-    double[] lats = new double[polygon.numPoints()];
-    double[] lons = new double[polygon.numPoints()];
-    for (int i = 0; i < lats.length; ++i) {
-      lats[i] = quantizeLat(polygon.getPolyLat(i));
-      lons[i] = quantizeLon(polygon.getPolyLon(i));
-    }
-    return new Polygon(lats, lons);
-  }
-
-  protected double quantizeLat(double rawLat) {
-    return decodeLatitude(encodeLatitude(rawLat));
-  }
-
-  protected double quantizeLatCeil(double rawLat) {
-    return decodeLatitude(encodeLatitudeCeil(rawLat));
-  }
-
-  protected double quantizeLon(double rawLon) {
-    return decodeLongitude(encodeLongitude(rawLon));
-  }
-
-  protected double quantizeLonCeil(double rawLon) {
-    return decodeLongitude(encodeLongitudeCeil(rawLon));
-  }
-
-  protected void addPolygonsToDoc(String field, Document doc, Polygon polygon) {
-    Field[] fields = LatLonShape.createIndexableFields(field, polygon);
-    for (Field f : fields) {
-      doc.add(f);
-    }
-  }
-
-  protected Query newRectQuery(String field, double minLat, double maxLat, double minLon, double maxLon) {
-    return LatLonShape.newBoxQuery(field, minLat, maxLat, minLon, maxLon);
-  }
-
-  public void testRandomTiny() throws Exception {
-    // Make sure single-leaf-node case is OK:
-    doTestRandom(10);
-  }
-
-  public void testRandomMedium() throws Exception {
-    doTestRandom(10000);
-  }
-
-  @Nightly
-  public void testRandomBig() throws Exception {
-    doTestRandom(50000);
-  }
-
-  private void doTestRandom(int count) throws Exception {
-    int numPolygons = atLeast(count);
-
-    if (VERBOSE) {
-      System.out.println("TEST: numPolygons=" + numPolygons);
-    }
-
-    Polygon[] polygons = new Polygon[numPolygons];
-    for (int id = 0; id < numPolygons; ++id) {
-      int x = random().nextInt(20);
-      if (x == 17) {
-        polygons[id] = null;
-        if (VERBOSE) {
-          System.out.println("  id=" + id + " is missing");
-        }
-      } else {
-        // create a polygon that does not cross the dateline
-        polygons[id] = GeoTestUtil.nextPolygon();
-      }
-    }
-    verify(polygons);
-  }
-
-  private void verify(Polygon... polygons) throws Exception {
-    verifyRandomBBoxes(polygons);
-  }
-
-  protected void verifyRandomBBoxes(Polygon... polygons) throws Exception {
-    IndexWriterConfig iwc = newIndexWriterConfig();
-    iwc.setMergeScheduler(new SerialMergeScheduler());
-    int mbd = iwc.getMaxBufferedDocs();
-    if (mbd != -1 && mbd < polygons.length / 100) {
-      iwc.setMaxBufferedDocs(polygons.length / 100);
-    }
-    Directory dir;
-    if (polygons.length > 1000) {
-      dir = newFSDirectory(createTempDir(getClass().getSimpleName()));
-    } else {
-      dir = newDirectory();
-    }
-
-    Set<Integer> deleted = new HashSet<>();
-    IndexWriter w = new IndexWriter(dir, iwc);
-    Polygon2D[] poly2D = new Polygon2D[polygons.length];
-    for (int id = 0; id < polygons.length; ++id) {
-      Document doc = new Document();
-      doc.add(newStringField("id", "" + id, Field.Store.NO));
-      doc.add(new NumericDocValuesField("id", id));
-      if (polygons[id] != null) {
-        try {
-          addPolygonsToDoc(FIELD_NAME, doc, polygons[id]);
-        } catch (IllegalArgumentException e) {
-          // GeoTestUtil will occassionally create invalid polygons
-          // invalid polygons will not tessellate
-          // we skip those polygons that will not tessellate, relying on the TestTessellator class
-          // to ensure the Tessellator correctly identified a malformed shape and its not a bug
-          if (VERBOSE) {
-            System.out.println("  id=" + id + " could not tessellate. Malformed shape " + polygons[id] + " detected");
-          }
-          // remove and skip the malformed shape
-          polygons[id] = null;
-          continue;
-        }
-        poly2D[id] = Polygon2D.create(quantizePolygon(polygons[id]));
-      }
-      w.addDocument(doc);
-      if (id > 0 && random().nextInt(100) == 42) {
-        int idToDelete = random().nextInt(id);
-        w.deleteDocuments(new Term("id", ""+idToDelete));
-        deleted.add(idToDelete);
-        if (VERBOSE) {
-          System.out.println("   delete id=" + idToDelete);
-        }
-      }
-    }
-
-    if (random().nextBoolean()) {
-      w.forceMerge(1);
-    }
-    final IndexReader r = DirectoryReader.open(w);
-    w.close();
-
-    IndexSearcher s = newSearcher(r);
-
-    final int iters = atLeast(75);
-
-    Bits liveDocs = MultiFields.getLiveDocs(s.getIndexReader());
-    int maxDoc = s.getIndexReader().maxDoc();
-
-    for (int iter = 0; iter < iters; ++iter) {
-      if (VERBOSE) {
-        System.out.println("\nTEST: iter=" + (iter+1) + " of " + iters + " s=" + s);
-      }
-
-      // BBox
-      Rectangle rect = GeoTestUtil.nextBoxNotCrossingDateline();
-      Query query = newRectQuery(FIELD_NAME, rect.minLat, rect.maxLat, rect.minLon, rect.maxLon);
-
-      if (VERBOSE) {
-        System.out.println("  query=" + query);
-      }
-
-      final FixedBitSet hits = new FixedBitSet(maxDoc);
-      s.search(query, new SimpleCollector() {
-
-        private int docBase;
-
-        @Override
-        public ScoreMode scoreMode() {
-          return ScoreMode.COMPLETE_NO_SCORES;
-        }
-
-        @Override
-        protected void doSetNextReader(LeafReaderContext context) throws IOException {
-          docBase = context.docBase;
-        }
-
-        @Override
-        public void collect(int doc) throws IOException {
-          hits.set(docBase+doc);
-        }
-      });
-
-      boolean fail = false;
-      NumericDocValues docIDToID = MultiDocValues.getNumericValues(r, "id");
-      for (int docID = 0; docID < maxDoc; ++docID) {
-        assertEquals(docID, docIDToID.nextDoc());
-        int id = (int) docIDToID.longValue();
-        boolean expected;
-        if (liveDocs != null && liveDocs.get(docID) == false) {
-          // document is deleted
-          expected = false;
-        } else if (polygons[id] == null) {
-          expected = false;
-        } else {
-          // check quantized poly against quantized query
-          expected = poly2D[id].relate(quantizeLatCeil(rect.minLat), quantizeLat(rect.maxLat),
-              quantizeLonCeil(rect.minLon), quantizeLon(rect.maxLon)) != Relation.CELL_OUTSIDE_QUERY;
-        }
-
-        if (hits.get(docID) != expected) {
-          StringBuilder b = new StringBuilder();
-
-          if (expected) {
-            b.append("FAIL: id=" + id + " should match but did not\n");
-          } else {
-            b.append("FAIL: id=" + id + " should not match but did\n");
-          }
-          b.append("  query=" + query + " docID=" + docID + "\n");
-          b.append("  polygon=" + quantizePolygon(polygons[id]) + "\n");
-          b.append("  deleted?=" + (liveDocs != null && liveDocs.get(docID) == false));
-          b.append("  rect=Rectangle(" + quantizeLatCeil(rect.minLat) + " TO " + quantizeLat(rect.maxLat) + " lon=" + quantizeLonCeil(rect.minLon) + " TO " + quantizeLon(rect.maxLon) + ")");
-          if (true) {
-            fail("wrong hit (first of possibly more):\n\n" + b);
-          } else {
-            System.out.println(b.toString());
-            fail = true;
-          }
-        }
-      }
-      if (fail) {
-        fail("some hits were wrong");
-      }
-    }
-    IOUtils.close(r, dir);
-  }
-}


Mime
View raw message