You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by ab...@apache.org on 2018/07/19 08:41:19 UTC
[18/50] [abbrv] lucene-solr:jira/solr-12509: LUCENE-8396: Add Points
Based Shape Indexing and Search that decomposes shapes into a triangular mesh
and indexes individual triangles as a 6 dimension point
LUCENE-8396: Add Points Based Shape Indexing and Search that decomposes shapes into a triangular mesh and indexes individual triangles as a 6 dimension point
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/b5ef1333
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/b5ef1333
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/b5ef1333
Branch: refs/heads/jira/solr-12509
Commit: b5ef13330f179ac6a2d98b9dfa4803811190e773
Parents: 4246089
Author: Nicholas Knize <nk...@gmail.com>
Authored: Sat Jul 14 11:27:21 2018 -0500
Committer: Nicholas Knize <nk...@gmail.com>
Committed: Sat Jul 14 11:28:37 2018 -0500
----------------------------------------------------------------------
lucene/CHANGES.txt | 3 +
.../java/org/apache/lucene/geo/GeoUtils.java | 38 +
.../src/java/org/apache/lucene/geo/Polygon.java | 49 +-
.../java/org/apache/lucene/geo/Polygon2D.java | 22 +-
.../org/apache/lucene/document/LatLonShape.java | 113 +++
.../document/LatLonShapeBoundingBoxQuery.java | 415 +++++++++
.../java/org/apache/lucene/geo/Tessellator.java | 910 +++++++++++++++++++
.../src/java/org/apache/lucene/geo/package.html | 31 +
.../apache/lucene/document/TestLatLonShape.java | 124 +++
.../lucene/document/TestLatLonShapeQueries.java | 276 ++++++
.../org/apache/lucene/geo/TestTessellator.java | 50 +
.../java/org/apache/lucene/geo/GeoTestUtil.java | 39 +-
12 files changed, 2026 insertions(+), 44 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/b5ef1333/lucene/CHANGES.txt
----------------------------------------------------------------------
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index d83ea86..b5335c8 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -169,6 +169,9 @@ Improvements
* 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
+ into a triangular mesh and indexes individual triangles as a 6 dimension point (Nick Knize)
+
Other:
* LUCENE-8366: Upgrade to ICU 62.1. Emoji handling now uses Unicode 11's
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/b5ef1333/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java b/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
index aaca549..468de93 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
@@ -174,4 +174,42 @@ public final class GeoUtils {
return maxLon - lon < 90 && lon - minLon < 90;
}
+ /**
+ * Returns a positive value if points a, b, and c are arranged in counter-clockwise order,
+ * negative value if clockwise, zero if collinear.
+ */
+ // see the "Orient2D" method described here:
+ // http://www.cs.berkeley.edu/~jrs/meshpapers/robnotes.pdf
+ // https://www.cs.cmu.edu/~quake/robust.html
+ // Note that this one does not yet have the floating point tricks to be exact!
+ public static int orient(double ax, double ay, double bx, double by, double cx, double cy) {
+ double v1 = (bx - ax) * (cy - ay);
+ double v2 = (cx - ax) * (by - ay);
+ if (v1 > v2) {
+ return 1;
+ } else if (v1 < v2) {
+ return -1;
+ } else {
+ return 0;
+ }
+ }
+
+ /**
+ * used to define the orientation of 3 points
+ * -1 = Clockwise
+ * 0 = Colinear
+ * 1 = Counter-clockwise
+ **/
+ public enum WindingOrder {
+ CW(-1), COLINEAR(0), CCW(1);
+ private final int sign;
+ WindingOrder(int sign) { this.sign = sign; }
+ public int sign() {return sign;}
+ public static WindingOrder fromSign(final int sign) {
+ if (sign == CW.sign) return CW;
+ if (sign == COLINEAR.sign) return COLINEAR;
+ if (sign == CCW.sign) return CCW;
+ throw new IllegalArgumentException("Invalid WindingOrder sign: " + sign);
+ }
+ }
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/b5ef1333/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 99453b9..e96fe8d 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Polygon.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Polygon.java
@@ -19,6 +19,8 @@ package org.apache.lucene.geo;
import java.text.ParseException;
import java.util.Arrays;
+import org.apache.lucene.geo.GeoUtils.WindingOrder;
+
/**
* Represents a closed polygon on the earth's surface. You can either construct the Polygon directly yourself with {@code double[]}
* coordinates, or use {@link Polygon#fromGeoJSON} if you have a polygon already encoded as a
@@ -48,6 +50,8 @@ public final class Polygon {
public final double minLon;
/** maximum longitude of this polygon's bounding box area */
public final double maxLon;
+ /** winding order of the vertices */
+ private final WindingOrder windingOrder;
/**
* Creates a new Polygon from the supplied latitude/longitude array, and optionally any holes.
@@ -92,21 +96,32 @@ public final class Polygon {
this.holes = holes.clone();
// compute bounding box
- double minLat = Double.POSITIVE_INFINITY;
- double maxLat = Double.NEGATIVE_INFINITY;
- double minLon = Double.POSITIVE_INFINITY;
- double maxLon = Double.NEGATIVE_INFINITY;
+ double minLat = polyLats[0];
+ double maxLat = polyLats[0];
+ double minLon = polyLons[0];
+ double maxLon = polyLons[0];
- for (int i = 0;i < polyLats.length; i++) {
+ double windingSum = 0d;
+ final int numPts = polyLats.length - 1;
+ for (int i = 1, j = 0; i < numPts; j = i++) {
minLat = Math.min(polyLats[i], minLat);
maxLat = Math.max(polyLats[i], maxLat);
minLon = Math.min(polyLons[i], minLon);
maxLon = Math.max(polyLons[i], maxLon);
+ // compute signed area
+ windingSum += (polyLons[j] - polyLons[numPts])*(polyLats[i] - polyLats[numPts])
+ - (polyLats[j] - polyLats[numPts])*(polyLons[i] - polyLons[numPts]);
}
this.minLat = minLat;
this.maxLat = maxLat;
this.minLon = minLon;
this.maxLon = maxLon;
+ this.windingOrder = (windingSum < 0) ? GeoUtils.WindingOrder.CW : GeoUtils.WindingOrder.CCW;
+ }
+
+ /** returns the number of vertex points */
+ public int numPoints() {
+ return polyLats.length;
}
/** Returns a copy of the internal latitude array */
@@ -114,16 +129,40 @@ public final class Polygon {
return polyLats.clone();
}
+ /** Returns latitude value at given index */
+ public double getPolyLat(int vertex) {
+ return polyLats[vertex];
+ }
+
/** Returns a copy of the internal longitude array */
public double[] getPolyLons() {
return polyLons.clone();
}
+ /** Returns longitude value at given index */
+ public double getPolyLon(int vertex) {
+ return polyLons[vertex];
+ }
+
/** Returns a copy of the internal holes array */
public Polygon[] getHoles() {
return holes.clone();
}
+ Polygon getHole(int i) {
+ return holes[i];
+ }
+
+ /** Returns the winding order (CW, COLINEAR, CCW) for the polygon shell */
+ public WindingOrder getWindingOrder() {
+ return this.windingOrder;
+ }
+
+ /** returns the number of holes for the polygon */
+ public int numHoles() {
+ return holes.length;
+ }
+
@Override
public int hashCode() {
final int prime = 31;
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/b5ef1333/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 699b874..3feb012 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
@@ -23,6 +23,8 @@ import org.apache.lucene.geo.Polygon;
import org.apache.lucene.index.PointValues.Relation;
import org.apache.lucene.util.ArrayUtil;
+import static org.apache.lucene.geo.GeoUtils.orient;
+
/**
* 2D polygon implementation represented as a balanced interval tree of edges.
* <p>
@@ -454,24 +456,4 @@ public final class Polygon2D {
}
return newNode;
}
-
- /**
- * Returns a positive value if points a, b, and c are arranged in counter-clockwise order,
- * negative value if clockwise, zero if collinear.
- */
- // see the "Orient2D" method described here:
- // http://www.cs.berkeley.edu/~jrs/meshpapers/robnotes.pdf
- // https://www.cs.cmu.edu/~quake/robust.html
- // Note that this one does not yet have the floating point tricks to be exact!
- private static int orient(double ax, double ay, double bx, double by, double cx, double cy) {
- double v1 = (bx - ax) * (cy - ay);
- double v2 = (cx - ax) * (by - ay);
- if (v1 > v2) {
- return 1;
- } else if (v1 < v2) {
- return -1;
- } else {
- return 0;
- }
- }
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/b5ef1333/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
new file mode 100644
index 0000000..eabc326
--- /dev/null
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShape.java
@@ -0,0 +1,113 @@
+/*
+ * 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.util.ArrayList;
+import java.util.List;
+
+import org.apache.lucene.geo.Polygon;
+import org.apache.lucene.geo.Tessellator;
+import org.apache.lucene.geo.Tessellator.Triangle;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.NumericUtils;
+
+/**
+ * An indexed shape utility class.
+ * <p>
+ * {@link Polygon}'s are decomposed into a triangular mesh using the {@link Tessellator} utility class
+ * Each {@link Triangle} is encoded and indexed as a multi-value field.
+ * <p>
+ * Finding all shapes that intersect a range (e.g., bounding box) at search time is efficient.
+ * <p>
+ * This class defines static factory methods for common operations:
+ * <ul>
+ * <li>{@link #createIndexableFields(String, Polygon)} for matching polygons that intersect a bounding box.
+ * <li>{@link #newBoxQuery newBoxQuery()} for matching polygons that intersect a bounding box.
+ * </ul>
+
+ * <b>WARNING</b>: Like {@link LatLonPoint}, vertex values are indexed with some loss of precision from the
+ * original {@code double} values (4.190951585769653E-8 for the latitude component
+ * and 8.381903171539307E-8 for longitude).
+ * @see PointValues
+ * @see LatLonDocValuesField
+ *
+ * @lucene.experimental
+ */
+public class LatLonShape {
+ public static final int BYTES = LatLonPoint.BYTES;
+
+ protected static final FieldType TYPE = new FieldType();
+ static {
+ TYPE.setDimensions(6, BYTES);
+ TYPE.freeze();
+ }
+
+ // no instance:
+ private LatLonShape() {
+ }
+
+ /** the lionshare of the indexing is done by the tessellator */
+ public static Field[] createIndexableFields(String fieldName, Polygon polygon) {
+ List<Triangle> tessellation = Tessellator.tessellate(polygon);
+ List<LatLonTriangle> fields = new ArrayList<>();
+ for (int i = 0; i < tessellation.size(); ++i) {
+ fields.add(new LatLonTriangle(fieldName, tessellation.get(i)));
+ }
+ return fields.toArray(new Field[fields.size()]);
+ }
+
+ /** create a query to find all polygons that intersect a defined bounding box
+ * note: does not currently support dateline crossing boxes
+ * todo split dateline crossing boxes into two queries like {@link LatLonPoint#newBoxQuery}
+ **/
+ public static Query newBoxQuery(String field, double minLatitude, double maxLatitude, double minLongitude, double maxLongitude) {
+ return new LatLonShapeBoundingBoxQuery(field, minLatitude, maxLatitude, minLongitude, maxLongitude);
+ }
+
+ /** polygons are decomposed into tessellated triangles using {@link org.apache.lucene.geo.Tessellator}
+ * these triangles are encoded and inserted as separate indexed POINT fields
+ */
+ private static class LatLonTriangle extends Field {
+
+ public LatLonTriangle(String name, Triangle t) {
+ super(name, TYPE);
+ setTriangleValue(t.getEncodedX(0), t.getEncodedY(0),
+ t.getEncodedX(1), t.getEncodedY(1),
+ t.getEncodedX(2), t.getEncodedY(2));
+ }
+
+ public void setTriangleValue(int aX, int aY, int bX, int bY, int cX, int cY) {
+ final byte[] bytes;
+
+ if (fieldsData == null) {
+ bytes = new byte[24];
+ fieldsData = new BytesRef(bytes);
+ } else {
+ bytes = ((BytesRef) fieldsData).bytes;
+ }
+
+ NumericUtils.intToSortableBytes(aY, bytes, 0);
+ NumericUtils.intToSortableBytes(aX, bytes, BYTES);
+ NumericUtils.intToSortableBytes(bY, bytes, BYTES * 2);
+ NumericUtils.intToSortableBytes(bX, bytes, BYTES * 3);
+ NumericUtils.intToSortableBytes(cY, bytes, BYTES * 4);
+ NumericUtils.intToSortableBytes(cX, bytes, BYTES * 5);
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/b5ef1333/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java
new file mode 100644
index 0000000..75ba931
--- /dev/null
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java
@@ -0,0 +1,415 @@
+/*
+ * 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.Polygon;
+import org.apache.lucene.geo.Tessellator;
+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.BitSetIterator;
+import org.apache.lucene.util.DocIdSetBuilder;
+import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.FutureArrays;
+import org.apache.lucene.util.NumericUtils;
+
+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;
+
+/**
+ * Finds all previously indexed shapes that intersect the specified bounding box.
+ *
+ * <p>The field must be indexed using
+ * {@link org.apache.lucene.document.LatLonShape#createIndexableFields(String, Polygon)} added per document.
+ *
+ * @lucene.experimental
+ **/
+class LatLonShapeBoundingBoxQuery extends Query {
+ final String field;
+ final byte[] bbox;
+ final int minX;
+ final int maxX;
+ final int minY;
+ final int maxY;
+
+ public LatLonShapeBoundingBoxQuery(String field, double minLat, double maxLat, double minLon, double maxLon) {
+ if (minLon > maxLon) {
+ throw new IllegalArgumentException("dateline crossing bounding box queries are not supported for [" + field + "]");
+ }
+ this.field = field;
+ this.bbox = new byte[4 * LatLonPoint.BYTES];
+ this.minX = encodeLongitudeCeil(minLon);
+ this.maxX = encodeLongitude(maxLon);
+ this.minY = encodeLatitudeCeil(minLat);
+ this.maxY = encodeLatitude(maxLat);
+ NumericUtils.intToSortableBytes(this.minY, this.bbox, 0);
+ NumericUtils.intToSortableBytes(this.minX, this.bbox, LatLonPoint.BYTES);
+ NumericUtils.intToSortableBytes(this.maxY, this.bbox, 2 * LatLonPoint.BYTES);
+ NumericUtils.intToSortableBytes(this.maxX, this.bbox, 3 * LatLonPoint.BYTES);
+ }
+
+ @Override
+ public final Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost) throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+
+ private boolean queryContains(byte[] t, int point) {
+ final int yIdx = 2 * LatLonPoint.BYTES * point;
+ final int xIdx = yIdx + LatLonPoint.BYTES;
+
+ if (FutureArrays.compareUnsigned(t, yIdx, xIdx, bbox, 0, LatLonPoint.BYTES) < 0 || //minY
+ FutureArrays.compareUnsigned(t, yIdx, xIdx, bbox, 2 * LatLonPoint.BYTES, 3 * LatLonPoint.BYTES) > 0 || //maxY
+ FutureArrays.compareUnsigned(t, xIdx, xIdx + LatLonPoint.BYTES, bbox, LatLonPoint.BYTES, 2 * LatLonPoint.BYTES) < 0 || // minX
+ FutureArrays.compareUnsigned(t, xIdx, xIdx + LatLonPoint.BYTES, bbox, 3 * LatLonPoint.BYTES, bbox.length) > 0) {
+ return false;
+ }
+ return true;
+ }
+
+ private boolean queryIntersects(int ax, int ay, int bx, int by, int cx, int cy) {
+ // top
+ if (Tessellator.linesIntersect(minX, maxY, maxX, maxY, ax, ay, bx, by) ||
+ Tessellator.linesIntersect(minX, maxY, maxX, maxY, bx, by, cx, cy) ||
+ Tessellator.linesIntersect(minX, maxY, maxX, maxY, cx, cy, ax, ay)) {
+ return true;
+ }
+
+ // bottom
+ if (Tessellator.linesIntersect(minX, minY, maxX, minY, ax, ay, bx, by) ||
+ Tessellator.linesIntersect(minX, minY, maxX, minY, bx, by, cx, cy) ||
+ Tessellator.linesIntersect(minX, minY, maxX, minY, cx, cy, ax, ay)) {
+ return true;
+ }
+
+ // left
+ if (Tessellator.linesIntersect(minX, minY, minX, maxY, ax, ay, bx, by) ||
+ Tessellator.linesIntersect(minX, minY, minX, maxY, bx, by, cx, cy) ||
+ Tessellator.linesIntersect(minX, minY, minX, maxY, cx, cy, ax, ay)) {
+ return true;
+ }
+
+ // right
+ if (Tessellator.linesIntersect(maxX, minY, maxX, maxY, ax, ay, bx, by) ||
+ Tessellator.linesIntersect(maxX, minY, maxX, maxY, bx, by, cx, cy) ||
+ Tessellator.linesIntersect(maxX, minY, maxX, maxY, cx, cy, ax, ay)) {
+ return true;
+ }
+ return false;
+ }
+
+ private boolean queryCrossesTriangle(byte[] t) {
+ // 1. query contains any triangle points
+ if (queryContains(t, 0) || queryContains(t, 1) || queryContains(t, 2)) {
+ return true;
+ }
+
+ int aY = NumericUtils.sortableBytesToInt(t, 0);
+ int aX = NumericUtils.sortableBytesToInt(t, LatLonPoint.BYTES);
+ int bY = NumericUtils.sortableBytesToInt(t, 2 * LatLonPoint.BYTES);
+ int bX = NumericUtils.sortableBytesToInt(t, 3 * LatLonPoint.BYTES);
+ int cY = NumericUtils.sortableBytesToInt(t, 4 * LatLonPoint.BYTES);
+ int cX = NumericUtils.sortableBytesToInt(t, 5 * LatLonPoint.BYTES);
+
+ int tMinX = StrictMath.min(StrictMath.min(aX, bX), cX);
+ int tMaxX = StrictMath.max(StrictMath.max(aX, bX), cX);
+ int tMinY = StrictMath.min(StrictMath.min(aY, bY), cY);
+ int tMaxY = StrictMath.max(StrictMath.max(aY, bY), cY);
+
+ // 2. check bounding boxes are disjoint
+ if (tMaxX < minX || tMinX > maxX || tMinY > maxY || tMaxY < minY) {
+ return false;
+ }
+
+ // 3. check triangle contains any query points
+ if (Tessellator.pointInTriangle(minX, minY, aX, aY, bX, bY, cX, cY)) {
+ return true;
+ } else if (Tessellator.pointInTriangle(maxX, minY, aX, aY, bX, bY, cX, cY)) {
+ return true;
+ } else if (Tessellator.pointInTriangle(maxX, maxY, aX, aY, bX, bY, cX, cY)) {
+ return true;
+ } else if (Tessellator.pointInTriangle(minX, maxY, aX, aY, bX, bY, cX, cY)) {
+ return true;
+ }
+
+
+ // 4. last ditch effort: check crossings
+ if (queryIntersects(aX, aY, bX, bY, cX, cY)) {
+ return true;
+ }
+ return false;
+ }
+
+ 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;
+
+ // check bounding box (DISJOINT)
+ if (FutureArrays.compareUnsigned(minTriangle, minXOfs, minXOfs + LatLonPoint.BYTES, bbox, 3 * LatLonPoint.BYTES, 4 * LatLonPoint.BYTES) > 0 ||
+ FutureArrays.compareUnsigned(maxTriangle, maxXOfs, maxXOfs + LatLonPoint.BYTES, bbox, LatLonPoint.BYTES, 2 * LatLonPoint.BYTES) < 0 ||
+ FutureArrays.compareUnsigned(minTriangle, minYOfs, minYOfs + LatLonPoint.BYTES, bbox, 2 * LatLonPoint.BYTES, 3 * LatLonPoint.BYTES) > 0 ||
+ FutureArrays.compareUnsigned(maxTriangle, maxYOfs, maxYOfs + LatLonPoint.BYTES, bbox, 0, LatLonPoint.BYTES) < 0) {
+ return Relation.CELL_OUTSIDE_QUERY;
+ }
+
+ if (FutureArrays.compareUnsigned(minTriangle, minXOfs, minXOfs + LatLonPoint.BYTES, bbox, LatLonPoint.BYTES, 2 * LatLonPoint.BYTES) > 0 &&
+ FutureArrays.compareUnsigned(maxTriangle, maxXOfs, maxXOfs + LatLonPoint.BYTES, bbox, 3 * LatLonPoint.BYTES, 4 * LatLonPoint.BYTES) < 0 &&
+ FutureArrays.compareUnsigned(minTriangle, minYOfs, minYOfs + LatLonPoint.BYTES, bbox, 0, LatLonPoint.BYTES) > 0 &&
+ FutureArrays.compareUnsigned(maxTriangle, maxYOfs, maxYOfs + LatLonPoint.BYTES, bbox, 2 * LatLonPoint.BYTES, 2 * LatLonPoint.BYTES) < 0) {
+ return Relation.CELL_INSIDE_QUERY;
+ }
+ return Relation.CELL_CROSSES_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);
+ }
+ };
+ }
+
+ /**
+ * Create a visitor that clears documents that do NOT match the bounding box query.
+ */
+ private IntersectVisitor getInverseIntersectVisitor(FixedBitSet result, int[] cost) {
+ return new IntersectVisitor() {
+
+ @Override
+ public void visit(int docID) {
+ result.clear(docID);
+ cost[0]--;
+ }
+
+ @Override
+ public void visit(int docID, byte[] packedTriangle) {
+ if (queryCrossesTriangle(packedTriangle)) {
+ result.clear(docID);
+ cost[0]--;
+ }
+ }
+
+ @Override
+ public Relation compare(byte[] minPackedValue, byte[] maxPackedValue) {
+ Relation r = relateRangeToQuery(minPackedValue, maxPackedValue);
+ if (r == Relation.CELL_OUTSIDE_QUERY) {
+ return Relation.CELL_INSIDE_QUERY;
+ } else if (r == Relation.CELL_INSIDE_QUERY || r == Relation.CELL_CROSSES_QUERY) {
+ return Relation.CELL_OUTSIDE_QUERY;
+ }
+ return r;
+ }
+ };
+ }
+
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ LeafReader reader = context.reader();
+ PointValues values = reader.getPointValues(field);
+ if (values == null) {
+ return null;
+ }
+
+ boolean allDocsMatch = true;
+ if (values.getDocCount() != reader.maxDoc() ||
+ relateRangeToQuery(values.getMinPackedValue(), values.getMaxPackedValue()) != Relation.CELL_INSIDE_QUERY) {
+ allDocsMatch = false;
+ }
+
+ final Weight weight = this;
+ if (allDocsMatch) {
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ return new ConstantScoreScorer(weight, score(),
+ DocIdSetIterator.all(reader.maxDoc()));
+ }
+
+ @Override
+ public long cost() {
+ return reader.maxDoc();
+ }
+ };
+ } else {
+ return new ScorerSupplier() {
+ final DocIdSetBuilder result = new DocIdSetBuilder(reader.maxDoc(), values, field);
+ final IntersectVisitor visitor = getIntersectVisitor(result);
+ long cost = -1;
+
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (values.getDocCount() == reader.maxDoc()
+ && values.getDocCount() == values.size()
+ && cost() > reader.maxDoc() / 2) {
+ // If all docs have exactly one value and the cost is greater
+ // than half the leaf size then maybe we can make things faster
+ // by computing the set of documents that do NOT match the query
+ final FixedBitSet result = new FixedBitSet(reader.maxDoc());
+ result.set(0, reader.maxDoc());
+ int[] cost = new int[]{reader.maxDoc()};
+ values.intersect(getInverseIntersectVisitor(result, cost));
+ final DocIdSetIterator iterator = new BitSetIterator(result, cost[0]);
+ return new ConstantScoreScorer(weight, score(), iterator);
+ }
+
+ 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 boolean equals(Object o) {
+ return sameClassAs(o) && equalsTo(getClass().cast(o));
+ }
+
+ private boolean equalsTo(LatLonShapeBoundingBoxQuery o) {
+ return Objects.equals(field, o.field) &&
+ Arrays.equals(bbox, o.bbox);
+ }
+
+ @Override
+ public int hashCode() {
+ int hash = classHash();
+ hash = 31 * hash + field.hashCode();
+ hash = 31 * hash + Arrays.hashCode(bbox);
+ return hash;
+ }
+
+ @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("Rectangle(lat=");
+ sb.append(decodeLatitude(minY));
+ sb.append(" TO ");
+ sb.append(decodeLatitude(maxY));
+ sb.append(" lon=");
+ sb.append(decodeLongitude(minX));
+ sb.append(" TO ");
+ sb.append(decodeLongitude(maxX));
+ sb.append(")");
+ return sb.toString();
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/b5ef1333/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java b/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
new file mode 100644
index 0000000..c4e52a1
--- /dev/null
+++ b/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
@@ -0,0 +1,910 @@
+/*
+ * 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.geo;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.apache.lucene.geo.GeoUtils.WindingOrder;
+import org.apache.lucene.util.BitUtil;
+
+import static org.apache.lucene.geo.GeoEncodingUtils.encodeLatitude;
+import static org.apache.lucene.geo.GeoEncodingUtils.encodeLongitude;
+import static org.apache.lucene.geo.GeoUtils.orient;
+
+/**
+ * Computes a triangular mesh tessellation for a given polygon.
+ * <p>
+ * This is inspired by mapbox's earcut algorithm (https://github.com/mapbox/earcut)
+ * which is a modification to FIST (https://www.cosy.sbg.ac.at/~held/projects/triang/triang.html)
+ * written by Martin Held, and ear clipping (https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf)
+ * written by David Eberly.
+ * <p>
+ * Notes:
+ * <ul>
+ * <li>Requires valid polygons:
+ * <ul>
+ * <li>No self intersections
+ * <li>Holes may only touch at one vertex
+ * <li>Polygon must have an area (e.g., no "line" boxes)
+ * <li>sensitive to overflow (e.g, subatomic values such as E-200 can cause unexpected behavior)
+ * </ul>
+ * </ul>
+ * <p>
+ * The code is a modified version of the javascript implementation provided by MapBox
+ * under the following license:
+ * <p>
+ * ISC License
+ * <p>
+ * Copyright (c) 2016, Mapbox
+ * <p>
+ * Permission to use, copy, modify, and/or distribute this software for any purpose
+ * with or without fee is hereby granted, provided that the above copyright notice
+ * and this permission notice appear in all copies.
+ * <p>
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH'
+ * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
+ * FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
+ * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
+ * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+ * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
+ * THIS SOFTWARE.
+ *
+ * @lucene.experimental
+ */
+final public class Tessellator {
+ // this is a dumb heuristic to control whether we cut over to sorted morton values
+ private static final int VERTEX_THRESHOLD = 80;
+
+ /** state of the tessellated split - avoids recursion */
+ private enum State {
+ INIT, CURE, SPLIT
+ }
+
+ // No Instance:
+ private Tessellator() {}
+
+ /** Produces an array of vertices representing the triangulated result set of the Points array */
+ public static final List<Triangle> tessellate(final Polygon polygon) {
+ // Attempt to establish a doubly-linked list of the provided shell points (should be CCW, but this will correct);
+ // then filter instances of intersections.
+ Node outerNode = createDoublyLinkedList(polygon, WindingOrder.CCW);
+ // If an outer node hasn't been detected, the shape is malformed. (must comply with OGC SFA specification)
+ if(outerNode == null) {
+ throw new IllegalArgumentException("Malformed shape detected in Tessellator!");
+ }
+
+ // Determine if the specified list of points contains holes
+ if (polygon.numHoles() > 0) {
+ // Eliminate the hole triangulation.
+ outerNode = eliminateHoles(polygon, outerNode);
+ }
+
+ // If the shape crosses VERTEX_THRESHOLD, use z-order curve hashing:
+ final boolean mortonOptimized;
+ {
+ int threshold = VERTEX_THRESHOLD - polygon.numPoints();
+ for (int i = 0; threshold >= 0 && i < polygon.numHoles(); ++i) {
+ threshold -= polygon.getHole(i).numPoints();
+ }
+
+ // Link polygon nodes in Z-Order
+ mortonOptimized = threshold < 0;
+ if (mortonOptimized == true) {
+ sortByMorton(outerNode);
+ }
+ }
+ // Calculate the tessellation using the doubly LinkedList.
+ List<Triangle> result = earcutLinkedList(outerNode, new ArrayList<>(), State.INIT, mortonOptimized);
+ if (result.size() == 0) {
+ throw new IllegalArgumentException("Unable to Tessellate shape [" + polygon + "]. Possible malformed shape detected.");
+ }
+
+ return result;
+ }
+
+ /** Creates a circular doubly linked list using polygon points. The order is governed by the specified winding order */
+ private static final Node createDoublyLinkedList(final Polygon polygon, final WindingOrder windingOrder) {
+ Node lastNode = null;
+ // Link points into the circular doubly-linked list in the specified winding order
+ if (windingOrder == polygon.getWindingOrder()) {
+ for (int i = 0; i < polygon.numPoints(); ++i) {
+ if (lastNode == null || filter(polygon, i, lastNode) == false) {
+ lastNode = insertNode(polygon, i, lastNode);
+ }
+ }
+ } else {
+ for (int i = polygon.numPoints() - 1; i >= 0; --i) {
+ if (lastNode == null || filter(polygon, i, lastNode) == false) {
+ lastNode = insertNode(polygon, i, lastNode);
+ }
+ }
+ }
+ // if first and last node are the same then remove the end node and set lastNode to the start
+ if (lastNode != null && isVertexEquals(lastNode, lastNode.next)) {
+ removeNode(lastNode);
+ lastNode = lastNode.next;
+ }
+
+ // Return the last node in the Doubly-Linked List
+ return lastNode;
+ }
+
+ /** Links every hole into the outer loop, producing a single-ring polygon without holes. **/
+ private static final Node eliminateHoles(final Polygon polygon, Node outerNode) {
+ // Define a list to hole a reference to each filtered hole list.
+ final List<Node> holeList = new ArrayList<>();
+ // Iterate through each array of hole vertices.
+ Polygon[] holes = polygon.getHoles();
+ for(int i = 0; i < polygon.numHoles(); ++i) {
+ // create the doubly-linked hole list
+ Node list = createDoublyLinkedList(holes[i], WindingOrder.CW);
+ if (list == list.next) {
+ list.isSteiner = true;
+ }
+ // Determine if the resulting hole polygon was successful.
+ if(list != null) {
+ // Add the leftmost vertex of the hole.
+ holeList.add(fetchLeftmost(list));
+ }
+ }
+
+ // Sort the hole vertices by x coordinate
+ holeList.sort((Node pNodeA, Node pNodeB) ->
+ pNodeA.getX() < pNodeB.getX() ? -1 : pNodeA.getX() == pNodeB.getX() ? 0 : 1);
+
+ // Process holes from left to right.
+ for(int i = 0; i < holeList.size(); ++i) {
+ // Eliminate hole triangles from the result set
+ final Node holeNode = holeList.get(i);
+ eliminateHole(holeNode, outerNode);
+ // Filter the new polygon.
+ outerNode = filterPoints(outerNode, outerNode.next);
+ }
+ // Return a pointer to the list.
+ return outerNode;
+ }
+
+ /** Finds a bridge between vertices that connects a hole with an outer ring, and links it */
+ private static final void eliminateHole(final Node holeNode, Node outerNode) {
+ // Attempt to find a logical bridge between the HoleNode and OuterNode.
+ outerNode = fetchHoleBridge(holeNode, outerNode);
+ // Determine whether a hole bridge could be fetched.
+ if(outerNode != null) {
+ // Split the resulting polygon.
+ Node node = splitPolygon(outerNode, holeNode);
+ // Filter the split nodes.
+ filterPoints(node, node.next);
+ }
+ }
+
+ /**
+ * David Eberly's algorithm for finding a bridge between a hole and outer polygon
+ *
+ * see: http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf
+ **/
+ private static final Node fetchHoleBridge(final Node holeNode, final Node outerNode) {
+ Node p = outerNode;
+ double qx = Double.NEGATIVE_INFINITY;
+ final double hx = holeNode.getX();
+ final double hy = holeNode.getY();
+ Node connection = null;
+ // 1. find a segment intersected by a ray from the hole's leftmost point to the left;
+ // segment's endpoint with lesser x will be potential connection point
+ {
+ do {
+ if (hy <= p.getY() && hy >= p.next.getY()) {
+ final double x = p.getX() + (hy - p.getY()) * (p.next.getX() - p.getX()) / (p.next.getY() - p.getY());
+ if (x <= hx && x > qx) {
+ qx = x;
+ connection = (p.getX() < p.next.getX()) ? p : p.next;
+ }
+ }
+ p = p.next;
+ } while (p != outerNode);
+ }
+
+ if (connection == null) {
+ return null;
+ } else if (hx == connection.getX()) {
+ return connection.previous;
+ }
+
+ // 2. look for points inside the triangle of hole point, segment intersection, and endpoint
+ // its a valid connection iff there are no points found;
+ // otherwise choose the point of the minimum angle with the ray as the connection point
+ Node stop = connection;
+ final double mx = connection.getX();
+ final double my = connection.getY();
+ double tanMin = Double.POSITIVE_INFINITY;
+ double tan;
+ p = connection.next;
+ {
+ while (p != stop) {
+ if (hx > p.getX() && p.getX() >= mx && pointInEar(hy < my ? hx : qx, hy, mx, my, hy < my ? qx : hx, hy, mx, my)) {
+ tan = Math.abs(hy - my) / (hx - mx); // tangential
+ if ((tan < tanMin || (tan == tanMin && p.getX() > connection.getX())) && isLocallyInside(p, holeNode)) {
+ connection = p;
+ tanMin = tan;
+ }
+ }
+ p = p.next;
+ }
+ }
+
+ return connection;
+ }
+
+ /** Finds the left-most hole of a polygon ring. **/
+ private static final Node fetchLeftmost(final Node start) {
+ Node node = start;
+ Node leftMost = start;
+ do {
+ // Determine if the current node possesses a lesser X position.
+ if (node.getX() < leftMost.getX()) {
+ // Maintain a reference to this Node.
+ leftMost = node;
+ }
+ // Progress the search to the next node in the doubly-linked list.
+ node = node.next;
+ } while (node != start);
+
+ // Return the node with the smallest X value.
+ return leftMost;
+ }
+
+ /** Main ear slicing loop which triangulates the vertices of a polygon, provided as a doubly-linked list. **/
+ private static final List<Triangle> earcutLinkedList(Node currEar, final List<Triangle> tessellation,
+ State state, final boolean mortonOptimized) {
+ earcut : do {
+ if (currEar == null || currEar.previous == currEar.next) {
+ return tessellation;
+ }
+
+ Node stop = currEar;
+ Node prevNode;
+ Node nextNode;
+
+ // Iteratively slice ears
+ do {
+ prevNode = currEar.previous;
+ nextNode = currEar.next;
+ // Determine whether the current triangle must be cut off.
+ final boolean isReflex = area(prevNode.getX(), prevNode.getY(), currEar.getX(), currEar.getY(), nextNode.getX(), nextNode.getY()) >= 0;
+ if (isReflex == false && isEar(currEar, mortonOptimized) == true) {
+ // Return the triangulated data
+ tessellation.add(new Triangle(prevNode, currEar, nextNode));
+ // Remove the ear node.
+ removeNode(currEar);
+
+ // Skipping to the next node leaves fewer slither triangles.
+ currEar = nextNode.next;
+ stop = nextNode.next;
+ continue;
+ }
+ currEar = nextNode;
+
+ // If the whole polygon has been iterated over and no more ears can be found.
+ if (currEar == stop) {
+ switch (state) {
+ case INIT:
+ // try filtering points and slicing again
+ currEar = filterPoints(currEar, null);
+ state = State.CURE;
+ continue earcut;
+ case CURE:
+ // if this didn't work, try curing all small self-intersections locally
+ currEar = cureLocalIntersections(currEar, tessellation);
+ state = State.SPLIT;
+ continue earcut;
+ case SPLIT:
+ // as a last resort, try splitting the remaining polygon into two
+ splitEarcut(currEar, tessellation, mortonOptimized);
+ break;
+ }
+ break;
+ }
+ } while (currEar.previous != currEar.next);
+ break;
+ } while (true);
+ // Return the calculated tessellation
+ return tessellation;
+ }
+
+ /** Determines whether a polygon node forms a valid ear with adjacent nodes. **/
+ private static final boolean isEar(final Node ear, final boolean mortonOptimized) {
+ if (mortonOptimized == true) {
+ return mortonIsEar(ear);
+ }
+
+ // make sure there aren't other points inside the potential ear
+ Node node = ear.next.next;
+ while (node != ear.previous) {
+ if (pointInEar(node.getX(), node.getY(), ear.previous.getX(), ear.previous.getY(), ear.getX(), ear.getY(), ear.next.getX(), ear.next.getY())
+ && area(node.previous.getX(), node.previous.getY(), node.getX(), node.getY(),
+ node.next.getX(), node.next.getY()) >= 0) {
+ return false;
+ }
+ node = node.next;
+ }
+ return true;
+ }
+
+ /** Uses morton code for speed to determine whether or a polygon node forms a valid ear w/ adjacent nodes */
+ private static final boolean mortonIsEar(final Node ear) {
+ double ax = ear.previous.x;
+ double ay = ear.previous.y;
+ double bx = ear.x;
+ double by = ear.y;
+ double cx = ear.next.x;
+ double cy = ear.next.y;
+
+ // now make sure we don't have other points inside the potential ear;
+ Node node;
+ int idx;
+
+ // triangle bbox (flip the bits so negative encoded values are < positive encoded values)
+ int minTX = StrictMath.min(StrictMath.min(ear.previous.x, ear.x), ear.next.x) ^ 0x80000000;
+ int minTY = StrictMath.min(StrictMath.min(ear.previous.y, ear.y), ear.next.y) ^ 0x80000000;
+ int maxTX = StrictMath.max(StrictMath.max(ear.previous.x, ear.x), ear.next.x) ^ 0x80000000;
+ int maxTY = StrictMath.max(StrictMath.max(ear.previous.y, ear.y), ear.next.y) ^ 0x80000000;
+
+ // z-order range for the current triangle bbox;
+ long minZ = BitUtil.interleave(minTX, minTY);
+ long maxZ = BitUtil.interleave(maxTX, maxTY);
+
+ // first look for points inside the triangle in increasing z-order
+ node = ear.nextZ;
+ while (node != null && Long.compareUnsigned(node.morton, maxZ) <= 0) {
+ if (Long.compareUnsigned(node.morton, maxZ) <= 0) {
+ idx = node.idx;
+ if (idx != ear.previous.idx && idx != ear.next.idx
+ && pointInEar(node.x, node.y, ax, ay, bx, by, cx, cy)
+ && area(node.previous.x, node.previous.y, node.x, node.y, node.next.x, node.next.y) >= 0) {
+ return false;
+ }
+ }
+ node = node.nextZ;
+ }
+ // then look for points in decreasing z-order
+ node = ear.previousZ;
+ while (node != null &&
+ Long.compareUnsigned(node.morton, minZ) >= 0) {
+ if (Long.compareUnsigned(node.morton, maxZ) <= 0) {
+ idx = node.idx;
+ if (idx != ear.previous.idx && idx != ear.next.idx
+ && pointInEar(node.x, node.y, ax, ay, bx, by, cx, cy)
+ && area(node.previous.x, node.previous.y, node.x, node.y, node.next.x, node.next.y) >= 0) {
+ return false;
+ }
+ }
+ node = node.previousZ;
+ }
+ return true;
+ }
+
+ /** Iterate through all polygon nodes and remove small local self-intersections **/
+ private static final Node cureLocalIntersections(Node startNode, final List<Triangle> tessellation) {
+ Node node = startNode;
+ Node nextNode;
+ do {
+ nextNode = node.next;
+ Node a = node.previous;
+ Node b = nextNode.next;
+
+ // a self-intersection where edge (v[i-1],v[i]) intersects (v[i+1],v[i+2])
+ if (isVertexEquals(a, b) == false
+ && linesIntersect(a.getX(), a.getY(), node.getX(), node.getY(), nextNode.getX(), nextNode.getY(), b.getX(), b.getY())
+ && isLocallyInside(a, b) && isLocallyInside(b, a)) {
+ // Return the triangulated vertices to the tessellation
+ tessellation.add(new Triangle(a, node, b));
+
+ // remove two nodes involved
+ removeNode(node);
+ removeNode(node.next);
+ node = startNode = b;
+ }
+ node = node.next;
+ } while (node != startNode);
+
+ return node;
+ }
+
+ /** Attempt to split a polygon and independently triangulate each side **/
+ private static final void splitEarcut(final Node start, final List<Triangle> tessellation, final boolean mortonIndexed) {
+ // Search for a valid diagonal that divides the polygon into two.
+ Node searchNode = start;
+ Node nextNode;
+ do {
+ nextNode = searchNode.next;
+ Node diagonal = nextNode.next;
+ while (diagonal != searchNode.previous) {
+ if(isValidDiagonal(searchNode, diagonal)) {
+ // Split the polygon into two at the point of the diagonal
+ Node splitNode = splitPolygon(searchNode, diagonal);
+ // Filter the resulting polygon.
+ searchNode = filterPoints(searchNode, searchNode.next);
+ splitNode = filterPoints(splitNode, splitNode.next);
+ // Attempt to earcut both of the resulting polygons
+ earcutLinkedList(searchNode, tessellation, State.INIT, mortonIndexed);
+ earcutLinkedList(splitNode, tessellation, State.INIT, mortonIndexed);
+ // Finish the iterative search
+ return;
+ }
+ diagonal = diagonal.next;
+ }
+ searchNode = searchNode.next;
+ } while (searchNode != start);
+ }
+
+ /** Links two polygon vertices using a bridge. **/
+ private static final Node splitPolygon(final Node a, final Node b) {
+ final Node a2 = new Node(a);
+ final Node b2 = new Node(b);
+ final Node an = a.next;
+ final Node bp = b.previous;
+
+ a.next = b;
+ a.nextZ = b;
+ b.previous = a;
+ b.previousZ = a;
+ an.previous = a2;
+ an.previousZ = a2;
+ b2.next = a2;
+ b2.nextZ = a2;
+ a2.previous = b2;
+ a2.previousZ = b2;
+ bp.next = b2;
+ bp.nextZ = b2;
+
+ return b2;
+ }
+
+ /** Determines whether a diagonal between two polygon nodes lies within a polygon interior. (This determines the validity of the ray.) **/
+ private static final boolean isValidDiagonal(final Node a, final Node b) {
+ return a.next.idx != b.idx && a.previous.idx != b.idx
+ && isIntersectingPolygon(a, a.getX(), a.getY(), b.getX(), b.getY()) == false
+ && isLocallyInside(a, b) && isLocallyInside(b, a)
+ && middleInsert(a, a.getX(), a.getY(), b.getX(), b.getY());
+ }
+
+ private static final boolean isLocallyInside(final Node a, final Node b) {
+ // if a is cw
+ if (area(a.previous.getX(), a.previous.getY(), a.getX(), a.getY(), a.next.getX(), a.next.getY()) < 0) {
+ return area(a.getX(), a.getY(), b.getX(), b.getY(), a.next.getX(), a.next.getY()) >= 0
+ && area(a.getX(), a.getY(), a.previous.getX(), a.previous.getY(), b.getX(), b.getY()) >= 0;
+ }
+ // ccw
+ return area(a.getX(), a.getY(), b.getX(), b.getY(), a.previous.getX(), a.previous.getY()) < 0
+ || area(a.getX(), a.getY(), a.next.getX(), a.next.getY(), b.getX(), b.getY()) < 0;
+ }
+
+ /** Determine whether the middle point of a polygon diagonal is contained within the polygon */
+ private static final boolean middleInsert(final Node start, final double x0, final double y0,
+ final double x1, final double y1) {
+ Node node = start;
+ Node nextNode;
+ boolean lIsInside = false;
+ final double lDx = (x0 + x1) / 2.0f;
+ final double lDy = (y0 + y1) / 2.0f;
+ do {
+ nextNode = node.next;
+ if (node.getY() > lDy != nextNode.getY() > lDy &&
+ lDx < (nextNode.getX() - node.getX()) * (lDy - node.getY()) / (nextNode.getY() - node.getY()) + node.getX()) {
+ lIsInside = !lIsInside;
+ }
+ node = node.next;
+ } while (node != start);
+ return lIsInside;
+ }
+
+ /** Determines if the diagonal of a polygon is intersecting with any polygon elements. **/
+ private static final boolean isIntersectingPolygon(final Node start, final double x0, final double y0,
+ final double x1, final double y1) {
+ Node node = start;
+ Node nextNode;
+ do {
+ nextNode = node.next;
+ if(node.getX() != x0 && node.getY() != y0 && nextNode.getX() != x0
+ && nextNode.getY() != y0 && node.getX() != x1 && node.getY() != y1
+ && nextNode.getX() != x1 && nextNode.getY() != y1) {
+ return linesIntersect(node.getX(), node.getY(), nextNode.getX(), nextNode.getY(), x0, y0, x1, y1);
+ }
+ node = nextNode;
+ } while (node != start);
+
+ return false;
+ }
+
+ /** Determines whether two line segments intersect. **/
+ public static final boolean linesIntersect(final double aX0, final double aY0, final double aX1, final double aY1,
+ final double bX0, final double bY0, final double bX1, final double bY1) {
+ return (area(aX0, aY0, aX1, aY1, bX0, bY0) > 0) != (area(aX0, aY0, aX1, aY1, bX1, bY1) > 0)
+ && (area(bX0, bY0, bX1, bY1, aX0, aY0) > 0) != (area(bX0, bY0, bX1, bY1, aX1, aY1) > 0);
+ }
+
+ /** Interlinks polygon nodes in Z-Order. **/
+ private static final void sortByMorton(Node start) {
+ start.previousZ.nextZ = null;
+ start.previousZ = null;
+ // Sort the generated ring using Z ordering.
+ tathamSort(start);
+ }
+
+ /**
+ * Simon Tatham's doubly-linked list O(n log n) mergesort
+ * see: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
+ **/
+ private static final void tathamSort(Node list) {
+ Node p, q, e, tail;
+ int i, numMerges, pSize, qSize;
+ int inSize = 1;
+
+ if (list == null) {
+ return;
+ }
+
+ do {
+ p = list;
+ list = null;
+ tail = null;
+ // count number of merges in this pass
+ numMerges = 0;
+
+ while(p != null) {
+ ++numMerges;
+ // step 'insize' places along from p
+ q = p;
+ for (i = 0, pSize = 0; i < inSize && q != null; ++i, ++pSize, q = q.nextZ);
+ // if q hasn't fallen off end, we have two lists to merge
+ qSize = inSize;
+
+ // now we have two lists; merge
+ while (pSize > 0 || (qSize > 0 && q != null)) {
+ // decide whether next element of merge comes from p or q
+ if (pSize == 0) {
+ // p is empty; e must come from q
+ e = q;
+ q = q.nextZ;
+ --qSize;
+ } else if (qSize == 0 || q == null) {
+ // q is empty; e must come from p
+ e = p;
+ p = p.nextZ;
+ --pSize;
+ } else if (Long.compareUnsigned(p.morton, q.morton) <= 0) {
+ // first element of p is lower (or same); e must come from p
+ e = p;
+ p = p.nextZ;
+ --pSize;
+ } else {
+ // first element of q is lower; e must come from q
+ e = q;
+ q = q.nextZ;
+ --qSize;
+ }
+
+ if (tail != null) {
+ tail.nextZ = e;
+ } else {
+ list = e;
+ }
+ // maintain reverse pointers
+ e.previousZ = tail;
+ tail = e;
+ }
+ // now p has stepped 'insize' places along, and q has too
+ p = q;
+ }
+
+ tail.nextZ = null;
+ inSize *= 2;
+ } while (numMerges > 1);
+ }
+
+ /** utility method to filter a single duplicate or colinear triangle */
+ private static boolean filter(final Polygon polygon, final int i, final Node node) {
+ final double x = polygon.getPolyLon(i);
+ final double y = polygon.getPolyLat(i);
+ final boolean equal = (x == node.getX() && y == node.getY());
+ if (equal == true) {
+ return true;
+ } else if (node.previous == node || node.previous.previous == node) {
+ return false;
+ }
+ return area(node.previous.previous.getX(), node.previous.previous.getY(), node.previous.getX(), node.previous.getY(), x, y) == 0d;
+ }
+
+ /** Eliminate colinear/duplicate points from the doubly linked list */
+ private static final Node filterPoints(final Node start, Node end) {
+ if (start == null) {
+ return start;
+ }
+
+ if(end == null) {
+ end = start;
+ }
+
+ Node node = start;
+ Node nextNode;
+ Node prevNode;
+ boolean continueIteration;
+
+ do {
+ continueIteration = false;
+ nextNode = node.next;
+ prevNode = node.previous;
+ if (node.isSteiner == false && isVertexEquals(node, nextNode)
+ || area(prevNode.getX(), prevNode.getY(), node.getX(), node.getY(), nextNode.getX(), nextNode.getY()) == 0) {
+ // Remove the node
+ removeNode(node);
+ node = end = prevNode;
+
+ if (node == nextNode) {
+ break;
+ }
+ continueIteration = true;
+ } else {
+ node = nextNode;
+ }
+ } while (continueIteration || node != end);
+ return end;
+ }
+
+ /** Creates a node and optionally links it with a previous node in a circular doubly-linked list */
+ private static final Node insertNode(final Polygon polygon, int index, final Node lastNode) {
+ final Node node = new Node(polygon, index);
+ if(lastNode == null) {
+ node.previous = node;
+ node.previousZ = node;
+ node.next = node;
+ node.nextZ = node;
+ } else {
+ node.next = lastNode.next;
+ node.nextZ = lastNode.nextZ;
+ node.previous = lastNode;
+ node.previousZ = lastNode;
+ lastNode.next.previous = node;
+ lastNode.nextZ.previousZ = node;
+ lastNode.next = node;
+ lastNode.nextZ = node;
+ }
+ return node;
+ }
+
+ /** Removes a node from the doubly linked list */
+ private static final void removeNode(Node node) {
+ node.next.previous = node.previous;
+ node.previous.next = node.next;
+
+ if (node.previousZ != null) {
+ node.previousZ.nextZ = node.nextZ;
+ }
+ if (node.nextZ != null) {
+ node.nextZ.previousZ = node.previousZ;
+ }
+ }
+
+ /** Determines if two point vertices are equal. **/
+ private static final boolean isVertexEquals(final Node a, final Node b) {
+ return a.getX() == b.getX() && a.getY() == b.getY();
+ }
+
+ /** Compute signed area of triangle */
+ private static double area(final double aX, final double aY, final double bX, final double bY,
+ final double cX, final double cY) {
+ return (bY - aY) * (cX - bX) - (bX - aX) * (cY - bY);
+ }
+
+ /** Compute whether point is in a candidate ear */
+ private static boolean pointInEar(final double x, final double y, final double ax, final double ay,
+ final double bx, final double by, final double cx, final double cy) {
+ return (cx - x) * (ay - y) - (ax - x) * (cy - y) >= 0 &&
+ (ax - x) * (by - y) - (bx - x) * (ay - y) >= 0 &&
+ (bx - x) * (cy - y) - (cx - x) * (by - y) >= 0;
+ }
+
+ /** compute whether the given x, y point is in a triangle; uses the winding order method */
+ public static boolean pointInTriangle (double x, double y, double ax, double ay, double bx, double by, double cx, double cy) {
+ int a = orient(x, y, ax, ay, bx, by);
+ int b = orient(x, y, bx, by, cx, cy);
+ if (a == 0 || b == 0 || a < 0 == b < 0) {
+ int c = orient(x, y, cx, cy, ax, ay);
+ return c == 0 || (c < 0 == (b < 0 || a < 0));
+ }
+ return false;
+ }
+
+ /** Brute force compute if a point is in the polygon by traversing entire triangulation
+ * todo: speed this up using either binary tree or prefix coding (filtering by bounding box of triangle)
+ **/
+ public static final boolean pointInPolygon(final List<Triangle> tessellation, double lat, double lon) {
+ // each triangle
+ for (int i = 0; i < tessellation.size(); ++i) {
+ if (tessellation.get(i).containsPoint(lat, lon)) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /** Circular Doubly-linked list used for polygon coordinates */
+ protected static class Node {
+ // vertex index in the polygon
+ private final int idx;
+ // reference to the polygon for lat/lon values
+ private final Polygon polygon;
+ // encoded x value
+ private final int x;
+ // encoded y value
+ private final int y;
+ // morton code for sorting
+ private final long morton;
+
+ // previous node
+ private Node previous;
+ // next node
+ private Node next;
+ // previous z node
+ private Node previousZ;
+ // next z node
+ private Node nextZ;
+ // triangle center
+ private boolean isSteiner = false;
+
+ protected Node(final Polygon polygon, final int index) {
+ this.idx = index;
+ this.polygon = polygon;
+ this.y = encodeLatitude(polygon.getPolyLat(idx));
+ this.x = encodeLongitude(polygon.getPolyLon(idx));
+ this.morton = BitUtil.interleave(x ^ 0x80000000, y ^ 0x80000000);
+ this.previous = null;
+ this.next = null;
+ this.previousZ = null;
+ this.nextZ = null;
+ }
+
+ /** simple deep copy constructor */
+ protected Node(Node other) {
+ this.idx = other.idx;
+ this.polygon = other.polygon;
+ this.morton = other.morton;
+ this.x = other.x;
+ this.y = other.y;
+ this.previous = other.previous;
+ this.next = other.next;
+ this.previousZ = other.previousZ;
+ this.nextZ = other.nextZ;
+ }
+
+ /** get the x value */
+ public final double getX() {
+ return polygon.getPolyLon(idx);
+ }
+
+ /** get the y value */
+ public final double getY() {
+ return polygon.getPolyLat(idx);
+ }
+
+ /** get the longitude value */
+ public final double getLon() {
+ return polygon.getPolyLon(idx);
+ }
+
+ /** get the latitude value */
+ public final double getLat() {
+ return polygon.getPolyLat(idx);
+ }
+
+ /** compare nodes by y then x */
+ public int compare(Node other) {
+ if (this.getLat() > other.getLat()) {
+ return 1;
+ } else if (this.getLat() == other.getLat()) {
+ if (this.getLon() > other.getLon()) {
+ return 1;
+ } else if (this.getLon() == other.getLon()) {
+ return 0;
+ }
+ }
+ return -1;
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder builder = new StringBuilder();
+ if (this.previous == null)
+ builder.append("||-");
+ else
+ builder.append(this.previous.idx + " <- ");
+ builder.append(this.idx);
+ if (this.next == null)
+ builder.append(" -||");
+ else
+ builder.append(" -> " + this.next.idx);
+ return builder.toString();
+ }
+ }
+
+ /** Triangle in the tessellated mesh */
+ public final static class Triangle {
+ Node[] vertex = new Node[3];
+
+ protected Triangle(Node a, Node b, Node c) {
+ // sort nodes by morton value
+ Node tA = a;
+ Node tB = b;
+ Node tC = c;
+ Node temp;
+ if (a.compare(b) > 0) {
+ temp = tA;
+ tA = tB;
+ tB = temp;
+ }
+ if (b.compare(c) > 0) {
+ temp = tB;
+ tB = tC;
+ tC = temp;
+ }
+ if (a.compare(b) > 0) {
+ temp = tA;
+ tA = tB;
+ tB = temp;
+ }
+ this.vertex[0] = tA;
+ this.vertex[1] = tB;
+ this.vertex[2] = tC;
+ }
+
+ /** get quantized x value for the given vertex */
+ public int getEncodedX(int vertex) {
+ return this.vertex[vertex].x;
+ }
+
+ /** get quantized y value for the given vertex */
+ public int getEncodedY(int vertex) {
+ return this.vertex[vertex].y;
+ }
+
+ /** get latitude value for the given vertex */
+ public double getLat(int vertex) {
+ return this.vertex[vertex].getLat();
+ }
+
+ /** get longitude value for the given vertex */
+ public double getLon(int vertex) {
+ return this.vertex[vertex].getLon();
+ }
+
+ /** utility method to compute whether the point is in the triangle */
+ protected boolean containsPoint(double lat, double lon) {
+ return pointInTriangle(lon, lat,
+ vertex[0].getLon(), vertex[0].getLat(),
+ vertex[1].getLon(), vertex[1].getLat(),
+ vertex[2].getLon(), vertex[2].getLat());
+ }
+
+ /** pretty print the triangle vertices */
+ public String toString() {
+ String result = vertex[0].x + ", " + vertex[0].y + " " +
+ vertex[1].x + ", " + vertex[1].y + " " +
+ vertex[2].x + ", " + vertex[2].y;
+ return result;
+ }
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/b5ef1333/lucene/sandbox/src/java/org/apache/lucene/geo/package.html
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/geo/package.html b/lucene/sandbox/src/java/org/apache/lucene/geo/package.html
new file mode 100644
index 0000000..e9859bd
--- /dev/null
+++ b/lucene/sandbox/src/java/org/apache/lucene/geo/package.html
@@ -0,0 +1,31 @@
+<!--
+ 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.
+ -->
+
+<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
+<!-- not a package-info.java, because we already defined this package in core/ -->
+
+<html>
+<head>
+ <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
+</head>
+<body>
+This package contains geo utility classes:
+<ul>
+ <li>{@link org.apache.lucene.geo.Tessellator Tessellator} for decomposing shapes into a triangular mesh</li>
+</ul>
+</body>
+</html>
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/b5ef1333/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShape.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShape.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShape.java
new file mode 100644
index 0000000..2ac2b39
--- /dev/null
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShape.java
@@ -0,0 +1,124 @@
+/*
+ * 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 com.carrotsearch.randomizedtesting.generators.RandomNumbers;
+import org.apache.lucene.geo.GeoTestUtil;
+import org.apache.lucene.geo.Polygon;
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.index.RandomIndexWriter;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.util.LuceneTestCase;
+import org.apache.lucene.util.TestUtil;
+
+/** Test case for indexing polygons and querying by bounding box */
+public class TestLatLonShape extends LuceneTestCase {
+ protected static String FIELDNAME = "field";
+ 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 testRandomPolygons() throws Exception {
+ long avgIdxTime = 0;
+ int numVertices;
+ int numPolys = RandomNumbers.randomIntBetween(random(), 50, 100);
+
+ Directory dir = newDirectory();
+ RandomIndexWriter writer = new RandomIndexWriter(random(), dir);
+ long start, end;
+
+ Polygon polygon;
+ Document document;
+ System.out.println("generating " + numPolys + " polygons");
+ for (int i = 0; i < numPolys;) {
+ document = new Document();
+ numVertices = TestUtil.nextInt(random(), 200000, 500000);
+ polygon = GeoTestUtil.createRegularPolygon(0, 0, atLeast(1000000), numVertices);
+ System.out.println("adding polygon " + i);
+ start = System.currentTimeMillis();
+ addPolygonsToDoc(FIELDNAME, document, polygon);
+ writer.addDocument(document);
+ end = System.currentTimeMillis();
+ avgIdxTime += ((end - start) - avgIdxTime) / ++i;
+ }
+ System.out.println("avg index time: " + avgIdxTime);
+
+ // search within 50km and verify we found our doc
+ IndexReader reader = writer.getReader();
+ IndexSearcher searcher = newSearcher(reader);
+ start = System.currentTimeMillis();
+ assertEquals(0, searcher.count(newRectQuery("field", -89.9, -89.8, -179.9, -179.8d)));
+ end = System.currentTimeMillis();
+
+ System.out.println("search: " + (end - start));
+
+ reader.close();
+ writer.close();
+ dir.close();
+ }
+
+ /** test we can search for a point */
+ public void testBasicIntersects() throws Exception {
+ Directory dir = newDirectory();
+ RandomIndexWriter writer = new RandomIndexWriter(random(), dir);
+
+ int numVertices = TestUtil.nextInt(random(), 200000, 500000);
+
+ // add a random polygon without a hole
+ Polygon p = GeoTestUtil.createRegularPolygon(0, 90, atLeast(1000000), numVertices);
+ Document document = new Document();
+ addPolygonsToDoc(FIELDNAME, document, p);
+ writer.addDocument(document);
+
+ // add a random polygon with a hole
+ Polygon inner = new Polygon(new double[] {-1d, -1d, 1d, 1d, -1d},
+ new double[] {-91d, -89d, -89d, -91.0, -91.0});
+ Polygon outer = GeoTestUtil.createRegularPolygon(0, -90, atLeast(1000000), numVertices);
+
+ document = new Document();
+ addPolygonsToDoc(FIELDNAME, document, new Polygon(outer.getPolyLats(), outer.getPolyLons(), inner));
+ writer.addDocument(document);
+
+ ////// search /////
+ // search an intersecting bbox
+ IndexReader reader = writer.getReader();
+ IndexSearcher searcher = newSearcher(reader);
+ Query q = newRectQuery(FIELDNAME, -1d, 1d, p.minLon, p.maxLon);
+ assertEquals(1, searcher.count(q));
+
+ // search a disjoint bbox
+ q = newRectQuery(FIELDNAME, p.minLat-1d, p.minLat+1, p.minLon-1d, p.minLon+1d);
+ assertEquals(0, searcher.count(q));
+
+ // search a bbox in the hole
+ q = newRectQuery(FIELDNAME, inner.minLat + 1e-6, inner.maxLat - 1e-6, inner.minLon + 1e-6, inner.maxLon - 1e-6);
+ assertEquals(0, searcher.count(q));
+
+ reader.close();
+ writer.close();
+ dir.close();
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/b5ef1333/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
new file mode 100644
index 0000000..03941b9
--- /dev/null
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShapeQueries.java
@@ -0,0 +1,276 @@
+/*
+ * 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(200000);
+ }
+
+ 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);
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/b5ef1333/lucene/sandbox/src/test/org/apache/lucene/geo/TestTessellator.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/geo/TestTessellator.java b/lucene/sandbox/src/test/org/apache/lucene/geo/TestTessellator.java
new file mode 100644
index 0000000..494d4e5
--- /dev/null
+++ b/lucene/sandbox/src/test/org/apache/lucene/geo/TestTessellator.java
@@ -0,0 +1,50 @@
+/*
+ * 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.geo;
+
+import org.apache.lucene.util.LuceneTestCase;
+
+import static org.apache.lucene.geo.GeoEncodingUtils.encodeLatitude;
+import static org.apache.lucene.geo.GeoEncodingUtils.encodeLongitude;
+import static org.apache.lucene.geo.GeoTestUtil.nextBox;
+
+/** Test case for the Polygon {@link Tessellator} class */
+public class TestTessellator extends LuceneTestCase {
+
+ public void testLinesIntersect() {
+ Rectangle rect = nextBox();
+ // quantize lat/lon of bounding box:
+ int minX = encodeLongitude(rect.minLon);
+ int maxX = encodeLongitude(rect.maxLon);
+ int minY = encodeLatitude(rect.minLat);
+ int maxY = encodeLatitude(rect.maxLat);
+ // simple case; test intersecting diagonals
+ assertTrue(Tessellator.linesIntersect(minX, minY, maxX, maxY, maxX, minY, minX, maxY));
+ // test closest encoded value
+ assertFalse(Tessellator.linesIntersect(minX, maxY, maxX, maxY, minX - 1, minY, minX - 1, maxY));
+ }
+
+ public void testSimpleTessellation() throws Exception {
+ Polygon poly = GeoTestUtil.createRegularPolygon(0.0, 0.0, 1000000, 1000000);
+ Polygon inner = new Polygon(new double[] {-1.0, -1.0, 0.5, 1.0, 1.0, 0.5, -1.0},
+ new double[]{1.0, -1.0, -0.5, -1.0, 1.0, 0.5, 1.0});
+ Polygon inner2 = new Polygon(new double[] {-1.0, -1.0, 0.5, 1.0, 1.0, 0.5, -1.0},
+ new double[]{-2.0, -4.0, -3.5, -4.0, -2.0, -2.5, -2.0});
+ poly = new Polygon(poly.getPolyLats(), poly.getPolyLons(), inner, inner2);
+ assertTrue(Tessellator.tessellate(poly).size() > 0);
+ }
+}
\ No newline at end of file