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 2016/04/02 20:57:49 UTC
[2/2] lucene-solr:master: LUCENE-7163: refactor GeoRect, Polygon,
and GeoUtils tests to geo package in core.
LUCENE-7163: refactor GeoRect, Polygon, and GeoUtils tests to geo package in core.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/6c219e99
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/6c219e99
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/6c219e99
Branch: refs/heads/master
Commit: 6c219e99e4b7018ec75430a1eb880566e63d4d63
Parents: d0156b1
Author: nknize <nk...@apache.org>
Authored: Fri Apr 1 13:12:34 2016 -0500
Committer: nknize <nk...@apache.org>
Committed: Sat Apr 2 13:57:02 2016 -0500
----------------------------------------------------------------------
.../src/java/org/apache/lucene/geo/Polygon.java | 316 ++++++++++++
.../java/org/apache/lucene/geo/Rectangle.java | 189 +++++++
.../org/apache/lucene/geo/TestGeoUtils.java | 338 +++++++++++++
.../org/apache/lucene/document/LatLonPoint.java | 2 +-
.../document/LatLonPointDistanceComparator.java | 5 +-
.../document/LatLonPointDistanceQuery.java | 8 +-
.../document/LatLonPointInPolygonQuery.java | 6 +-
.../document/TestLatLonPointDistanceSort.java | 2 +-
.../lucene/search/TestLatLonPointQueries.java | 2 +-
.../geopoint/search/GeoPointDistanceQuery.java | 12 +-
.../search/GeoPointDistanceQueryImpl.java | 8 +-
.../geopoint/search/GeoPointInPolygonQuery.java | 8 +-
.../search/GeoPointInPolygonQueryImpl.java | 2 +-
.../org/apache/lucene/spatial/util/GeoRect.java | 191 -------
.../org/apache/lucene/spatial/util/Polygon.java | 314 ------------
.../geopoint/search/TestGeoPointQuery.java | 2 +-
.../search/TestLegacyGeoPointQuery.java | 2 +-
.../spatial/util/BaseGeoPointTestCase.java | 17 +-
.../apache/lucene/spatial/util/GeoTestUtil.java | 500 -------------------
.../spatial/util/TestGeoEncodingUtils.java | 101 ++++
.../lucene/spatial/util/TestGeoUtils.java | 399 ---------------
.../apache/lucene/spatial/util/TestPolygon.java | 19 +-
.../java/org/apache/lucene/geo/GeoTestUtil.java | 499 ++++++++++++++++++
.../org/apache/lucene/geo/package-info.java | 21 +
24 files changed, 1516 insertions(+), 1447 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6c219e99/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
new file mode 100644
index 0000000..3f32920
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/geo/Polygon.java
@@ -0,0 +1,316 @@
+/*
+ * 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.Arrays;
+
+/**
+ * Represents a closed polygon on the earth's surface.
+ * @lucene.experimental
+ */
+public final class Polygon {
+ private final double[] polyLats;
+ private final double[] polyLons;
+ private final Polygon[] holes;
+
+ /** minimum latitude of this polygon's bounding box area */
+ public final double minLat;
+ /** maximum latitude of this polygon's bounding box area */
+ public final double maxLat;
+ /** minimum longitude of this polygon's bounding box area */
+ public final double minLon;
+ /** maximum longitude of this polygon's bounding box area */
+ public final double maxLon;
+
+ // TODO: refactor to GeoUtils once LUCENE-7165 is complete
+ private static final double ENCODING_TOLERANCE = 1e-6;
+
+ // TODO: we could also compute the maximal inner bounding box, to make relations faster to compute?
+
+ /**
+ * Creates a new Polygon from the supplied latitude/longitude array, and optionally any holes.
+ */
+ public Polygon(double[] polyLats, double[] polyLons, Polygon... holes) {
+ if (polyLats == null) {
+ throw new IllegalArgumentException("polyLats must not be null");
+ }
+ if (polyLons == null) {
+ throw new IllegalArgumentException("polyLons must not be null");
+ }
+ if (holes == null) {
+ throw new IllegalArgumentException("holes must not be null");
+ }
+ if (polyLats.length != polyLons.length) {
+ throw new IllegalArgumentException("polyLats and polyLons must be equal length");
+ }
+ if (polyLats.length != polyLons.length) {
+ throw new IllegalArgumentException("polyLats and polyLons must be equal length");
+ }
+ if (polyLats.length < 4) {
+ throw new IllegalArgumentException("at least 4 polygon points required");
+ }
+ if (polyLats[0] != polyLats[polyLats.length-1]) {
+ throw new IllegalArgumentException("first and last points of the polygon must be the same (it must close itself): polyLats[0]=" + polyLats[0] + " polyLats[" + (polyLats.length-1) + "]=" + polyLats[polyLats.length-1]);
+ }
+ if (polyLons[0] != polyLons[polyLons.length-1]) {
+ throw new IllegalArgumentException("first and last points of the polygon must be the same (it must close itself): polyLons[0]=" + polyLons[0] + " polyLons[" + (polyLons.length-1) + "]=" + polyLons[polyLons.length-1]);
+ }
+ for (int i = 0; i < polyLats.length; i++) {
+ GeoUtils.checkLatitude(polyLats[i]);
+ GeoUtils.checkLongitude(polyLons[i]);
+ }
+ for (int i = 0; i < holes.length; i++) {
+ Polygon inner = holes[i];
+ if (inner.holes.length > 0) {
+ throw new IllegalArgumentException("holes may not contain holes: polygons may not nest.");
+ }
+ }
+ this.polyLats = polyLats.clone();
+ this.polyLons = polyLons.clone();
+ 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;
+
+ for (int i = 0;i < polyLats.length; 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);
+ }
+ this.minLat = minLat;
+ this.maxLat = maxLat;
+ this.minLon = minLon;
+ this.maxLon = maxLon;
+ }
+
+ /** Returns true if the point is contained within this polygon */
+ public boolean contains(double latitude, double longitude) {
+ // check bounding box
+ if (latitude < minLat || latitude > maxLat || longitude < minLon || longitude > maxLon) {
+ return false;
+ }
+ /*
+ * simple even-odd point in polygon computation
+ * 1. Determine if point is contained in the longitudinal range
+ * 2. Determine whether point crosses the edge by computing the latitudinal delta
+ * between the end-point of a parallel vector (originating at the point) and the
+ * y-component of the edge sink
+ *
+ * NOTE: Requires polygon point (x,y) order either clockwise or counter-clockwise
+ */
+ boolean inPoly = false;
+ /*
+ * Note: This is using a euclidean coordinate system which could result in
+ * upwards of 110KM error at the equator.
+ * TODO convert coordinates to cylindrical projection (e.g. mercator)
+ */
+ for (int i = 1; i < polyLats.length; i++) {
+ if (polyLons[i] <= longitude && polyLons[i-1] >= longitude || polyLons[i-1] <= longitude && polyLons[i] >= longitude) {
+ if (polyLats[i] + (longitude - polyLons[i]) / (polyLons[i-1] - polyLons[i]) * (polyLats[i-1] - polyLats[i]) <= latitude) {
+ inPoly = !inPoly;
+ }
+ }
+ }
+ if (inPoly) {
+ for (Polygon hole : holes) {
+ if (hole.contains(latitude, longitude)) {
+ return false;
+ }
+ }
+ return true;
+ } else {
+ return false;
+ }
+ }
+
+ /**
+ * Computes whether a rectangle is within a polygon (shared boundaries not allowed)
+ */
+ public boolean contains(double minLat, double maxLat, double minLon, double maxLon) {
+ // check if rectangle crosses poly (to handle concave/pacman polys), then check that all 4 corners
+ // are contained
+ boolean contains = crosses(minLat, maxLat, minLon, maxLon) == false &&
+ contains(minLat, minLon) &&
+ contains(minLat, maxLon) &&
+ contains(maxLat, maxLon) &&
+ contains(maxLat, minLon);
+
+ if (contains) {
+ // if we intersect with any hole, game over
+ for (Polygon hole : holes) {
+ if (hole.crosses(minLat, maxLat, minLon, maxLon) || hole.contains(minLat, maxLat, minLon, maxLon)) {
+ return false;
+ }
+ }
+ return true;
+ } else {
+ return false;
+ }
+ }
+
+ /**
+ * Convenience method for accurately computing whether a rectangle crosses a poly.
+ */
+ public boolean crosses(double minLat, double maxLat, final double minLon, final double maxLon) {
+ // if the bounding boxes are disjoint then the shape does not cross
+ if (maxLon < this.minLon || minLon > this.maxLon || maxLat < this.minLat || minLat > this.maxLat) {
+ return false;
+ }
+ // if the rectangle fully encloses us, we cross.
+ if (minLat <= this.minLat && maxLat >= this.maxLat && minLon <= this.minLon && maxLon >= this.maxLon) {
+ return true;
+ }
+ // if we cross any hole, we cross
+ for (Polygon hole : holes) {
+ if (hole.crosses(minLat, maxLat, minLon, maxLon)) {
+ return true;
+ }
+ }
+
+ /*
+ * Accurately compute (within restrictions of cartesian decimal degrees) whether a rectangle crosses a polygon
+ */
+ final double[][] bbox = new double[][] { {minLon, minLat}, {maxLon, minLat}, {maxLon, maxLat}, {minLon, maxLat}, {minLon, minLat} };
+ final int polyLength = polyLons.length-1;
+ double d, s, t, a1, b1, c1, a2, b2, c2;
+ double x00, y00, x01, y01, x10, y10, x11, y11;
+
+ // computes the intersection point between each bbox edge and the polygon edge
+ for (short b=0; b<4; ++b) {
+ a1 = bbox[b+1][1]-bbox[b][1];
+ b1 = bbox[b][0]-bbox[b+1][0];
+ c1 = a1*bbox[b+1][0] + b1*bbox[b+1][1];
+ for (int p=0; p<polyLength; ++p) {
+ a2 = polyLats[p+1]-polyLats[p];
+ b2 = polyLons[p]-polyLons[p+1];
+ // compute determinant
+ d = a1*b2 - a2*b1;
+ if (d != 0) {
+ // lines are not parallel, check intersecting points
+ c2 = a2*polyLons[p+1] + b2*polyLats[p+1];
+ s = (1/d)*(b2*c1 - b1*c2);
+ t = (1/d)*(a1*c2 - a2*c1);
+ // todo TOLERANCE SHOULD MATCH EVERYWHERE this is currently blocked by LUCENE-7165
+ x00 = Math.min(bbox[b][0], bbox[b+1][0]) - ENCODING_TOLERANCE;
+ x01 = Math.max(bbox[b][0], bbox[b+1][0]) + ENCODING_TOLERANCE;
+ y00 = Math.min(bbox[b][1], bbox[b+1][1]) - ENCODING_TOLERANCE;
+ y01 = Math.max(bbox[b][1], bbox[b+1][1]) + ENCODING_TOLERANCE;
+ x10 = Math.min(polyLons[p], polyLons[p+1]) - ENCODING_TOLERANCE;
+ x11 = Math.max(polyLons[p], polyLons[p+1]) + ENCODING_TOLERANCE;
+ y10 = Math.min(polyLats[p], polyLats[p+1]) - ENCODING_TOLERANCE;
+ y11 = Math.max(polyLats[p], polyLats[p+1]) + ENCODING_TOLERANCE;
+ // check whether the intersection point is touching one of the line segments
+ boolean touching = ((x00 == s && y00 == t) || (x01 == s && y01 == t))
+ || ((x10 == s && y10 == t) || (x11 == s && y11 == t));
+ // if line segments are not touching and the intersection point is within the range of either segment
+ if (!(touching || x00 > s || x01 < s || y00 > t || y01 < t || x10 > s || x11 < s || y10 > t || y11 < t)) {
+ return true;
+ }
+ }
+ } // for each poly edge
+ } // for each bbox edge
+ return false;
+ }
+
+ /** Returns a copy of the internal latitude array */
+ public double[] getPolyLats() {
+ return polyLats.clone();
+ }
+
+ /** Returns a copy of the internal longitude array */
+ public double[] getPolyLons() {
+ return polyLons.clone();
+ }
+
+ /** Returns a copy of the internal holes array */
+ public Polygon[] getHoles() {
+ return holes.clone();
+ }
+
+ /** Helper for multipolygon logic: returns true if any of the supplied polygons contain the point */
+ public static boolean contains(Polygon[] polygons, double latitude, double longitude) {
+ for (Polygon polygon : polygons) {
+ if (polygon.contains(latitude, longitude)) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /** Helper for multipolygon logic: returns true if any of the supplied polygons contain the rectangle */
+ public static boolean contains(Polygon[] polygons, double minLat, double maxLat, double minLon, double maxLon) {
+ for (Polygon polygon : polygons) {
+ if (polygon.contains(minLat, maxLat, minLon, maxLon)) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /** Helper for multipolygon logic: returns true if any of the supplied polygons crosses the rectangle */
+ public static boolean crosses(Polygon[] polygons, double minLat, double maxLat, double minLon, double maxLon) {
+ for (Polygon polygon : polygons) {
+ if (polygon.crosses(minLat, maxLat, minLon, maxLon)) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ @Override
+ public int hashCode() {
+ final int prime = 31;
+ int result = 1;
+ result = prime * result + Arrays.hashCode(holes);
+ result = prime * result + Arrays.hashCode(polyLats);
+ result = prime * result + Arrays.hashCode(polyLons);
+ return result;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) return true;
+ if (obj == null) return false;
+ if (getClass() != obj.getClass()) return false;
+ Polygon other = (Polygon) obj;
+ if (!Arrays.equals(holes, other.holes)) return false;
+ if (!Arrays.equals(polyLats, other.polyLats)) return false;
+ if (!Arrays.equals(polyLons, other.polyLons)) return false;
+ return true;
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder sb = new StringBuilder();
+ for (int i = 0; i < polyLats.length; i++) {
+ sb.append("[")
+ .append(polyLats[i])
+ .append(", ")
+ .append(polyLons[i])
+ .append("] ");
+ }
+ if (holes.length > 0) {
+ sb.append(", holes=");
+ sb.append(Arrays.toString(holes));
+ }
+ return sb.toString();
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6c219e99/lucene/core/src/java/org/apache/lucene/geo/Rectangle.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/geo/Rectangle.java b/lucene/core/src/java/org/apache/lucene/geo/Rectangle.java
new file mode 100644
index 0000000..527395e
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/geo/Rectangle.java
@@ -0,0 +1,189 @@
+/*
+ * 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 static java.lang.Math.PI;
+import static java.lang.Math.max;
+import static java.lang.Math.min;
+import static java.lang.Math.toDegrees;
+import static java.lang.Math.toRadians;
+import static org.apache.lucene.geo.GeoUtils.checkLatitude;
+import static org.apache.lucene.geo.GeoUtils.checkLongitude;
+import static org.apache.lucene.geo.GeoUtils.MAX_LAT_INCL;
+import static org.apache.lucene.geo.GeoUtils.MIN_LAT_INCL;
+import static org.apache.lucene.geo.GeoUtils.MAX_LAT_RADIANS;
+import static org.apache.lucene.geo.GeoUtils.MAX_LON_RADIANS;
+import static org.apache.lucene.geo.GeoUtils.MIN_LAT_RADIANS;
+import static org.apache.lucene.geo.GeoUtils.MIN_LON_RADIANS;
+import static org.apache.lucene.geo.GeoUtils.EARTH_MEAN_RADIUS_METERS;
+import static org.apache.lucene.geo.GeoUtils.sloppySin;
+import static org.apache.lucene.util.SloppyMath.TO_DEGREES;
+import static org.apache.lucene.util.SloppyMath.asin;
+import static org.apache.lucene.util.SloppyMath.cos;
+
+/** Represents a lat/lon rectangle. */
+public class Rectangle {
+ /** maximum longitude value (in degrees) */
+ public final double minLat;
+ /** minimum longitude value (in degrees) */
+ public final double minLon;
+ /** maximum latitude value (in degrees) */
+ public final double maxLat;
+ /** minimum latitude value (in degrees) */
+ public final double maxLon;
+
+ /**
+ * Constructs a bounding box by first validating the provided latitude and longitude coordinates
+ */
+ public Rectangle(double minLat, double maxLat, double minLon, double maxLon) {
+ GeoUtils.checkLatitude(minLat);
+ GeoUtils.checkLatitude(maxLat);
+ GeoUtils.checkLongitude(minLon);
+ GeoUtils.checkLongitude(maxLon);
+ this.minLon = minLon;
+ this.maxLon = maxLon;
+ this.minLat = minLat;
+ this.maxLat = maxLat;
+ assert maxLat >= minLat;
+
+ // NOTE: cannot assert maxLon >= minLon since this rect could cross the dateline
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder b = new StringBuilder();
+ b.append("GeoRect(lat=");
+ b.append(minLat);
+ b.append(" TO ");
+ b.append(maxLat);
+ b.append(" lon=");
+ b.append(minLon);
+ b.append(" TO ");
+ b.append(maxLon);
+ if (maxLon < minLon) {
+ b.append(" [crosses dateline!]");
+ }
+ b.append(")");
+
+ return b.toString();
+ }
+
+ /** Returns true if this bounding box crosses the dateline */
+ public boolean crossesDateline() {
+ return maxLon < minLon;
+ }
+
+ /** Compute Bounding Box for a circle using WGS-84 parameters */
+ public static Rectangle fromPointDistance(final double centerLat, final double centerLon, final double radiusMeters) {
+ checkLatitude(centerLat);
+ checkLongitude(centerLon);
+ final double radLat = toRadians(centerLat);
+ final double radLon = toRadians(centerLon);
+ // LUCENE-7143
+ double radDistance = (radiusMeters + 7E-2) / EARTH_MEAN_RADIUS_METERS;
+ double minLat = radLat - radDistance;
+ double maxLat = radLat + radDistance;
+ double minLon;
+ double maxLon;
+
+ if (minLat > MIN_LAT_RADIANS && maxLat < MAX_LAT_RADIANS) {
+ double deltaLon = asin(sloppySin(radDistance) / cos(radLat));
+ minLon = radLon - deltaLon;
+ if (minLon < MIN_LON_RADIANS) {
+ minLon += 2d * PI;
+ }
+ maxLon = radLon + deltaLon;
+ if (maxLon > MAX_LON_RADIANS) {
+ maxLon -= 2d * PI;
+ }
+ } else {
+ // a pole is within the distance
+ minLat = max(minLat, MIN_LAT_RADIANS);
+ maxLat = min(maxLat, MAX_LAT_RADIANS);
+ minLon = MIN_LON_RADIANS;
+ maxLon = MAX_LON_RADIANS;
+ }
+
+ return new Rectangle(toDegrees(minLat), toDegrees(maxLat), toDegrees(minLon), toDegrees(maxLon));
+ }
+
+ /** maximum error from {@link #axisLat(double, double)}. logic must be prepared to handle this */
+ public static final double AXISLAT_ERROR = 0.1D / EARTH_MEAN_RADIUS_METERS * TO_DEGREES;
+
+ /**
+ * Calculate the latitude of a circle's intersections with its bbox meridians.
+ * <p>
+ * <b>NOTE:</b> the returned value will be +/- {@link #AXISLAT_ERROR} of the actual value.
+ * @param centerLat The latitude of the circle center
+ * @param radiusMeters The radius of the circle in meters
+ * @return A latitude
+ */
+ public static double axisLat(double centerLat, double radiusMeters) {
+ // A spherical triangle with:
+ // r is the radius of the circle in radians
+ // l1 is the latitude of the circle center
+ // l2 is the latitude of the point at which the circle intersect's its bbox longitudes
+ // We know r is tangent to the bbox meridians at l2, therefore it is a right angle.
+ // So from the law of cosines, with the angle of l1 being 90, we have:
+ // cos(l1) = cos(r) * cos(l2) + sin(r) * sin(l2) * cos(90)
+ // The second part cancels out because cos(90) == 0, so we have:
+ // cos(l1) = cos(r) * cos(l2)
+ // Solving for l2, we get:
+ // l2 = acos( cos(l1) / cos(r) )
+ // We ensure r is in the range (0, PI/2) and l1 in the range (0, PI/2]. This means we
+ // cannot divide by 0, and we will always get a positive value in the range [0, 1) as
+ // the argument to arc cosine, resulting in a range (0, PI/2].
+ final double PIO2 = Math.PI / 2D;
+ double l1 = toRadians(centerLat);
+ double r = (radiusMeters + 7E-2) / EARTH_MEAN_RADIUS_METERS;
+
+ // if we are within radius range of a pole, the lat is the pole itself
+ if (Math.abs(l1) + r >= MAX_LAT_RADIANS) {
+ return centerLat >= 0 ? MAX_LAT_INCL : MIN_LAT_INCL;
+ }
+
+ // adjust l1 as distance from closest pole, to form a right triangle with bbox meridians
+ // and ensure it is in the range (0, PI/2]
+ l1 = centerLat >= 0 ? PIO2 - l1 : l1 + PIO2;
+
+ double l2 = Math.acos(Math.cos(l1) / Math.cos(r));
+ assert !Double.isNaN(l2);
+
+ // now adjust back to range [-pi/2, pi/2], ie latitude in radians
+ l2 = centerLat >= 0 ? PIO2 - l2 : l2 - PIO2;
+
+ return toDegrees(l2);
+ }
+
+ /** Returns the bounding box over an array of polygons */
+ public static Rectangle fromPolygon(Polygon[] polygons) {
+ // compute bounding box
+ double minLat = Double.POSITIVE_INFINITY;
+ double maxLat = Double.NEGATIVE_INFINITY;
+ double minLon = Double.POSITIVE_INFINITY;
+ double maxLon = Double.NEGATIVE_INFINITY;
+
+ for (int i = 0;i < polygons.length; i++) {
+ minLat = Math.min(polygons[i].minLat, minLat);
+ maxLat = Math.max(polygons[i].maxLat, maxLat);
+ minLon = Math.min(polygons[i].minLon, minLon);
+ maxLon = Math.max(polygons[i].maxLon, maxLon);
+ }
+
+ return new Rectangle(minLat, maxLat, minLon, maxLon);
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6c219e99/lucene/core/src/test/org/apache/lucene/geo/TestGeoUtils.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/test/org/apache/lucene/geo/TestGeoUtils.java b/lucene/core/src/test/org/apache/lucene/geo/TestGeoUtils.java
new file mode 100644
index 0000000..8727b42
--- /dev/null
+++ b/lucene/core/src/test/org/apache/lucene/geo/TestGeoUtils.java
@@ -0,0 +1,338 @@
+/*
+ * 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.Locale;
+
+import org.apache.lucene.util.LuceneTestCase;
+import org.apache.lucene.util.SloppyMath;
+import org.junit.BeforeClass;
+
+/**
+ * Tests class for methods in GeoUtils
+ *
+ * @lucene.experimental
+ */
+public class TestGeoUtils extends LuceneTestCase {
+
+ // Global bounding box we will "cover" in the random test; we have to make this "smallish" else the queries take very long:
+ private static double originLat;
+ private static double originLon;
+
+ @BeforeClass
+ public static void beforeClass() throws Exception {
+ originLon = GeoTestUtil.nextLongitude();
+ originLat = GeoTestUtil.nextLatitude();
+ }
+
+ public double randomLat(boolean small) {
+ double result;
+ if (small) {
+ result = GeoTestUtil.nextLatitudeNear(originLat);
+ } else {
+ result = GeoTestUtil.nextLatitude();
+ }
+ return result;
+ }
+
+ public double randomLon(boolean small) {
+ double result;
+ if (small) {
+ result = GeoTestUtil.nextLongitudeNear(originLon);
+ } else {
+ result = GeoTestUtil.nextLongitude();
+ }
+ return result;
+ }
+
+ // We rely heavily on GeoUtils.circleToBBox so we test it here:
+ public void testRandomCircleToBBox() throws Exception {
+ int iters = atLeast(1000);
+ for(int iter=0;iter<iters;iter++) {
+
+ boolean useSmallRanges = random().nextBoolean();
+
+ double radiusMeters;
+
+ double centerLat = randomLat(useSmallRanges);
+ double centerLon = randomLon(useSmallRanges);
+
+ if (useSmallRanges) {
+ // Approx 4 degrees lon at the equator:
+ radiusMeters = random().nextDouble() * 444000;
+ } else {
+ radiusMeters = random().nextDouble() * 50000000;
+ }
+
+ // TODO: randomly quantize radius too, to provoke exact math errors?
+
+ Rectangle bbox = Rectangle.fromPointDistance(centerLat, centerLon, radiusMeters);
+
+ int numPointsToTry = 1000;
+ for(int i=0;i<numPointsToTry;i++) {
+
+ double lat;
+ double lon;
+
+ if (random().nextBoolean()) {
+ lat = randomLat(useSmallRanges);
+ lon = randomLon(useSmallRanges);
+ } else {
+ // pick a lat/lon within the bbox or "slightly" outside it to try to improve test efficiency
+ lat = GeoTestUtil.nextLatitudeAround(bbox.minLat, bbox.maxLat);
+ if (bbox.crossesDateline()) {
+ if (random().nextBoolean()) {
+ lon = GeoTestUtil.nextLongitudeAround(bbox.maxLon, -180);
+ } else {
+ lon = GeoTestUtil.nextLongitudeAround(0, bbox.minLon);
+ }
+ } else {
+ lon = GeoTestUtil.nextLongitudeAround(bbox.minLon, bbox.maxLon);
+ }
+ }
+
+ double distanceMeters = SloppyMath.haversinMeters(centerLat, centerLon, lat, lon);
+
+ // Haversin says it's within the circle:
+ boolean haversinSays = distanceMeters <= radiusMeters;
+
+ // BBox says its within the box:
+ boolean bboxSays;
+ if (bbox.crossesDateline()) {
+ if (lat >= bbox.minLat && lat <= bbox.maxLat) {
+ bboxSays = lon <= bbox.maxLon || lon >= bbox.minLon;
+ } else {
+ bboxSays = false;
+ }
+ } else {
+ bboxSays = lat >= bbox.minLat && lat <= bbox.maxLat && lon >= bbox.minLon && lon <= bbox.maxLon;
+ }
+
+ if (haversinSays) {
+ if (bboxSays == false) {
+ System.out.println("small=" + useSmallRanges + " centerLat=" + centerLat + " cetnerLon=" + centerLon + " radiusMeters=" + radiusMeters);
+ System.out.println(" bbox: lat=" + bbox.minLat + " to " + bbox.maxLat + " lon=" + bbox.minLon + " to " + bbox.maxLon);
+ System.out.println(" point: lat=" + lat + " lon=" + lon);
+ System.out.println(" haversin: " + distanceMeters);
+ fail("point was within the distance according to haversin, but the bbox doesn't contain it");
+ }
+ } else {
+ // it's fine if haversin said it was outside the radius and bbox said it was inside the box
+ }
+ }
+ }
+ }
+
+ // similar to testRandomCircleToBBox, but different, less evil, maybe simpler
+ public void testBoundingBoxOpto() {
+ for (int i = 0; i < 1000; i++) {
+ double lat = GeoTestUtil.nextLatitude();
+ double lon = GeoTestUtil.nextLongitude();
+ double radius = 50000000 * random().nextDouble();
+ Rectangle box = Rectangle.fromPointDistance(lat, lon, radius);
+ final Rectangle box1;
+ final Rectangle box2;
+ if (box.crossesDateline()) {
+ box1 = new Rectangle(box.minLat, box.maxLat, -180, box.maxLon);
+ box2 = new Rectangle(box.minLat, box.maxLat, box.minLon, 180);
+ } else {
+ box1 = box;
+ box2 = null;
+ }
+
+ for (int j = 0; j < 10000; j++) {
+ double lat2 = GeoTestUtil.nextLatitude();
+ double lon2 = GeoTestUtil.nextLongitude();
+ // if the point is within radius, then it should be in our bounding box
+ if (SloppyMath.haversinMeters(lat, lon, lat2, lon2) <= radius) {
+ assertTrue(lat >= box.minLat && lat <= box.maxLat);
+ assertTrue(lon >= box1.minLon && lon <= box1.maxLon || (box2 != null && lon >= box2.minLon && lon <= box2.maxLon));
+ }
+ }
+ }
+ }
+
+ // test we can use haversinSortKey() for distance queries.
+ public void testHaversinOpto() {
+ for (int i = 0; i < 1000; i++) {
+ double lat = GeoTestUtil.nextLatitude();
+ double lon = GeoTestUtil.nextLongitude();
+ double radius = 50000000 * random().nextDouble();
+ Rectangle box = Rectangle.fromPointDistance(lat, lon, radius);
+
+ if (box.maxLon - lon < 90 && lon - box.minLon < 90) {
+ double minPartialDistance = Math.max(SloppyMath.haversinSortKey(lat, lon, lat, box.maxLon),
+ SloppyMath.haversinSortKey(lat, lon, box.maxLat, lon));
+
+ for (int j = 0; j < 10000; j++) {
+ double lat2 = GeoTestUtil.nextLatitude();
+ double lon2 = GeoTestUtil.nextLongitude();
+ // if the point is within radius, then it should be <= our sort key
+ if (SloppyMath.haversinMeters(lat, lon, lat2, lon2) <= radius) {
+ assertTrue(SloppyMath.haversinSortKey(lat, lon, lat2, lon2) <= minPartialDistance);
+ }
+ }
+ }
+ }
+ }
+
+ /** Test infinite radius covers whole earth */
+ public void testInfiniteRect() {
+ for (int i = 0; i < 1000; i++) {
+ double centerLat = GeoTestUtil.nextLatitude();
+ double centerLon = GeoTestUtil.nextLongitude();
+ Rectangle rect = Rectangle.fromPointDistance(centerLat, centerLon, Double.POSITIVE_INFINITY);
+ assertEquals(-180.0, rect.minLon, 0.0D);
+ assertEquals(180.0, rect.maxLon, 0.0D);
+ assertEquals(-90.0, rect.minLat, 0.0D);
+ assertEquals(90.0, rect.maxLat, 0.0D);
+ assertFalse(rect.crossesDateline());
+ }
+ }
+
+ public void testAxisLat() {
+ double earthCircumference = 2D * Math.PI * GeoUtils.EARTH_MEAN_RADIUS_METERS;
+ assertEquals(90, Rectangle.axisLat(0, earthCircumference / 4), 0.0D);
+
+ for (int i = 0; i < 100; ++i) {
+ boolean reallyBig = random().nextInt(10) == 0;
+ final double maxRadius = reallyBig ? 1.1 * earthCircumference : earthCircumference / 8;
+ final double radius = maxRadius * random().nextDouble();
+ double prevAxisLat = Rectangle.axisLat(0.0D, radius);
+ for (double lat = 0.1D; lat < 90D; lat += 0.1D) {
+ double nextAxisLat = Rectangle.axisLat(lat, radius);
+ Rectangle bbox = Rectangle.fromPointDistance(lat, 180D, radius);
+ double dist = SloppyMath.haversinMeters(lat, 180D, nextAxisLat, bbox.maxLon);
+ if (nextAxisLat < GeoUtils.MAX_LAT_INCL) {
+ assertEquals("lat = " + lat, dist, radius, 0.1D);
+ }
+ assertTrue("lat = " + lat, prevAxisLat <= nextAxisLat);
+ prevAxisLat = nextAxisLat;
+ }
+
+ prevAxisLat = Rectangle.axisLat(-0.0D, radius);
+ for (double lat = -0.1D; lat > -90D; lat -= 0.1D) {
+ double nextAxisLat = Rectangle.axisLat(lat, radius);
+ Rectangle bbox = Rectangle.fromPointDistance(lat, 180D, radius);
+ double dist = SloppyMath.haversinMeters(lat, 180D, nextAxisLat, bbox.maxLon);
+ if (nextAxisLat > GeoUtils.MIN_LAT_INCL) {
+ assertEquals("lat = " + lat, dist, radius, 0.1D);
+ }
+ assertTrue("lat = " + lat, prevAxisLat >= nextAxisLat);
+ prevAxisLat = nextAxisLat;
+ }
+ }
+ }
+
+ // TODO: does not really belong here, but we test it like this for now
+ // we can make a fake IndexReader to send boxes directly to Point visitors instead?
+ public void testCircleOpto() throws Exception {
+ for (int i = 0; i < 50; i++) {
+ // circle
+ final double centerLat = -90 + 180.0 * random().nextDouble();
+ final double centerLon = -180 + 360.0 * random().nextDouble();
+ final double radius = 50_000_000D * random().nextDouble();
+ final Rectangle box = Rectangle.fromPointDistance(centerLat, centerLon, radius);
+ // TODO: remove this leniency!
+ if (box.crossesDateline()) {
+ --i; // try again...
+ continue;
+ }
+ final double axisLat = Rectangle.axisLat(centerLat, radius);
+
+ for (int k = 0; k < 1000; ++k) {
+
+ double[] latBounds = {-90, box.minLat, axisLat, box.maxLat, 90};
+ double[] lonBounds = {-180, box.minLon, centerLon, box.maxLon, 180};
+ // first choose an upper left corner
+ int maxLatRow = random().nextInt(4);
+ double latMax = randomInRange(latBounds[maxLatRow], latBounds[maxLatRow + 1]);
+ int minLonCol = random().nextInt(4);
+ double lonMin = randomInRange(lonBounds[minLonCol], lonBounds[minLonCol + 1]);
+ // now choose a lower right corner
+ int minLatMaxRow = maxLatRow == 3 ? 3 : maxLatRow + 1; // make sure it will at least cross into the bbox
+ int minLatRow = random().nextInt(minLatMaxRow);
+ double latMin = randomInRange(latBounds[minLatRow], Math.min(latBounds[minLatRow + 1], latMax));
+ int maxLonMinCol = Math.max(minLonCol, 1); // make sure it will at least cross into the bbox
+ int maxLonCol = maxLonMinCol + random().nextInt(4 - maxLonMinCol);
+ double lonMax = randomInRange(Math.max(lonBounds[maxLonCol], lonMin), lonBounds[maxLonCol + 1]);
+
+ assert latMax >= latMin;
+ assert lonMax >= lonMin;
+
+ if (isDisjoint(centerLat, centerLon, radius, axisLat, latMin, latMax, lonMin, lonMax)) {
+ // intersects says false: test a ton of points
+ for (int j = 0; j < 200; j++) {
+ double lat = latMin + (latMax - latMin) * random().nextDouble();
+ double lon = lonMin + (lonMax - lonMin) * random().nextDouble();
+
+ if (random().nextBoolean()) {
+ // explicitly test an edge
+ int edge = random().nextInt(4);
+ if (edge == 0) {
+ lat = latMin;
+ } else if (edge == 1) {
+ lat = latMax;
+ } else if (edge == 2) {
+ lon = lonMin;
+ } else if (edge == 3) {
+ lon = lonMax;
+ }
+ }
+ double distance = SloppyMath.haversinMeters(centerLat, centerLon, lat, lon);
+ try {
+ assertTrue(String.format(Locale.ROOT, "\nisDisjoint(\n" +
+ "centerLat=%s\n" +
+ "centerLon=%s\n" +
+ "radius=%s\n" +
+ "latMin=%s\n" +
+ "latMax=%s\n" +
+ "lonMin=%s\n" +
+ "lonMax=%s) == false BUT\n" +
+ "haversin(%s, %s, %s, %s) = %s\nbbox=%s",
+ centerLat, centerLon, radius, latMin, latMax, lonMin, lonMax,
+ centerLat, centerLon, lat, lon, distance, Rectangle.fromPointDistance(centerLat, centerLon, radius)),
+ distance > radius);
+ } catch (AssertionError e) {
+ GeoTestUtil.toWebGLEarth(latMin, latMax, lonMin, lonMax, centerLat, centerLon, radius);
+ throw e;
+ }
+ }
+ }
+ }
+ }
+ }
+
+ static double randomInRange(double min, double max) {
+ return min + (max - min) * random().nextDouble();
+ }
+
+ static boolean isDisjoint(double centerLat, double centerLon, double radius, double axisLat, double latMin, double latMax, double lonMin, double lonMax) {
+ if ((centerLon < lonMin || centerLon > lonMax) && (axisLat+ Rectangle.AXISLAT_ERROR < latMin || axisLat- Rectangle.AXISLAT_ERROR > latMax)) {
+ // circle not fully inside / crossing axis
+ if (SloppyMath.haversinMeters(centerLat, centerLon, latMin, lonMin) > radius &&
+ SloppyMath.haversinMeters(centerLat, centerLon, latMin, lonMax) > radius &&
+ SloppyMath.haversinMeters(centerLat, centerLon, latMax, lonMin) > radius &&
+ SloppyMath.haversinMeters(centerLat, centerLon, latMax, lonMax) > radius) {
+ // no points inside
+ return true;
+ }
+ }
+
+ return false;
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6c219e99/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPoint.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPoint.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPoint.java
index 507f543..26bb04a 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPoint.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPoint.java
@@ -29,7 +29,7 @@ import org.apache.lucene.search.FieldDoc;
import org.apache.lucene.search.PointRangeQuery;
import org.apache.lucene.search.Query;
import org.apache.lucene.search.SortField;
-import org.apache.lucene.spatial.util.Polygon;
+import org.apache.lucene.geo.Polygon;
/**
* An indexed location field.
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6c219e99/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceComparator.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceComparator.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceComparator.java
index 0ed85ad..58db5e5 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceComparator.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceComparator.java
@@ -26,8 +26,7 @@ import org.apache.lucene.index.SortedNumericDocValues;
import org.apache.lucene.search.FieldComparator;
import org.apache.lucene.search.LeafFieldComparator;
import org.apache.lucene.search.Scorer;
-import org.apache.lucene.spatial.util.GeoRect;
-import org.apache.lucene.geo.GeoUtils;
+import org.apache.lucene.geo.Rectangle;
import org.apache.lucene.util.SloppyMath;
/**
@@ -83,7 +82,7 @@ class LatLonPointDistanceComparator extends FieldComparator<Double> implements L
// sampling if we get called way too much: don't make gobs of bounding
// boxes if comparator hits a worst case order (e.g. backwards distance order)
if (setBottomCounter < 1024 || (setBottomCounter & 0x3F) == 0x3F) {
- GeoRect box = GeoRect.fromPointDistance(latitude, longitude, haversin2(bottom));
+ Rectangle box = Rectangle.fromPointDistance(latitude, longitude, haversin2(bottom));
// pre-encode our box to our integer encoding, so we don't have to decode
// to double values for uncompetitive hits. This has some cost!
minLat = LatLonPoint.encodeLatitude(box.minLat);
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6c219e99/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java
index 2934718..1b667dd 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java
@@ -18,6 +18,7 @@ package org.apache.lucene.document;
import java.io.IOException;
+import org.apache.lucene.geo.Rectangle;
import org.apache.lucene.index.DocValues;
import org.apache.lucene.index.FieldInfo;
import org.apache.lucene.index.LeafReader;
@@ -35,7 +36,6 @@ import org.apache.lucene.search.Query;
import org.apache.lucene.search.Scorer;
import org.apache.lucene.search.TwoPhaseIterator;
import org.apache.lucene.search.Weight;
-import org.apache.lucene.spatial.util.GeoRect;
import org.apache.lucene.geo.GeoUtils;
import org.apache.lucene.util.BitSet;
import org.apache.lucene.util.DocIdSetBuilder;
@@ -71,7 +71,7 @@ final class LatLonPointDistanceQuery extends Query {
@Override
public Weight createWeight(IndexSearcher searcher, boolean needsScores) throws IOException {
- GeoRect box = GeoRect.fromPointDistance(latitude, longitude, radiusMeters);
+ Rectangle box = Rectangle.fromPointDistance(latitude, longitude, radiusMeters);
// create bounding box(es) for the distance range
// these are pre-encoded with LatLonPoint's encoding
final byte minLat[] = new byte[Integer.BYTES];
@@ -108,7 +108,7 @@ final class LatLonPointDistanceQuery extends Query {
maxPartialDistance = Double.POSITIVE_INFINITY;
}
- final double axisLat = GeoRect.axisLat(latitude, radiusMeters);
+ final double axisLat = Rectangle.axisLat(latitude, radiusMeters);
return new ConstantScoreWeight(this) {
@@ -196,7 +196,7 @@ final class LatLonPointDistanceQuery extends Query {
double latMax = LatLonPoint.decodeLatitude(maxPackedValue, 0);
double lonMax = LatLonPoint.decodeLongitude(maxPackedValue, Integer.BYTES);
- if ((longitude < lonMin || longitude > lonMax) && (axisLat+GeoRect.AXISLAT_ERROR < latMin || axisLat-GeoRect.AXISLAT_ERROR > latMax)) {
+ if ((longitude < lonMin || longitude > lonMax) && (axisLat+ Rectangle.AXISLAT_ERROR < latMin || axisLat- Rectangle.AXISLAT_ERROR > latMax)) {
// circle not fully inside / crossing axis
if (SloppyMath.haversinMeters(latitude, longitude, latMin, lonMin) > radiusMeters &&
SloppyMath.haversinMeters(latitude, longitude, latMin, lonMax) > radiusMeters &&
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6c219e99/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointInPolygonQuery.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointInPolygonQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointInPolygonQuery.java
index 56e906b..54f5192 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointInPolygonQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointInPolygonQuery.java
@@ -19,6 +19,7 @@ package org.apache.lucene.document;
import java.io.IOException;
import java.util.Arrays;
+import org.apache.lucene.geo.Rectangle;
import org.apache.lucene.index.PointValues.IntersectVisitor;
import org.apache.lucene.index.PointValues.Relation;
import org.apache.lucene.search.ConstantScoreScorer;
@@ -42,8 +43,7 @@ import org.apache.lucene.util.FixedBitSet;
import org.apache.lucene.util.NumericUtils;
import org.apache.lucene.util.SparseFixedBitSet;
import org.apache.lucene.util.StringHelper;
-import org.apache.lucene.spatial.util.GeoRect;
-import org.apache.lucene.spatial.util.Polygon;
+import org.apache.lucene.geo.Polygon;
/** Finds all previously indexed points that fall within the specified polygons.
*
@@ -84,7 +84,7 @@ final class LatLonPointInPolygonQuery extends Query {
// bounding box over all polygons, this can speed up tree intersection/cheaply improve approximation for complex multi-polygons
// these are pre-encoded with LatLonPoint's encoding
- final GeoRect box = GeoRect.fromPolygon(polygons);
+ 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];
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6c219e99/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceSort.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceSort.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceSort.java
index ac402b6..5ce819c 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceSort.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceSort.java
@@ -19,6 +19,7 @@ package org.apache.lucene.document;
import java.io.IOException;
import java.util.Arrays;
+import org.apache.lucene.geo.GeoTestUtil;
import org.apache.lucene.index.IndexReader;
import org.apache.lucene.index.IndexWriterConfig;
import org.apache.lucene.index.RandomIndexWriter;
@@ -29,7 +30,6 @@ import org.apache.lucene.search.MatchAllDocsQuery;
import org.apache.lucene.search.Sort;
import org.apache.lucene.search.SortField;
import org.apache.lucene.search.TopDocs;
-import org.apache.lucene.spatial.util.GeoTestUtil;
import org.apache.lucene.store.Directory;
import org.apache.lucene.util.LuceneTestCase;
import org.apache.lucene.util.SloppyMath;
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6c219e99/lucene/sandbox/src/test/org/apache/lucene/search/TestLatLonPointQueries.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/search/TestLatLonPointQueries.java b/lucene/sandbox/src/test/org/apache/lucene/search/TestLatLonPointQueries.java
index 3bde389..08b9ebf 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/search/TestLatLonPointQueries.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/search/TestLatLonPointQueries.java
@@ -19,7 +19,7 @@ package org.apache.lucene.search;
import org.apache.lucene.document.Document;
import org.apache.lucene.document.LatLonPoint;
import org.apache.lucene.spatial.util.BaseGeoPointTestCase;
-import org.apache.lucene.spatial.util.Polygon;
+import org.apache.lucene.geo.Polygon;
public class TestLatLonPointQueries extends BaseGeoPointTestCase {
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6c219e99/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQuery.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQuery.java b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQuery.java
index c7ac6eb..9e90a11 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQuery.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQuery.java
@@ -21,7 +21,7 @@ import org.apache.lucene.search.BooleanClause;
import org.apache.lucene.search.BooleanQuery;
import org.apache.lucene.search.Query;
import org.apache.lucene.spatial.geopoint.document.GeoPointField.TermEncoding;
-import org.apache.lucene.spatial.util.GeoRect;
+import org.apache.lucene.geo.Rectangle;
import org.apache.lucene.geo.GeoUtils;
/** Implements a simple point distance query on a GeoPoint field. This is based on
@@ -80,10 +80,10 @@ public class GeoPointDistanceQuery extends GeoPointInBBoxQuery {
* {@link org.apache.lucene.spatial.geopoint.document.GeoPointField.TermEncoding} parameter
**/
public GeoPointDistanceQuery(final String field, final TermEncoding termEncoding, final double centerLat, final double centerLon, final double radiusMeters) {
- this(field, termEncoding, GeoRect.fromPointDistance(centerLat, centerLon, checkRadius(radiusMeters)), centerLat, centerLon, radiusMeters);
+ this(field, termEncoding, Rectangle.fromPointDistance(centerLat, centerLon, checkRadius(radiusMeters)), centerLat, centerLon, radiusMeters);
}
- private GeoPointDistanceQuery(final String field, final TermEncoding termEncoding, final GeoRect bbox,
+ private GeoPointDistanceQuery(final String field, final TermEncoding termEncoding, final Rectangle bbox,
final double centerLat, final double centerLon, final double radiusMeters) {
super(field, termEncoding, bbox.minLat, bbox.maxLat, bbox.minLon, bbox.maxLon);
@@ -105,7 +105,7 @@ public class GeoPointDistanceQuery extends GeoPointInBBoxQuery {
unwrappedLon += -360.0D;
}
GeoPointDistanceQueryImpl left = new GeoPointDistanceQueryImpl(field, termEncoding, this, unwrappedLon,
- new GeoRect(minLat, maxLat, GeoUtils.MIN_LON_INCL, maxLon));
+ new Rectangle(minLat, maxLat, GeoUtils.MIN_LON_INCL, maxLon));
bqb.add(new BooleanClause(left, BooleanClause.Occur.SHOULD));
if (unwrappedLon < maxLon) {
@@ -113,13 +113,13 @@ public class GeoPointDistanceQuery extends GeoPointInBBoxQuery {
unwrappedLon += 360.0D;
}
GeoPointDistanceQueryImpl right = new GeoPointDistanceQueryImpl(field, termEncoding, this, unwrappedLon,
- new GeoRect(minLat, maxLat, minLon, GeoUtils.MAX_LON_INCL));
+ new Rectangle(minLat, maxLat, minLon, GeoUtils.MAX_LON_INCL));
bqb.add(new BooleanClause(right, BooleanClause.Occur.SHOULD));
return bqb.build();
}
return new GeoPointDistanceQueryImpl(field, termEncoding, this, centerLon,
- new GeoRect(this.minLat, this.maxLat, this.minLon, this.maxLon));
+ new Rectangle(this.minLat, this.maxLat, this.minLon, this.maxLon));
}
@Override
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6c219e99/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQueryImpl.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQueryImpl.java b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQueryImpl.java
index 46dcce9..a360fdb 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQueryImpl.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQueryImpl.java
@@ -16,9 +16,9 @@
*/
package org.apache.lucene.spatial.geopoint.search;
+import org.apache.lucene.geo.Rectangle;
import org.apache.lucene.search.MultiTermQuery;
import org.apache.lucene.spatial.geopoint.document.GeoPointField.TermEncoding;
-import org.apache.lucene.spatial.util.GeoRect;
import org.apache.lucene.util.SloppyMath;
/** Package private implementation for the public facing GeoPointDistanceQuery delegate class.
@@ -36,7 +36,7 @@ final class GeoPointDistanceQueryImpl extends GeoPointInBBoxQueryImpl {
final double axisLat;
GeoPointDistanceQueryImpl(final String field, final TermEncoding termEncoding, final GeoPointDistanceQuery q,
- final double centerLonUnwrapped, final GeoRect bbox) {
+ final double centerLonUnwrapped, final Rectangle bbox) {
super(field, termEncoding, bbox.minLat, bbox.maxLat, bbox.minLon, bbox.maxLon);
distanceQuery = q;
centerLon = centerLonUnwrapped;
@@ -49,7 +49,7 @@ final class GeoPointDistanceQueryImpl extends GeoPointInBBoxQueryImpl {
} else {
maxPartialDistance = Double.POSITIVE_INFINITY;
}
- axisLat = GeoRect.axisLat(distanceQuery.centerLat, distanceQuery.radiusMeters);
+ axisLat = Rectangle.axisLat(distanceQuery.centerLat, distanceQuery.radiusMeters);
}
@Override
@@ -75,7 +75,7 @@ final class GeoPointDistanceQueryImpl extends GeoPointInBBoxQueryImpl {
minLat > GeoPointDistanceQueryImpl.this.maxLat ||
minLon > GeoPointDistanceQueryImpl.this.maxLon) {
return false;
- } else if ((centerLon < minLon || centerLon > maxLon) && (axisLat+GeoRect.AXISLAT_ERROR < minLat || axisLat-GeoRect.AXISLAT_ERROR > maxLat)) {
+ } else if ((centerLon < minLon || centerLon > maxLon) && (axisLat+ Rectangle.AXISLAT_ERROR < minLat || axisLat- Rectangle.AXISLAT_ERROR > maxLat)) {
if (SloppyMath.haversinMeters(distanceQuery.centerLat, centerLon, minLat, minLon) > distanceQuery.radiusMeters &&
SloppyMath.haversinMeters(distanceQuery.centerLat, centerLon, minLat, maxLon) > distanceQuery.radiusMeters &&
SloppyMath.haversinMeters(distanceQuery.centerLat, centerLon, maxLat, minLon) > distanceQuery.radiusMeters &&
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6c219e99/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInPolygonQuery.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInPolygonQuery.java b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInPolygonQuery.java
index 0d29d25..17ce54d 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInPolygonQuery.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInPolygonQuery.java
@@ -23,8 +23,8 @@ import org.apache.lucene.search.Query;
import org.apache.lucene.spatial.geopoint.document.GeoPointField;
import org.apache.lucene.spatial.geopoint.document.GeoPointField.TermEncoding;
import org.apache.lucene.spatial.util.GeoEncodingUtils;
-import org.apache.lucene.spatial.util.GeoRect;
-import org.apache.lucene.spatial.util.Polygon;
+import org.apache.lucene.geo.Rectangle;
+import org.apache.lucene.geo.Polygon;
/** Implements a simple point in polygon query on a GeoPoint field. This is based on
* {@code GeoPointInBBoxQueryImpl} and is implemented using a
@@ -82,11 +82,11 @@ public final class GeoPointInPolygonQuery extends GeoPointInBBoxQuery {
* that fall within or on the boundary of the polygon defined by the input parameters.
*/
public GeoPointInPolygonQuery(String field, TermEncoding termEncoding, Polygon... polygons) {
- this(field, termEncoding, GeoRect.fromPolygon(polygons), polygons);
+ this(field, termEncoding, Rectangle.fromPolygon(polygons), polygons);
}
// internal constructor
- private GeoPointInPolygonQuery(String field, TermEncoding termEncoding, GeoRect boundingBox, Polygon... polygons) {
+ private GeoPointInPolygonQuery(String field, TermEncoding termEncoding, Rectangle boundingBox, Polygon... polygons) {
super(field, termEncoding, boundingBox.minLat, boundingBox.maxLat, boundingBox.minLon, boundingBox.maxLon);
this.polygons = polygons.clone();
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6c219e99/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInPolygonQueryImpl.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInPolygonQueryImpl.java b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInPolygonQueryImpl.java
index 20c9078..1bb43c7 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInPolygonQueryImpl.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInPolygonQueryImpl.java
@@ -20,7 +20,7 @@ import java.util.Objects;
import org.apache.lucene.search.MultiTermQuery;
import org.apache.lucene.spatial.geopoint.document.GeoPointField.TermEncoding;
-import org.apache.lucene.spatial.util.Polygon;
+import org.apache.lucene.geo.Polygon;
/** Package private implementation for the public facing GeoPointInPolygonQuery delegate class.
*
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6c219e99/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoRect.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoRect.java b/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoRect.java
deleted file mode 100644
index fdde3bf..0000000
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/util/GeoRect.java
+++ /dev/null
@@ -1,191 +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.spatial.util;
-
-import org.apache.lucene.geo.GeoUtils;
-
-import static java.lang.Math.PI;
-import static java.lang.Math.max;
-import static java.lang.Math.min;
-import static java.lang.Math.toDegrees;
-import static java.lang.Math.toRadians;
-import static org.apache.lucene.geo.GeoUtils.checkLatitude;
-import static org.apache.lucene.geo.GeoUtils.checkLongitude;
-import static org.apache.lucene.geo.GeoUtils.MAX_LAT_INCL;
-import static org.apache.lucene.geo.GeoUtils.MIN_LAT_INCL;
-import static org.apache.lucene.geo.GeoUtils.MAX_LAT_RADIANS;
-import static org.apache.lucene.geo.GeoUtils.MAX_LON_RADIANS;
-import static org.apache.lucene.geo.GeoUtils.MIN_LAT_RADIANS;
-import static org.apache.lucene.geo.GeoUtils.MIN_LON_RADIANS;
-import static org.apache.lucene.geo.GeoUtils.EARTH_MEAN_RADIUS_METERS;
-import static org.apache.lucene.geo.GeoUtils.sloppySin;
-import static org.apache.lucene.util.SloppyMath.TO_DEGREES;
-import static org.apache.lucene.util.SloppyMath.asin;
-import static org.apache.lucene.util.SloppyMath.cos;
-
-/** Represents a lat/lon rectangle. */
-public class GeoRect {
- /** maximum longitude value (in degrees) */
- public final double minLat;
- /** minimum longitude value (in degrees) */
- public final double minLon;
- /** maximum latitude value (in degrees) */
- public final double maxLat;
- /** minimum latitude value (in degrees) */
- public final double maxLon;
-
- /**
- * Constructs a bounding box by first validating the provided latitude and longitude coordinates
- */
- public GeoRect(double minLat, double maxLat, double minLon, double maxLon) {
- GeoUtils.checkLatitude(minLat);
- GeoUtils.checkLatitude(maxLat);
- GeoUtils.checkLongitude(minLon);
- GeoUtils.checkLongitude(maxLon);
- this.minLon = minLon;
- this.maxLon = maxLon;
- this.minLat = minLat;
- this.maxLat = maxLat;
- assert maxLat >= minLat;
-
- // NOTE: cannot assert maxLon >= minLon since this rect could cross the dateline
- }
-
- @Override
- public String toString() {
- StringBuilder b = new StringBuilder();
- b.append("GeoRect(lat=");
- b.append(minLat);
- b.append(" TO ");
- b.append(maxLat);
- b.append(" lon=");
- b.append(minLon);
- b.append(" TO ");
- b.append(maxLon);
- if (maxLon < minLon) {
- b.append(" [crosses dateline!]");
- }
- b.append(")");
-
- return b.toString();
- }
-
- /** Returns true if this bounding box crosses the dateline */
- public boolean crossesDateline() {
- return maxLon < minLon;
- }
-
- /** Compute Bounding Box for a circle using WGS-84 parameters */
- public static GeoRect fromPointDistance(final double centerLat, final double centerLon, final double radiusMeters) {
- checkLatitude(centerLat);
- checkLongitude(centerLon);
- final double radLat = toRadians(centerLat);
- final double radLon = toRadians(centerLon);
- // LUCENE-7143
- double radDistance = (radiusMeters + 7E-2) / EARTH_MEAN_RADIUS_METERS;
- double minLat = radLat - radDistance;
- double maxLat = radLat + radDistance;
- double minLon;
- double maxLon;
-
- if (minLat > MIN_LAT_RADIANS && maxLat < MAX_LAT_RADIANS) {
- double deltaLon = asin(sloppySin(radDistance) / cos(radLat));
- minLon = radLon - deltaLon;
- if (minLon < MIN_LON_RADIANS) {
- minLon += 2d * PI;
- }
- maxLon = radLon + deltaLon;
- if (maxLon > MAX_LON_RADIANS) {
- maxLon -= 2d * PI;
- }
- } else {
- // a pole is within the distance
- minLat = max(minLat, MIN_LAT_RADIANS);
- maxLat = min(maxLat, MAX_LAT_RADIANS);
- minLon = MIN_LON_RADIANS;
- maxLon = MAX_LON_RADIANS;
- }
-
- return new GeoRect(toDegrees(minLat), toDegrees(maxLat), toDegrees(minLon), toDegrees(maxLon));
- }
-
- /** maximum error from {@link #axisLat(double, double)}. logic must be prepared to handle this */
- public static final double AXISLAT_ERROR = 0.1D / EARTH_MEAN_RADIUS_METERS * TO_DEGREES;
-
- /**
- * Calculate the latitude of a circle's intersections with its bbox meridians.
- * <p>
- * <b>NOTE:</b> the returned value will be +/- {@link #AXISLAT_ERROR} of the actual value.
- * @param centerLat The latitude of the circle center
- * @param radiusMeters The radius of the circle in meters
- * @return A latitude
- */
- public static double axisLat(double centerLat, double radiusMeters) {
- // A spherical triangle with:
- // r is the radius of the circle in radians
- // l1 is the latitude of the circle center
- // l2 is the latitude of the point at which the circle intersect's its bbox longitudes
- // We know r is tangent to the bbox meridians at l2, therefore it is a right angle.
- // So from the law of cosines, with the angle of l1 being 90, we have:
- // cos(l1) = cos(r) * cos(l2) + sin(r) * sin(l2) * cos(90)
- // The second part cancels out because cos(90) == 0, so we have:
- // cos(l1) = cos(r) * cos(l2)
- // Solving for l2, we get:
- // l2 = acos( cos(l1) / cos(r) )
- // We ensure r is in the range (0, PI/2) and l1 in the range (0, PI/2]. This means we
- // cannot divide by 0, and we will always get a positive value in the range [0, 1) as
- // the argument to arc cosine, resulting in a range (0, PI/2].
- final double PIO2 = Math.PI / 2D;
- double l1 = toRadians(centerLat);
- double r = (radiusMeters + 7E-2) / EARTH_MEAN_RADIUS_METERS;
-
- // if we are within radius range of a pole, the lat is the pole itself
- if (Math.abs(l1) + r >= MAX_LAT_RADIANS) {
- return centerLat >= 0 ? MAX_LAT_INCL : MIN_LAT_INCL;
- }
-
- // adjust l1 as distance from closest pole, to form a right triangle with bbox meridians
- // and ensure it is in the range (0, PI/2]
- l1 = centerLat >= 0 ? PIO2 - l1 : l1 + PIO2;
-
- double l2 = Math.acos(Math.cos(l1) / Math.cos(r));
- assert !Double.isNaN(l2);
-
- // now adjust back to range [-pi/2, pi/2], ie latitude in radians
- l2 = centerLat >= 0 ? PIO2 - l2 : l2 - PIO2;
-
- return toDegrees(l2);
- }
-
- /** Returns the bounding box over an array of polygons */
- public static GeoRect fromPolygon(Polygon[] polygons) {
- // compute bounding box
- double minLat = Double.POSITIVE_INFINITY;
- double maxLat = Double.NEGATIVE_INFINITY;
- double minLon = Double.POSITIVE_INFINITY;
- double maxLon = Double.NEGATIVE_INFINITY;
-
- for (int i = 0;i < polygons.length; i++) {
- minLat = Math.min(polygons[i].minLat, minLat);
- maxLat = Math.max(polygons[i].maxLat, maxLat);
- minLon = Math.min(polygons[i].minLon, minLon);
- maxLon = Math.max(polygons[i].maxLon, maxLon);
- }
-
- return new GeoRect(minLat, maxLat, minLon, maxLon);
- }
-}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6c219e99/lucene/spatial/src/java/org/apache/lucene/spatial/util/Polygon.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/util/Polygon.java b/lucene/spatial/src/java/org/apache/lucene/spatial/util/Polygon.java
deleted file mode 100644
index c0e2323..0000000
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/util/Polygon.java
+++ /dev/null
@@ -1,314 +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.spatial.util;
-
-import java.util.Arrays;
-
-import org.apache.lucene.geo.GeoUtils;
-
-/**
- * Represents a closed polygon on the earth's surface.
- * @lucene.experimental
- */
-public final class Polygon {
- private final double[] polyLats;
- private final double[] polyLons;
- private final Polygon[] holes;
-
- /** minimum latitude of this polygon's bounding box area */
- public final double minLat;
- /** maximum latitude of this polygon's bounding box area */
- public final double maxLat;
- /** minimum longitude of this polygon's bounding box area */
- public final double minLon;
- /** maximum longitude of this polygon's bounding box area */
- public final double maxLon;
-
- // TODO: we could also compute the maximal inner bounding box, to make relations faster to compute?
-
- /**
- * Creates a new Polygon from the supplied latitude/longitude array, and optionally any holes.
- */
- public Polygon(double[] polyLats, double[] polyLons, Polygon... holes) {
- if (polyLats == null) {
- throw new IllegalArgumentException("polyLats must not be null");
- }
- if (polyLons == null) {
- throw new IllegalArgumentException("polyLons must not be null");
- }
- if (holes == null) {
- throw new IllegalArgumentException("holes must not be null");
- }
- if (polyLats.length != polyLons.length) {
- throw new IllegalArgumentException("polyLats and polyLons must be equal length");
- }
- if (polyLats.length != polyLons.length) {
- throw new IllegalArgumentException("polyLats and polyLons must be equal length");
- }
- if (polyLats.length < 4) {
- throw new IllegalArgumentException("at least 4 polygon points required");
- }
- if (polyLats[0] != polyLats[polyLats.length-1]) {
- throw new IllegalArgumentException("first and last points of the polygon must be the same (it must close itself): polyLats[0]=" + polyLats[0] + " polyLats[" + (polyLats.length-1) + "]=" + polyLats[polyLats.length-1]);
- }
- if (polyLons[0] != polyLons[polyLons.length-1]) {
- throw new IllegalArgumentException("first and last points of the polygon must be the same (it must close itself): polyLons[0]=" + polyLons[0] + " polyLons[" + (polyLons.length-1) + "]=" + polyLons[polyLons.length-1]);
- }
- for (int i = 0; i < polyLats.length; i++) {
- GeoUtils.checkLatitude(polyLats[i]);
- GeoUtils.checkLongitude(polyLons[i]);
- }
- for (int i = 0; i < holes.length; i++) {
- Polygon inner = holes[i];
- if (inner.holes.length > 0) {
- throw new IllegalArgumentException("holes may not contain holes: polygons may not nest.");
- }
- }
- this.polyLats = polyLats.clone();
- this.polyLons = polyLons.clone();
- 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;
-
- for (int i = 0;i < polyLats.length; 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);
- }
- this.minLat = minLat;
- this.maxLat = maxLat;
- this.minLon = minLon;
- this.maxLon = maxLon;
- }
-
- /** Returns true if the point is contained within this polygon */
- public boolean contains(double latitude, double longitude) {
- // check bounding box
- if (latitude < minLat || latitude > maxLat || longitude < minLon || longitude > maxLon) {
- return false;
- }
- /*
- * simple even-odd point in polygon computation
- * 1. Determine if point is contained in the longitudinal range
- * 2. Determine whether point crosses the edge by computing the latitudinal delta
- * between the end-point of a parallel vector (originating at the point) and the
- * y-component of the edge sink
- *
- * NOTE: Requires polygon point (x,y) order either clockwise or counter-clockwise
- */
- boolean inPoly = false;
- /*
- * Note: This is using a euclidean coordinate system which could result in
- * upwards of 110KM error at the equator.
- * TODO convert coordinates to cylindrical projection (e.g. mercator)
- */
- for (int i = 1; i < polyLats.length; i++) {
- if (polyLons[i] <= longitude && polyLons[i-1] >= longitude || polyLons[i-1] <= longitude && polyLons[i] >= longitude) {
- if (polyLats[i] + (longitude - polyLons[i]) / (polyLons[i-1] - polyLons[i]) * (polyLats[i-1] - polyLats[i]) <= latitude) {
- inPoly = !inPoly;
- }
- }
- }
- if (inPoly) {
- for (Polygon hole : holes) {
- if (hole.contains(latitude, longitude)) {
- return false;
- }
- }
- return true;
- } else {
- return false;
- }
- }
-
- /**
- * Computes whether a rectangle is within a polygon (shared boundaries not allowed)
- */
- public boolean contains(double minLat, double maxLat, double minLon, double maxLon) {
- // check if rectangle crosses poly (to handle concave/pacman polys), then check that all 4 corners
- // are contained
- boolean contains = crosses(minLat, maxLat, minLon, maxLon) == false &&
- contains(minLat, minLon) &&
- contains(minLat, maxLon) &&
- contains(maxLat, maxLon) &&
- contains(maxLat, minLon);
-
- if (contains) {
- // if we intersect with any hole, game over
- for (Polygon hole : holes) {
- if (hole.crosses(minLat, maxLat, minLon, maxLon) || hole.contains(minLat, maxLat, minLon, maxLon)) {
- return false;
- }
- }
- return true;
- } else {
- return false;
- }
- }
-
- /**
- * Convenience method for accurately computing whether a rectangle crosses a poly.
- */
- public boolean crosses(double minLat, double maxLat, final double minLon, final double maxLon) {
- // if the bounding boxes are disjoint then the shape does not cross
- if (maxLon < this.minLon || minLon > this.maxLon || maxLat < this.minLat || minLat > this.maxLat) {
- return false;
- }
- // if the rectangle fully encloses us, we cross.
- if (minLat <= this.minLat && maxLat >= this.maxLat && minLon <= this.minLon && maxLon >= this.maxLon) {
- return true;
- }
- // if we cross any hole, we cross
- for (Polygon hole : holes) {
- if (hole.crosses(minLat, maxLat, minLon, maxLon)) {
- return true;
- }
- }
-
- /*
- * Accurately compute (within restrictions of cartesian decimal degrees) whether a rectangle crosses a polygon
- */
- final double[][] bbox = new double[][] { {minLon, minLat}, {maxLon, minLat}, {maxLon, maxLat}, {minLon, maxLat}, {minLon, minLat} };
- final int polyLength = polyLons.length-1;
- double d, s, t, a1, b1, c1, a2, b2, c2;
- double x00, y00, x01, y01, x10, y10, x11, y11;
-
- // computes the intersection point between each bbox edge and the polygon edge
- for (short b=0; b<4; ++b) {
- a1 = bbox[b+1][1]-bbox[b][1];
- b1 = bbox[b][0]-bbox[b+1][0];
- c1 = a1*bbox[b+1][0] + b1*bbox[b+1][1];
- for (int p=0; p<polyLength; ++p) {
- a2 = polyLats[p+1]-polyLats[p];
- b2 = polyLons[p]-polyLons[p+1];
- // compute determinant
- d = a1*b2 - a2*b1;
- if (d != 0) {
- // lines are not parallel, check intersecting points
- c2 = a2*polyLons[p+1] + b2*polyLats[p+1];
- s = (1/d)*(b2*c1 - b1*c2);
- t = (1/d)*(a1*c2 - a2*c1);
- x00 = Math.min(bbox[b][0], bbox[b+1][0]) - GeoEncodingUtils.TOLERANCE;
- x01 = Math.max(bbox[b][0], bbox[b+1][0]) + GeoEncodingUtils.TOLERANCE;
- y00 = Math.min(bbox[b][1], bbox[b+1][1]) - GeoEncodingUtils.TOLERANCE;
- y01 = Math.max(bbox[b][1], bbox[b+1][1]) + GeoEncodingUtils.TOLERANCE;
- x10 = Math.min(polyLons[p], polyLons[p+1]) - GeoEncodingUtils.TOLERANCE;
- x11 = Math.max(polyLons[p], polyLons[p+1]) + GeoEncodingUtils.TOLERANCE;
- y10 = Math.min(polyLats[p], polyLats[p+1]) - GeoEncodingUtils.TOLERANCE;
- y11 = Math.max(polyLats[p], polyLats[p+1]) + GeoEncodingUtils.TOLERANCE;
- // check whether the intersection point is touching one of the line segments
- boolean touching = ((x00 == s && y00 == t) || (x01 == s && y01 == t))
- || ((x10 == s && y10 == t) || (x11 == s && y11 == t));
- // if line segments are not touching and the intersection point is within the range of either segment
- if (!(touching || x00 > s || x01 < s || y00 > t || y01 < t || x10 > s || x11 < s || y10 > t || y11 < t)) {
- return true;
- }
- }
- } // for each poly edge
- } // for each bbox edge
- return false;
- }
-
- /** Returns a copy of the internal latitude array */
- public double[] getPolyLats() {
- return polyLats.clone();
- }
-
- /** Returns a copy of the internal longitude array */
- public double[] getPolyLons() {
- return polyLons.clone();
- }
-
- /** Returns a copy of the internal holes array */
- public Polygon[] getHoles() {
- return holes.clone();
- }
-
- /** Helper for multipolygon logic: returns true if any of the supplied polygons contain the point */
- public static boolean contains(Polygon[] polygons, double latitude, double longitude) {
- for (Polygon polygon : polygons) {
- if (polygon.contains(latitude, longitude)) {
- return true;
- }
- }
- return false;
- }
-
- /** Helper for multipolygon logic: returns true if any of the supplied polygons contain the rectangle */
- public static boolean contains(Polygon[] polygons, double minLat, double maxLat, double minLon, double maxLon) {
- for (Polygon polygon : polygons) {
- if (polygon.contains(minLat, maxLat, minLon, maxLon)) {
- return true;
- }
- }
- return false;
- }
-
- /** Helper for multipolygon logic: returns true if any of the supplied polygons crosses the rectangle */
- public static boolean crosses(Polygon[] polygons, double minLat, double maxLat, double minLon, double maxLon) {
- for (Polygon polygon : polygons) {
- if (polygon.crosses(minLat, maxLat, minLon, maxLon)) {
- return true;
- }
- }
- return false;
- }
-
- @Override
- public int hashCode() {
- final int prime = 31;
- int result = 1;
- result = prime * result + Arrays.hashCode(holes);
- result = prime * result + Arrays.hashCode(polyLats);
- result = prime * result + Arrays.hashCode(polyLons);
- return result;
- }
-
- @Override
- public boolean equals(Object obj) {
- if (this == obj) return true;
- if (obj == null) return false;
- if (getClass() != obj.getClass()) return false;
- Polygon other = (Polygon) obj;
- if (!Arrays.equals(holes, other.holes)) return false;
- if (!Arrays.equals(polyLats, other.polyLats)) return false;
- if (!Arrays.equals(polyLons, other.polyLons)) return false;
- return true;
- }
-
- @Override
- public String toString() {
- StringBuilder sb = new StringBuilder();
- for (int i = 0; i < polyLats.length; i++) {
- sb.append("[")
- .append(polyLats[i])
- .append(", ")
- .append(polyLons[i])
- .append("] ");
- }
- if (holes.length > 0) {
- sb.append(", holes=");
- sb.append(Arrays.toString(holes));
- }
- return sb.toString();
- }
-}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6c219e99/lucene/spatial/src/test/org/apache/lucene/spatial/geopoint/search/TestGeoPointQuery.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/test/org/apache/lucene/spatial/geopoint/search/TestGeoPointQuery.java b/lucene/spatial/src/test/org/apache/lucene/spatial/geopoint/search/TestGeoPointQuery.java
index 91afe3f..ff8baca 100644
--- a/lucene/spatial/src/test/org/apache/lucene/spatial/geopoint/search/TestGeoPointQuery.java
+++ b/lucene/spatial/src/test/org/apache/lucene/spatial/geopoint/search/TestGeoPointQuery.java
@@ -19,7 +19,7 @@ package org.apache.lucene.spatial.geopoint.search;
import org.apache.lucene.document.Document;
import org.apache.lucene.search.Query;
import org.apache.lucene.spatial.util.GeoEncodingUtils;
-import org.apache.lucene.spatial.util.Polygon;
+import org.apache.lucene.geo.Polygon;
import org.apache.lucene.spatial.geopoint.document.GeoPointField;
import org.apache.lucene.spatial.geopoint.document.GeoPointField.TermEncoding;
import org.apache.lucene.spatial.util.BaseGeoPointTestCase;
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6c219e99/lucene/spatial/src/test/org/apache/lucene/spatial/geopoint/search/TestLegacyGeoPointQuery.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/test/org/apache/lucene/spatial/geopoint/search/TestLegacyGeoPointQuery.java b/lucene/spatial/src/test/org/apache/lucene/spatial/geopoint/search/TestLegacyGeoPointQuery.java
index cd15f66..4c8e3e3 100644
--- a/lucene/spatial/src/test/org/apache/lucene/spatial/geopoint/search/TestLegacyGeoPointQuery.java
+++ b/lucene/spatial/src/test/org/apache/lucene/spatial/geopoint/search/TestLegacyGeoPointQuery.java
@@ -19,7 +19,7 @@ package org.apache.lucene.spatial.geopoint.search;
import org.apache.lucene.document.Document;
import org.apache.lucene.search.Query;
import org.apache.lucene.spatial.util.GeoEncodingUtils;
-import org.apache.lucene.spatial.util.Polygon;
+import org.apache.lucene.geo.Polygon;
import org.apache.lucene.spatial.geopoint.document.GeoPointField;
import org.apache.lucene.spatial.geopoint.document.GeoPointField.TermEncoding;
import org.apache.lucene.spatial.util.BaseGeoPointTestCase;
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6c219e99/lucene/spatial/src/test/org/apache/lucene/spatial/util/BaseGeoPointTestCase.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/test/org/apache/lucene/spatial/util/BaseGeoPointTestCase.java b/lucene/spatial/src/test/org/apache/lucene/spatial/util/BaseGeoPointTestCase.java
index 182ec6f..6ae4d20 100644
--- a/lucene/spatial/src/test/org/apache/lucene/spatial/util/BaseGeoPointTestCase.java
+++ b/lucene/spatial/src/test/org/apache/lucene/spatial/util/BaseGeoPointTestCase.java
@@ -37,7 +37,10 @@ import org.apache.lucene.document.Field;
import org.apache.lucene.document.NumericDocValuesField;
import org.apache.lucene.document.StoredField;
import org.apache.lucene.document.StringField;
+import org.apache.lucene.geo.Rectangle;
+import org.apache.lucene.geo.GeoTestUtil;
import org.apache.lucene.geo.GeoUtils;
+import org.apache.lucene.geo.Polygon;
import org.apache.lucene.index.DirectoryReader;
import org.apache.lucene.index.IndexReader;
import org.apache.lucene.index.IndexWriter;
@@ -537,7 +540,7 @@ public abstract class BaseGeoPointTestCase extends LuceneTestCase {
int iters = atLeast(25);
for (int iter=0;iter<iters;iter++) {
- GeoRect rect = randomRect(small);
+ Rectangle rect = randomRect(small);
if (VERBOSE) {
System.out.println("\nTEST: iter=" + iter + " rect=" + rect);
@@ -716,7 +719,7 @@ public abstract class BaseGeoPointTestCase extends LuceneTestCase {
return lon;
}
- protected GeoRect randomRect(boolean small) {
+ protected Rectangle randomRect(boolean small) {
if (small) {
return GeoTestUtil.nextBoxNear(originLat, originLon);
} else {
@@ -732,7 +735,7 @@ public abstract class BaseGeoPointTestCase extends LuceneTestCase {
protected abstract Query newPolygonQuery(String field, Polygon... polygon);
- static final boolean rectContainsPoint(GeoRect rect, double pointLat, double pointLon) {
+ static final boolean rectContainsPoint(Rectangle rect, double pointLat, double pointLon) {
assert Double.isNaN(pointLat) == false;
if (rect.minLon < rect.maxLon) {
@@ -820,7 +823,7 @@ public abstract class BaseGeoPointTestCase extends LuceneTestCase {
System.out.println("\nTEST: iter=" + iter + " s=" + s);
}
- GeoRect rect = randomRect(small);
+ Rectangle rect = randomRect(small);
Query query = newRectQuery(FIELD_NAME, rect.minLat, rect.maxLat, rect.minLon, rect.maxLon);
@@ -1173,7 +1176,7 @@ public abstract class BaseGeoPointTestCase extends LuceneTestCase {
}
public void testRectBoundariesAreInclusive() throws Exception {
- GeoRect rect;
+ Rectangle rect;
// TODO: why this dateline leniency???
while (true) {
rect = randomRect(random().nextBoolean());
@@ -1182,7 +1185,7 @@ public abstract class BaseGeoPointTestCase extends LuceneTestCase {
}
}
// this test works in quantized space: for testing inclusiveness of exact edges it must be aware of index-time quantization!
- rect = new GeoRect(quantizeLat(rect.minLat), quantizeLat(rect.maxLat), quantizeLon(rect.minLon), quantizeLon(rect.maxLon));
+ rect = new Rectangle(quantizeLat(rect.minLat), quantizeLat(rect.maxLat), quantizeLon(rect.minLon), quantizeLon(rect.maxLon));
Directory dir = newDirectory();
IndexWriterConfig iwc = newIndexWriterConfig();
// Else seeds may not reproduce:
@@ -1341,7 +1344,7 @@ public abstract class BaseGeoPointTestCase extends LuceneTestCase {
public void testEquals() throws Exception {
Query q1, q2;
- GeoRect rect = randomRect(false);
+ Rectangle rect = randomRect(false);
q1 = newRectQuery("field", rect.minLat, rect.maxLat, rect.minLon, rect.maxLon);
q2 = newRectQuery("field", rect.minLat, rect.maxLat, rect.minLon, rect.maxLon);