You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by nk...@apache.org on 2018/08/02 02:32:53 UTC
lucene-solr:branch_7x: LUCENE-8435: Add new LatLonShapePolygonQuery
for querying indexed LatLonShape fields by arbitrary polygons
Repository: lucene-solr
Updated Branches:
refs/heads/branch_7x 7faa803a7 -> d85defbed
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/d85defbe
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/d85defbe
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/d85defbe
Branch: refs/heads/branch_7x
Commit: d85defbedc54814f01dfc99cc275b563df0cfa3d
Parents: 7faa803
Author: Nicholas Knize <nk...@gmail.com>
Authored: Sat Jul 28 12:55:35 2018 -0500
Committer: Nicholas Knize <nk...@gmail.com>
Committed: Wed Aug 1 14:08:47 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 | 270 +++++++++++++
.../document/TestLatLonPolygonShapeQueries.java | 392 +++++++++++++++++++
.../lucene/document/TestLatLonShapeQueries.java | 275 -------------
8 files changed, 884 insertions(+), 279 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/d85defbe/lucene/CHANGES.txt
----------------------------------------------------------------------
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 1b96ff4..745d996 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -84,6 +84,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/d85defbe/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/d85defbe/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/d85defbe/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/d85defbe/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/d85defbe/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..0387a68
--- /dev/null
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapePolygonQuery.java
@@ -0,0 +1,270 @@
+/*
+ * 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.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, boolean needsScores, 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/d85defbe/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..e6bd907
--- /dev/null
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPolygonShapeQueries.java
@@ -0,0 +1,392 @@
+/*
+ * 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.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 boolean needsScores() {
+ return false;
+ }
+
+ @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 boolean needsScores() {
+ return false;
+ }
+
+ @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/d85defbe/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 1ef0344..0000000
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShapeQueries.java
+++ /dev/null
@@ -1,275 +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.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 boolean needsScores() {
- return false;
- }
-
- @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);
- }
-}