lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From no...@apache.org
Subject [28/50] [abbrv] lucene-solr:apiv2: LUCENE-7163: refactor GeoRect, Polygon, and GeoUtils tests to geo package in core.
Date Thu, 07 Apr 2016 20:30:00 GMT
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/apiv2
Commit: 6c219e99e4b7018ec75430a1eb880566e63d4d63
Parents: d0156b1
Author: nknize <nknize@apache.org>
Authored: Fri Apr 1 13:12:34 2016 -0500
Committer: nknize <nknize@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);


Mime
View raw message