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:48 UTC
[1/2] lucene-solr:master: LUCENE-7163: refactor GeoRect, Polygon,
and GeoUtils tests to geo package in core.
Repository: lucene-solr
Updated Branches:
refs/heads/master d0156b112 -> 6c219e99e
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6c219e99/lucene/spatial/src/test/org/apache/lucene/spatial/util/GeoTestUtil.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/test/org/apache/lucene/spatial/util/GeoTestUtil.java b/lucene/spatial/src/test/org/apache/lucene/spatial/util/GeoTestUtil.java
deleted file mode 100644
index 1e4fcf3..0000000
--- a/lucene/spatial/src/test/org/apache/lucene/spatial/util/GeoTestUtil.java
+++ /dev/null
@@ -1,500 +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.ArrayList;
-import java.util.List;
-import java.util.Random;
-
-import org.apache.lucene.geo.GeoUtils;
-import org.apache.lucene.util.SloppyMath;
-
-import com.carrotsearch.randomizedtesting.RandomizedContext;
-
-/** static methods for testing geo */
-public class GeoTestUtil {
-
- /** returns next pseudorandom latitude (anywhere) */
- public static double nextLatitude() {
- return -90 + 180.0 * random().nextDouble();
- }
-
- /** returns next pseudorandom longitude (anywhere) */
- public static double nextLongitude() {
- return -180 + 360.0 * random().nextDouble();
- }
-
- /** returns next pseudorandom latitude, kinda close to {@code otherLatitude} */
- public static double nextLatitudeNear(double otherLatitude) {
- GeoUtils.checkLatitude(otherLatitude);
- return normalizeLatitude(otherLatitude + random().nextDouble() - 0.5);
- }
-
- /** returns next pseudorandom longitude, kinda close to {@code otherLongitude} */
- public static double nextLongitudeNear(double otherLongitude) {
- GeoUtils.checkLongitude(otherLongitude);
- return normalizeLongitude(otherLongitude + random().nextDouble() - 0.5);
- }
-
- /**
- * returns next pseudorandom latitude, kinda close to {@code minLatitude/maxLatitude}
- * <b>NOTE:</b>minLatitude/maxLatitude are merely guidelines. the returned value is sometimes
- * outside of that range! this is to facilitate edge testing.
- */
- public static double nextLatitudeAround(double minLatitude, double maxLatitude) {
- GeoUtils.checkLatitude(minLatitude);
- GeoUtils.checkLatitude(maxLatitude);
- return normalizeLatitude(randomRangeMaybeSlightlyOutside(minLatitude, maxLatitude));
- }
-
- /**
- * returns next pseudorandom longitude, kinda close to {@code minLongitude/maxLongitude}
- * <b>NOTE:</b>minLongitude/maxLongitude are merely guidelines. the returned value is sometimes
- * outside of that range! this is to facilitate edge testing.
- */
- public static double nextLongitudeAround(double minLongitude, double maxLongitude) {
- GeoUtils.checkLongitude(minLongitude);
- GeoUtils.checkLongitude(maxLongitude);
- return normalizeLongitude(randomRangeMaybeSlightlyOutside(minLongitude, maxLongitude));
- }
-
- /** returns next pseudorandom box: can cross the 180th meridian */
- public static GeoRect nextBox() {
- return nextBoxInternal(nextLatitude(), nextLatitude(), nextLongitude(), nextLongitude(), true);
- }
-
- /** returns next pseudorandom box, can cross the 180th meridian, kinda close to {@code otherLatitude} and {@code otherLongitude} */
- public static GeoRect nextBoxNear(double otherLatitude, double otherLongitude) {
- GeoUtils.checkLongitude(otherLongitude);
- GeoUtils.checkLongitude(otherLongitude);
- return nextBoxInternal(nextLatitudeNear(otherLatitude), nextLatitudeNear(otherLatitude),
- nextLongitudeNear(otherLongitude), nextLongitudeNear(otherLongitude), true);
- }
-
- /** returns next pseudorandom polygon */
- public static Polygon nextPolygon() {
- if (random().nextBoolean()) {
- return surpriseMePolygon(null, null);
- }
-
- GeoRect box = nextBoxInternal(nextLatitude(), nextLatitude(), nextLongitude(), nextLongitude(), false);
- if (random().nextBoolean()) {
- // box
- return boxPolygon(box);
- } else {
- // triangle
- return trianglePolygon(box);
- }
- }
-
- /** returns next pseudorandom polygon, kinda close to {@code otherLatitude} and {@code otherLongitude} */
- public static Polygon nextPolygonNear(double otherLatitude, double otherLongitude) {
- if (random().nextBoolean()) {
- return surpriseMePolygon(otherLatitude, otherLongitude);
- }
-
- GeoRect box = nextBoxInternal(nextLatitudeNear(otherLatitude), nextLatitudeNear(otherLatitude),
- nextLongitudeNear(otherLongitude), nextLongitudeNear(otherLongitude), false);
- if (random().nextBoolean()) {
- // box
- return boxPolygon(box);
- } else {
- // triangle
- return trianglePolygon(box);
- }
- }
-
- private static GeoRect nextBoxInternal(double lat0, double lat1, double lon0, double lon1, boolean canCrossDateLine) {
- if (lat1 < lat0) {
- double x = lat0;
- lat0 = lat1;
- lat1 = x;
- }
-
- if (canCrossDateLine == false && lon1 < lon0) {
- double x = lon0;
- lon0 = lon1;
- lon1 = x;
- }
-
- return new GeoRect(lat0, lat1, lon0, lon1);
- }
-
- private static Polygon boxPolygon(GeoRect box) {
- assert box.crossesDateline() == false;
- final double[] polyLats = new double[5];
- final double[] polyLons = new double[5];
- polyLats[0] = box.minLat;
- polyLons[0] = box.minLon;
- polyLats[1] = box.maxLat;
- polyLons[1] = box.minLon;
- polyLats[2] = box.maxLat;
- polyLons[2] = box.maxLon;
- polyLats[3] = box.minLat;
- polyLons[3] = box.maxLon;
- polyLats[4] = box.minLat;
- polyLons[4] = box.minLon;
- return new Polygon(polyLats, polyLons);
- }
-
- private static Polygon trianglePolygon(GeoRect box) {
- assert box.crossesDateline() == false;
- final double[] polyLats = new double[4];
- final double[] polyLons = new double[4];
- polyLats[0] = box.minLat;
- polyLons[0] = box.minLon;
- polyLats[1] = box.maxLat;
- polyLons[1] = box.minLon;
- polyLats[2] = box.maxLat;
- polyLons[2] = box.maxLon;
- polyLats[3] = box.minLat;
- polyLons[3] = box.minLon;
- return new Polygon(polyLats, polyLons);
- }
-
- private static Polygon surpriseMePolygon(Double otherLatitude, Double otherLongitude) {
- // repeat until we get a poly that doesn't cross dateline:
- newPoly:
- while (true) {
- //System.out.println("\nPOLY ITER");
- final double centerLat;
- final double centerLon;
- if (otherLatitude == null) {
- centerLat = nextLatitude();
- centerLon = nextLongitude();
- } else {
- GeoUtils.checkLatitude(otherLatitude);
- GeoUtils.checkLongitude(otherLongitude);
- centerLat = nextLatitudeNear(otherLatitude);
- centerLon = nextLongitudeNear(otherLongitude);
- }
-
- double radius = 0.1 + 20 * random().nextDouble();
- double radiusDelta = random().nextDouble();
-
- ArrayList<Double> lats = new ArrayList<>();
- ArrayList<Double> lons = new ArrayList<>();
- double angle = 0.0;
- while (true) {
- angle += random().nextDouble()*40.0;
- //System.out.println(" angle " + angle);
- if (angle > 360) {
- break;
- }
- double len = radius * (1.0 - radiusDelta + radiusDelta * random().nextDouble());
- //System.out.println(" len=" + len);
- double lat = centerLat + len * Math.cos(Math.toRadians(angle));
- double lon = centerLon + len * Math.sin(Math.toRadians(angle));
- if (lon <= GeoUtils.MIN_LON_INCL || lon >= GeoUtils.MAX_LON_INCL) {
- // cannot cross dateline: try again!
- continue newPoly;
- }
- if (lat > 90) {
- // cross the north pole
- lat = 180 - lat;
- lon = 180 - lon;
- } else if (lat < -90) {
- // cross the south pole
- lat = -180 - lat;
- lon = 180 - lon;
- }
- if (lon <= GeoUtils.MIN_LON_INCL || lon >= GeoUtils.MAX_LON_INCL) {
- // cannot cross dateline: try again!
- continue newPoly;
- }
- lats.add(lat);
- lons.add(lon);
-
- //System.out.println(" lat=" + lats.get(lats.size()-1) + " lon=" + lons.get(lons.size()-1));
- }
-
- // close it
- lats.add(lats.get(0));
- lons.add(lons.get(0));
-
- double[] latsArray = new double[lats.size()];
- double[] lonsArray = new double[lons.size()];
- for(int i=0;i<lats.size();i++) {
- latsArray[i] = lats.get(i);
- lonsArray[i] = lons.get(i);
- }
- return new Polygon(latsArray, lonsArray);
- }
- }
-
- /** Returns random double min to max or up to 1% outside of that range */
- private static double randomRangeMaybeSlightlyOutside(double min, double max) {
- return min + (random().nextDouble() + (0.5 - random().nextDouble()) * .02) * (max - min);
- }
-
- /** Puts latitude in range of -90 to 90. */
- private static double normalizeLatitude(double latitude) {
- if (latitude >= -90 && latitude <= 90) {
- return latitude; //common case, and avoids slight double precision shifting
- }
- double off = Math.abs((latitude + 90) % 360);
- return (off <= 180 ? off : 360-off) - 90;
- }
-
- /** Puts longitude in range of -180 to +180. */
- private static double normalizeLongitude(double longitude) {
- if (longitude >= -180 && longitude <= 180) {
- return longitude; //common case, and avoids slight double precision shifting
- }
- double off = (longitude + 180) % 360;
- if (off < 0) {
- return 180 + off;
- } else if (off == 0 && longitude > 0) {
- return 180;
- } else {
- return -180 + off;
- }
- }
-
- /** Keep it simple, we don't need to take arbitrary Random for geo tests */
- private static Random random() {
- return RandomizedContext.current().getRandom();
- }
-
- // craziness for plotting stuff :)
-
- private static double wrapLat(double lat) {
- //System.out.println("wrapLat " + lat);
- if (lat > 90) {
- //System.out.println(" " + (180 - lat));
- return 180 - lat;
- } else if (lat < -90) {
- //System.out.println(" " + (-180 - lat));
- return -180 - lat;
- } else {
- //System.out.println(" " + lat);
- return lat;
- }
- }
-
- private static double wrapLon(double lon) {
- //System.out.println("wrapLon " + lon);
- if (lon > 180) {
- //System.out.println(" " + (lon - 360));
- return lon - 360;
- } else if (lon < -180) {
- //System.out.println(" " + (lon + 360));
- return lon + 360;
- } else {
- //System.out.println(" " + lon);
- return lon;
- }
- }
-
- private static void drawRectApproximatelyOnEarthSurface(String name, String color, double minLat, double maxLat, double minLon, double maxLon) {
- int steps = 20;
- System.out.println(" var " + name + " = WE.polygon([");
- System.out.println(" // min -> max lat, min lon");
- for(int i=0;i<steps;i++) {
- System.out.println(" [" + (minLat + (maxLat - minLat) * i / steps) + ", " + minLon + "],");
- }
- System.out.println(" // max lat, min -> max lon");
- for(int i=0;i<steps;i++) {
- System.out.println(" [" + (maxLat + ", " + (minLon + (maxLon - minLon) * i / steps)) + "],");
- }
- System.out.println(" // max -> min lat, max lon");
- for(int i=0;i<steps;i++) {
- System.out.println(" [" + (minLat + (maxLat - minLat) * (steps-i) / steps) + ", " + maxLon + "],");
- }
- System.out.println(" // min lat, max -> min lon");
- for(int i=0;i<steps;i++) {
- System.out.println(" [" + minLat + ", " + (minLon + (maxLon - minLon) * (steps-i) / steps) + "],");
- }
- System.out.println(" // min lat, min lon");
- System.out.println(" [" + minLat + ", " + minLon + "]");
- System.out.println(" ], {color: \"" + color + "\", fillColor: \"" + color + "\"});");
- System.out.println(" " + name + ".addTo(earth);");
- }
-
- private static void plotLatApproximatelyOnEarthSurface(String name, String color, double lat, double minLon, double maxLon) {
- System.out.println(" var " + name + " = WE.polygon([");
- double lon;
- for(lon = minLon;lon<=maxLon;lon += (maxLon-minLon)/36) {
- System.out.println(" [" + lat + ", " + lon + "],");
- }
- System.out.println(" [" + lat + ", " + maxLon + "],");
- lon -= (maxLon-minLon)/36;
- for(;lon>=minLon;lon -= (maxLon-minLon)/36) {
- System.out.println(" [" + lat + ", " + lon + "],");
- }
- System.out.println(" ], {color: \"" + color + "\", fillColor: \"#ffffff\", opacity: " + (color.equals("#ffffff") ? "0.3" : "1") + ", fillOpacity: 0.0001});");
- System.out.println(" " + name + ".addTo(earth);");
- }
-
- private static void plotLonApproximatelyOnEarthSurface(String name, String color, double lon, double minLat, double maxLat) {
- System.out.println(" var " + name + " = WE.polygon([");
- double lat;
- for(lat = minLat;lat<=maxLat;lat += (maxLat-minLat)/36) {
- System.out.println(" [" + lat + ", " + lon + "],");
- }
- System.out.println(" [" + maxLat + ", " + lon + "],");
- lat -= (maxLat-minLat)/36;
- for(;lat>=minLat;lat -= (maxLat-minLat)/36) {
- System.out.println(" [" + lat + ", " + lon + "],");
- }
- System.out.println(" ], {color: \"" + color + "\", fillColor: \"#ffffff\", opacity: " + (color.equals("#ffffff") ? "0.3" : "1") + ", fillOpacity: 0.0001});");
- System.out.println(" " + name + ".addTo(earth);");
- }
-
- // http://www.webglearth.org has API details:
- public static void polysToWebGLEarth(List<double[][]> polys) {
- System.out.println("<!DOCTYPE HTML>");
- System.out.println("<html>");
- System.out.println(" <head>");
- System.out.println(" <script src=\"http://www.webglearth.com/v2/api.js\"></script>");
- System.out.println(" <script>");
- System.out.println(" function initialize() {");
- System.out.println(" var earth = new WE.map('earth_div');");
-
- int count = 0;
- for (double[][] poly : polys) {
- System.out.println(" var poly" + count + " = WE.polygon([");
- for(int i=0;i<poly[0].length;i++) {
- double lat = poly[0][i];
- double lon = poly[1][i];
- System.out.println(" [" + lat + ", " + lon + "],");
- }
- System.out.println(" ], {color: '#00ff00'});");
- System.out.println(" poly" + count + ".addTo(earth);");
- }
-
- System.out.println(" WE.tileLayer('http://{s}.tile.openstreetmap.org/{z}/{x}/{y}.png',{");
- System.out.println(" attribution: '© OpenStreetMap contributors'");
- System.out.println(" }).addTo(earth);");
- System.out.println(" }");
- System.out.println(" </script>");
- System.out.println(" <style>");
- System.out.println(" html, body{padding: 0; margin: 0;}");
- System.out.println(" #earth_div{top: 0; right: 0; bottom: 0; left: 0; position: absolute !important;}");
- System.out.println(" </style>");
- System.out.println(" <title>WebGL Earth API: Hello World</title>");
- System.out.println(" </head>");
- System.out.println(" <body onload=\"initialize()\">");
- System.out.println(" <div id=\"earth_div\"></div>");
- System.out.println(" </body>");
- System.out.println("</html>");
- }
-
- // http://www.webglearth.org has API details:
- public static void toWebGLEarth(double rectMinLatitude, double rectMaxLatitude,
- double rectMinLongitude, double rectMaxLongitude,
- double centerLatitude, double centerLongitude,
- double radiusMeters) {
- GeoRect box = GeoRect.fromPointDistance(centerLatitude, centerLongitude, radiusMeters);
- System.out.println("<!DOCTYPE HTML>");
- System.out.println("<html>");
- System.out.println(" <head>");
- System.out.println(" <script src=\"http://www.webglearth.com/v2/api.js\"></script>");
- System.out.println(" <script>");
- System.out.println(" function initialize() {");
- System.out.println(" var earth = new WE.map('earth_div', {center: [" + centerLatitude + ", " + centerLongitude + "]});");
- System.out.println(" var marker = WE.marker([" + centerLatitude + ", " + centerLongitude + "]).addTo(earth);");
- drawRectApproximatelyOnEarthSurface("cell", "#ff0000", rectMinLatitude, rectMaxLatitude, rectMinLongitude, rectMaxLongitude);
- System.out.println(" var polygonB = WE.polygon([");
- StringBuilder b = new StringBuilder();
- inverseHaversin(b, centerLatitude, centerLongitude, radiusMeters);
- System.out.println(b);
- System.out.println(" ], {color: '#00ff00'});");
- System.out.println(" polygonB.addTo(earth);");
- drawRectApproximatelyOnEarthSurface("bbox", "#00ff00", box.minLat, box.maxLat, box.minLon, box.maxLon);
- System.out.println(" WE.tileLayer('http://{s}.tile.openstreetmap.org/{z}/{x}/{y}.png',{");
- System.out.println(" attribution: '© OpenStreetMap contributors'");
- System.out.println(" }).addTo(earth);");
- plotLatApproximatelyOnEarthSurface("lat0", "#ffffff", 4.68, 0.0, 360.0);
- plotLatApproximatelyOnEarthSurface("lat1", "#ffffff", 180-93.09, 0.0, 360.0);
- plotLatApproximatelyOnEarthSurface("axisLat", "#00ff00", GeoRect.axisLat(centerLatitude, radiusMeters), box.minLon, box.maxLon);
- plotLonApproximatelyOnEarthSurface("axisLon", "#00ff00", centerLongitude, box.minLat, box.maxLat);
- System.out.println(" }");
- System.out.println(" </script>");
- System.out.println(" <style>");
- System.out.println(" html, body{padding: 0; margin: 0;}");
- System.out.println(" #earth_div{top: 0; right: 0; bottom: 0; left: 0; position: absolute !important;}");
- System.out.println(" </style>");
- System.out.println(" <title>WebGL Earth API: Hello World</title>");
- System.out.println(" </head>");
- System.out.println(" <body onload=\"initialize()\">");
- System.out.println(" <div id=\"earth_div\"></div>");
- System.out.println(" </body>");
- System.out.println("</html>");
- }
-
- private static void inverseHaversin(StringBuilder b, double centerLat, double centerLon, double radiusMeters) {
- double angle = 0;
- int steps = 100;
-
- newAngle:
- while (angle < 360) {
- double x = Math.cos(Math.toRadians(angle));
- double y = Math.sin(Math.toRadians(angle));
- double factor = 2.0;
- double step = 1.0;
- int last = 0;
- double lastDistanceMeters = 0.0;
- //System.out.println("angle " + angle + " slope=" + slope);
- while (true) {
- double lat = wrapLat(centerLat + y * factor);
- double lon = wrapLon(centerLon + x * factor);
- double distanceMeters = SloppyMath.haversinMeters(centerLat, centerLon, lat, lon);
-
- if (last == 1 && distanceMeters < lastDistanceMeters) {
- // For large enough circles, some angles are not possible:
- //System.out.println(" done: give up on angle " + angle);
- angle += 360./steps;
- continue newAngle;
- }
- if (last == -1 && distanceMeters > lastDistanceMeters) {
- // For large enough circles, some angles are not possible:
- //System.out.println(" done: give up on angle " + angle);
- angle += 360./steps;
- continue newAngle;
- }
- lastDistanceMeters = distanceMeters;
-
- //System.out.println(" iter lat=" + lat + " lon=" + lon + " distance=" + distanceMeters + " vs " + radiusMeters);
- if (Math.abs(distanceMeters - radiusMeters) < 0.1) {
- b.append(" [" + lat + ", " + lon + "],\n");
- break;
- }
- if (distanceMeters > radiusMeters) {
- // too big
- //System.out.println(" smaller");
- factor -= step;
- if (last == 1) {
- //System.out.println(" half-step");
- step /= 2.0;
- }
- last = -1;
- } else if (distanceMeters < radiusMeters) {
- // too small
- //System.out.println(" bigger");
- factor += step;
- if (last == -1) {
- //System.out.println(" half-step");
- step /= 2.0;
- }
- last = 1;
- }
- }
- angle += 360./steps;
- }
- }
-}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6c219e99/lucene/spatial/src/test/org/apache/lucene/spatial/util/TestGeoEncodingUtils.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/test/org/apache/lucene/spatial/util/TestGeoEncodingUtils.java b/lucene/spatial/src/test/org/apache/lucene/spatial/util/TestGeoEncodingUtils.java
new file mode 100644
index 0000000..1a1b2cc
--- /dev/null
+++ b/lucene/spatial/src/test/org/apache/lucene/spatial/util/TestGeoEncodingUtils.java
@@ -0,0 +1,101 @@
+package org.apache.lucene.spatial.util;
+
+/*
+ * 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.
+ */
+
+import org.apache.lucene.util.BytesRefBuilder;
+import org.apache.lucene.util.LuceneTestCase;
+
+import static org.apache.lucene.geo.GeoTestUtil.nextLatitude;
+import static org.apache.lucene.geo.GeoTestUtil.nextLongitude;
+
+/**
+ * Tests methods in {@link GeoEncodingUtils}
+ */
+public class TestGeoEncodingUtils extends LuceneTestCase {
+ /**
+ * Tests stability of {@link GeoEncodingUtils#geoCodedToPrefixCoded}
+ */
+ public void testGeoPrefixCoding() throws Exception {
+ int numIters = atLeast(1000);
+ long hash;
+ long decodedHash;
+ BytesRefBuilder brb = new BytesRefBuilder();
+ while (numIters-- >= 0) {
+ hash = GeoEncodingUtils.mortonHash(nextLatitude(), nextLongitude());
+ for (int i=32; i<64; ++i) {
+ GeoEncodingUtils.geoCodedToPrefixCoded(hash, i, brb);
+ decodedHash = GeoEncodingUtils.prefixCodedToGeoCoded(brb.get());
+ assertEquals((hash >>> i) << i, decodedHash);
+ }
+ }
+ }
+
+ public void testMortonEncoding() throws Exception {
+ long hash = GeoEncodingUtils.mortonHash(90, 180);
+ assertEquals(180.0, GeoEncodingUtils.mortonUnhashLon(hash), 0);
+ assertEquals(90.0, GeoEncodingUtils.mortonUnhashLat(hash), 0);
+ }
+
+ public void testEncodeDecode() throws Exception {
+ int iters = atLeast(10000);
+ for(int iter=0;iter<iters;iter++) {
+ double lat = nextLatitude();
+ double lon = nextLongitude();
+
+ long enc = GeoEncodingUtils.mortonHash(lat, lon);
+ double latEnc = GeoEncodingUtils.mortonUnhashLat(enc);
+ double lonEnc = GeoEncodingUtils.mortonUnhashLon(enc);
+
+ assertEquals("lat=" + lat + " latEnc=" + latEnc + " diff=" + (lat - latEnc), lat, latEnc, GeoEncodingUtils.TOLERANCE);
+ assertEquals("lon=" + lon + " lonEnc=" + lonEnc + " diff=" + (lon - lonEnc), lon, lonEnc, GeoEncodingUtils.TOLERANCE);
+ }
+ }
+
+ /** make sure values always go down: this is important for edge case consistency */
+ public void testEncodeDecodeRoundsDown() throws Exception {
+ int iters = atLeast(1000);
+ for(int iter=0;iter<iters;iter++) {
+ double lat = -90 + 180.0 * random().nextDouble();
+ double lon = -180 + 360.0 * random().nextDouble();
+
+ long enc = GeoEncodingUtils.mortonHash(lat, lon);
+ double latEnc = GeoEncodingUtils.mortonUnhashLat(enc);
+ double lonEnc = GeoEncodingUtils.mortonUnhashLon(enc);
+ assertTrue(latEnc <= lat);
+ assertTrue(lonEnc <= lon);
+ }
+ }
+
+ public void testScaleUnscaleIsStable() throws Exception {
+ int iters = atLeast(1000);
+ for(int iter=0;iter<iters;iter++) {
+ double lat = nextLatitude();
+ double lon = nextLongitude();
+
+ long enc = GeoEncodingUtils.mortonHash(lat, lon);
+ double latEnc = GeoEncodingUtils.mortonUnhashLat(enc);
+ double lonEnc = GeoEncodingUtils.mortonUnhashLon(enc);
+
+ long enc2 = GeoEncodingUtils.mortonHash(lat, lon);
+ double latEnc2 = GeoEncodingUtils.mortonUnhashLat(enc2);
+ double lonEnc2 = GeoEncodingUtils.mortonUnhashLon(enc2);
+ assertEquals(latEnc, latEnc2, 0.0);
+ assertEquals(lonEnc, lonEnc2, 0.0);
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6c219e99/lucene/spatial/src/test/org/apache/lucene/spatial/util/TestGeoUtils.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/test/org/apache/lucene/spatial/util/TestGeoUtils.java b/lucene/spatial/src/test/org/apache/lucene/spatial/util/TestGeoUtils.java
deleted file mode 100644
index 28b885a..0000000
--- a/lucene/spatial/src/test/org/apache/lucene/spatial/util/TestGeoUtils.java
+++ /dev/null
@@ -1,399 +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.Locale;
-
-import org.apache.lucene.geo.GeoUtils;
-import org.apache.lucene.util.BytesRefBuilder;
-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;
- }
-
- /**
- * Tests stability of {@link GeoEncodingUtils#geoCodedToPrefixCoded}
- */
- public void testGeoPrefixCoding() throws Exception {
- int numIters = atLeast(1000);
- long hash;
- long decodedHash;
- BytesRefBuilder brb = new BytesRefBuilder();
- while (numIters-- >= 0) {
- hash = GeoEncodingUtils.mortonHash(randomLat(false), randomLon(false));
- for (int i=32; i<64; ++i) {
- GeoEncodingUtils.geoCodedToPrefixCoded(hash, i, brb);
- decodedHash = GeoEncodingUtils.prefixCodedToGeoCoded(brb.get());
- assertEquals((hash >>> i) << i, decodedHash);
- }
- }
- }
-
- public void testMortonEncoding() throws Exception {
- long hash = GeoEncodingUtils.mortonHash(90, 180);
- assertEquals(180.0, GeoEncodingUtils.mortonUnhashLon(hash), 0);
- assertEquals(90.0, GeoEncodingUtils.mortonUnhashLat(hash), 0);
- }
-
- public void testEncodeDecode() throws Exception {
- int iters = atLeast(10000);
- boolean small = random().nextBoolean();
- for(int iter=0;iter<iters;iter++) {
- double lat = randomLat(small);
- double lon = randomLon(small);
-
- long enc = GeoEncodingUtils.mortonHash(lat, lon);
- double latEnc = GeoEncodingUtils.mortonUnhashLat(enc);
- double lonEnc = GeoEncodingUtils.mortonUnhashLon(enc);
-
- assertEquals("lat=" + lat + " latEnc=" + latEnc + " diff=" + (lat - latEnc), lat, latEnc, GeoEncodingUtils.TOLERANCE);
- assertEquals("lon=" + lon + " lonEnc=" + lonEnc + " diff=" + (lon - lonEnc), lon, lonEnc, GeoEncodingUtils.TOLERANCE);
- }
- }
-
- public void testScaleUnscaleIsStable() throws Exception {
- int iters = atLeast(1000);
- boolean small = random().nextBoolean();
- for(int iter=0;iter<iters;iter++) {
- double lat = randomLat(small);
- double lon = randomLon(small);
-
- long enc = GeoEncodingUtils.mortonHash(lat, lon);
- double latEnc = GeoEncodingUtils.mortonUnhashLat(enc);
- double lonEnc = GeoEncodingUtils.mortonUnhashLon(enc);
-
- long enc2 = GeoEncodingUtils.mortonHash(lat, lon);
- double latEnc2 = GeoEncodingUtils.mortonUnhashLat(enc2);
- double lonEnc2 = GeoEncodingUtils.mortonUnhashLon(enc2);
- assertEquals(latEnc, latEnc2, 0.0);
- assertEquals(lonEnc, lonEnc2, 0.0);
- }
- }
-
- // 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?
-
- GeoRect bbox = GeoRect.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();
- GeoRect box = GeoRect.fromPointDistance(lat, lon, radius);
- final GeoRect box1;
- final GeoRect box2;
- if (box.crossesDateline()) {
- box1 = new GeoRect(box.minLat, box.maxLat, -180, box.maxLon);
- box2 = new GeoRect(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();
- GeoRect box = GeoRect.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();
- GeoRect rect = GeoRect.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, GeoRect.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 = GeoRect.axisLat(0.0D, radius);
- for (double lat = 0.1D; lat < 90D; lat += 0.1D) {
- double nextAxisLat = GeoRect.axisLat(lat, radius);
- GeoRect bbox = GeoRect.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 = GeoRect.axisLat(-0.0D, radius);
- for (double lat = -0.1D; lat > -90D; lat -= 0.1D) {
- double nextAxisLat = GeoRect.axisLat(lat, radius);
- GeoRect bbox = GeoRect.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 GeoRect box = GeoRect.fromPointDistance(centerLat, centerLon, radius);
- // TODO: remove this leniency!
- if (box.crossesDateline()) {
- --i; // try again...
- continue;
- }
- final double axisLat = GeoRect.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, GeoRect.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+GeoRect.AXISLAT_ERROR < latMin || axisLat-GeoRect.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/spatial/src/test/org/apache/lucene/spatial/util/TestPolygon.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/test/org/apache/lucene/spatial/util/TestPolygon.java b/lucene/spatial/src/test/org/apache/lucene/spatial/util/TestPolygon.java
index 4ccd8d4..259aada 100644
--- a/lucene/spatial/src/test/org/apache/lucene/spatial/util/TestPolygon.java
+++ b/lucene/spatial/src/test/org/apache/lucene/spatial/util/TestPolygon.java
@@ -16,8 +16,15 @@
*/
package org.apache.lucene.spatial.util;
+import org.apache.lucene.geo.Polygon;
import org.apache.lucene.util.LuceneTestCase;
+import static org.apache.lucene.geo.GeoTestUtil.nextLatitude;
+import static org.apache.lucene.geo.GeoTestUtil.nextLatitudeAround;
+import static org.apache.lucene.geo.GeoTestUtil.nextLongitude;
+import static org.apache.lucene.geo.GeoTestUtil.nextLongitudeAround;
+import static org.apache.lucene.geo.GeoTestUtil.nextPolygon;
+
public class TestPolygon extends LuceneTestCase {
/** null polyLats not allowed */
@@ -109,11 +116,11 @@ public class TestPolygon extends LuceneTestCase {
public void testBoundingBox() throws Exception {
for (int i = 0; i < 100; i++) {
- Polygon polygon = GeoTestUtil.nextPolygon();
+ Polygon polygon = nextPolygon();
for (int j = 0; j < 100; j++) {
- double latitude = GeoTestUtil.nextLatitude();
- double longitude = GeoTestUtil.nextLongitude();
+ double latitude = nextLatitude();
+ double longitude = nextLongitude();
// if the point is within poly, then it should be in our bounding box
if (polygon.contains(latitude, longitude)) {
assertTrue(latitude >= polygon.minLat && latitude <= polygon.maxLat);
@@ -125,11 +132,11 @@ public class TestPolygon extends LuceneTestCase {
public void testBoundingBoxEdgeCases() throws Exception {
for (int i = 0; i < 100; i++) {
- Polygon polygon = GeoTestUtil.nextPolygon();
+ Polygon polygon = nextPolygon();
for (int j = 0; j < 100; j++) {
- double latitude = GeoTestUtil.nextLatitudeAround(polygon.minLat, polygon.maxLat);
- double longitude = GeoTestUtil.nextLongitudeAround(polygon.minLon, polygon.maxLon);
+ double latitude = nextLatitudeAround(polygon.minLat, polygon.maxLat);
+ double longitude = nextLongitudeAround(polygon.minLon, polygon.maxLon);
// if the point is within poly, then it should be in our bounding box
if (polygon.contains(latitude, longitude)) {
assertTrue(latitude >= polygon.minLat && latitude <= polygon.maxLat);
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6c219e99/lucene/test-framework/src/java/org/apache/lucene/geo/GeoTestUtil.java
----------------------------------------------------------------------
diff --git a/lucene/test-framework/src/java/org/apache/lucene/geo/GeoTestUtil.java b/lucene/test-framework/src/java/org/apache/lucene/geo/GeoTestUtil.java
new file mode 100644
index 0000000..bcb473e
--- /dev/null
+++ b/lucene/test-framework/src/java/org/apache/lucene/geo/GeoTestUtil.java
@@ -0,0 +1,499 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.geo;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Random;
+
+import org.apache.lucene.util.SloppyMath;
+
+import com.carrotsearch.randomizedtesting.RandomizedContext;
+
+/** static methods for testing geo */
+public class GeoTestUtil {
+
+ /** returns next pseudorandom latitude (anywhere) */
+ public static double nextLatitude() {
+ return -90 + 180.0 * random().nextDouble();
+ }
+
+ /** returns next pseudorandom longitude (anywhere) */
+ public static double nextLongitude() {
+ return -180 + 360.0 * random().nextDouble();
+ }
+
+ /** returns next pseudorandom latitude, kinda close to {@code otherLatitude} */
+ public static double nextLatitudeNear(double otherLatitude) {
+ GeoUtils.checkLatitude(otherLatitude);
+ return normalizeLatitude(otherLatitude + random().nextDouble() - 0.5);
+ }
+
+ /** returns next pseudorandom longitude, kinda close to {@code otherLongitude} */
+ public static double nextLongitudeNear(double otherLongitude) {
+ GeoUtils.checkLongitude(otherLongitude);
+ return normalizeLongitude(otherLongitude + random().nextDouble() - 0.5);
+ }
+
+ /**
+ * returns next pseudorandom latitude, kinda close to {@code minLatitude/maxLatitude}
+ * <b>NOTE:</b>minLatitude/maxLatitude are merely guidelines. the returned value is sometimes
+ * outside of that range! this is to facilitate edge testing.
+ */
+ public static double nextLatitudeAround(double minLatitude, double maxLatitude) {
+ GeoUtils.checkLatitude(minLatitude);
+ GeoUtils.checkLatitude(maxLatitude);
+ return normalizeLatitude(randomRangeMaybeSlightlyOutside(minLatitude, maxLatitude));
+ }
+
+ /**
+ * returns next pseudorandom longitude, kinda close to {@code minLongitude/maxLongitude}
+ * <b>NOTE:</b>minLongitude/maxLongitude are merely guidelines. the returned value is sometimes
+ * outside of that range! this is to facilitate edge testing.
+ */
+ public static double nextLongitudeAround(double minLongitude, double maxLongitude) {
+ GeoUtils.checkLongitude(minLongitude);
+ GeoUtils.checkLongitude(maxLongitude);
+ return normalizeLongitude(randomRangeMaybeSlightlyOutside(minLongitude, maxLongitude));
+ }
+
+ /** returns next pseudorandom box: can cross the 180th meridian */
+ public static Rectangle nextBox() {
+ return nextBoxInternal(nextLatitude(), nextLatitude(), nextLongitude(), nextLongitude(), true);
+ }
+
+ /** returns next pseudorandom box, can cross the 180th meridian, kinda close to {@code otherLatitude} and {@code otherLongitude} */
+ public static Rectangle nextBoxNear(double otherLatitude, double otherLongitude) {
+ GeoUtils.checkLongitude(otherLongitude);
+ GeoUtils.checkLongitude(otherLongitude);
+ return nextBoxInternal(nextLatitudeNear(otherLatitude), nextLatitudeNear(otherLatitude),
+ nextLongitudeNear(otherLongitude), nextLongitudeNear(otherLongitude), true);
+ }
+
+ /** returns next pseudorandom polygon */
+ public static Polygon nextPolygon() {
+ if (random().nextBoolean()) {
+ return surpriseMePolygon(null, null);
+ }
+
+ Rectangle box = nextBoxInternal(nextLatitude(), nextLatitude(), nextLongitude(), nextLongitude(), false);
+ if (random().nextBoolean()) {
+ // box
+ return boxPolygon(box);
+ } else {
+ // triangle
+ return trianglePolygon(box);
+ }
+ }
+
+ /** returns next pseudorandom polygon, kinda close to {@code otherLatitude} and {@code otherLongitude} */
+ public static Polygon nextPolygonNear(double otherLatitude, double otherLongitude) {
+ if (random().nextBoolean()) {
+ return surpriseMePolygon(otherLatitude, otherLongitude);
+ }
+
+ Rectangle box = nextBoxInternal(nextLatitudeNear(otherLatitude), nextLatitudeNear(otherLatitude),
+ nextLongitudeNear(otherLongitude), nextLongitudeNear(otherLongitude), false);
+ if (random().nextBoolean()) {
+ // box
+ return boxPolygon(box);
+ } else {
+ // triangle
+ return trianglePolygon(box);
+ }
+ }
+
+ private static Rectangle nextBoxInternal(double lat0, double lat1, double lon0, double lon1, boolean canCrossDateLine) {
+ if (lat1 < lat0) {
+ double x = lat0;
+ lat0 = lat1;
+ lat1 = x;
+ }
+
+ if (canCrossDateLine == false && lon1 < lon0) {
+ double x = lon0;
+ lon0 = lon1;
+ lon1 = x;
+ }
+
+ return new Rectangle(lat0, lat1, lon0, lon1);
+ }
+
+ private static Polygon boxPolygon(Rectangle box) {
+ assert box.crossesDateline() == false;
+ final double[] polyLats = new double[5];
+ final double[] polyLons = new double[5];
+ polyLats[0] = box.minLat;
+ polyLons[0] = box.minLon;
+ polyLats[1] = box.maxLat;
+ polyLons[1] = box.minLon;
+ polyLats[2] = box.maxLat;
+ polyLons[2] = box.maxLon;
+ polyLats[3] = box.minLat;
+ polyLons[3] = box.maxLon;
+ polyLats[4] = box.minLat;
+ polyLons[4] = box.minLon;
+ return new Polygon(polyLats, polyLons);
+ }
+
+ private static Polygon trianglePolygon(Rectangle box) {
+ assert box.crossesDateline() == false;
+ final double[] polyLats = new double[4];
+ final double[] polyLons = new double[4];
+ polyLats[0] = box.minLat;
+ polyLons[0] = box.minLon;
+ polyLats[1] = box.maxLat;
+ polyLons[1] = box.minLon;
+ polyLats[2] = box.maxLat;
+ polyLons[2] = box.maxLon;
+ polyLats[3] = box.minLat;
+ polyLons[3] = box.minLon;
+ return new Polygon(polyLats, polyLons);
+ }
+
+ private static Polygon surpriseMePolygon(Double otherLatitude, Double otherLongitude) {
+ // repeat until we get a poly that doesn't cross dateline:
+ newPoly:
+ while (true) {
+ //System.out.println("\nPOLY ITER");
+ final double centerLat;
+ final double centerLon;
+ if (otherLatitude == null) {
+ centerLat = nextLatitude();
+ centerLon = nextLongitude();
+ } else {
+ GeoUtils.checkLatitude(otherLatitude);
+ GeoUtils.checkLongitude(otherLongitude);
+ centerLat = nextLatitudeNear(otherLatitude);
+ centerLon = nextLongitudeNear(otherLongitude);
+ }
+
+ double radius = 0.1 + 20 * random().nextDouble();
+ double radiusDelta = random().nextDouble();
+
+ ArrayList<Double> lats = new ArrayList<>();
+ ArrayList<Double> lons = new ArrayList<>();
+ double angle = 0.0;
+ while (true) {
+ angle += random().nextDouble()*40.0;
+ //System.out.println(" angle " + angle);
+ if (angle > 360) {
+ break;
+ }
+ double len = radius * (1.0 - radiusDelta + radiusDelta * random().nextDouble());
+ //System.out.println(" len=" + len);
+ double lat = centerLat + len * Math.cos(Math.toRadians(angle));
+ double lon = centerLon + len * Math.sin(Math.toRadians(angle));
+ if (lon <= GeoUtils.MIN_LON_INCL || lon >= GeoUtils.MAX_LON_INCL) {
+ // cannot cross dateline: try again!
+ continue newPoly;
+ }
+ if (lat > 90) {
+ // cross the north pole
+ lat = 180 - lat;
+ lon = 180 - lon;
+ } else if (lat < -90) {
+ // cross the south pole
+ lat = -180 - lat;
+ lon = 180 - lon;
+ }
+ if (lon <= GeoUtils.MIN_LON_INCL || lon >= GeoUtils.MAX_LON_INCL) {
+ // cannot cross dateline: try again!
+ continue newPoly;
+ }
+ lats.add(lat);
+ lons.add(lon);
+
+ //System.out.println(" lat=" + lats.get(lats.size()-1) + " lon=" + lons.get(lons.size()-1));
+ }
+
+ // close it
+ lats.add(lats.get(0));
+ lons.add(lons.get(0));
+
+ double[] latsArray = new double[lats.size()];
+ double[] lonsArray = new double[lons.size()];
+ for(int i=0;i<lats.size();i++) {
+ latsArray[i] = lats.get(i);
+ lonsArray[i] = lons.get(i);
+ }
+ return new Polygon(latsArray, lonsArray);
+ }
+ }
+
+ /** Returns random double min to max or up to 1% outside of that range */
+ private static double randomRangeMaybeSlightlyOutside(double min, double max) {
+ return min + (random().nextDouble() + (0.5 - random().nextDouble()) * .02) * (max - min);
+ }
+
+ /** Puts latitude in range of -90 to 90. */
+ private static double normalizeLatitude(double latitude) {
+ if (latitude >= -90 && latitude <= 90) {
+ return latitude; //common case, and avoids slight double precision shifting
+ }
+ double off = Math.abs((latitude + 90) % 360);
+ return (off <= 180 ? off : 360-off) - 90;
+ }
+
+ /** Puts longitude in range of -180 to +180. */
+ private static double normalizeLongitude(double longitude) {
+ if (longitude >= -180 && longitude <= 180) {
+ return longitude; //common case, and avoids slight double precision shifting
+ }
+ double off = (longitude + 180) % 360;
+ if (off < 0) {
+ return 180 + off;
+ } else if (off == 0 && longitude > 0) {
+ return 180;
+ } else {
+ return -180 + off;
+ }
+ }
+
+ /** Keep it simple, we don't need to take arbitrary Random for geo tests */
+ private static Random random() {
+ return RandomizedContext.current().getRandom();
+ }
+
+ // craziness for plotting stuff :)
+
+ private static double wrapLat(double lat) {
+ //System.out.println("wrapLat " + lat);
+ if (lat > 90) {
+ //System.out.println(" " + (180 - lat));
+ return 180 - lat;
+ } else if (lat < -90) {
+ //System.out.println(" " + (-180 - lat));
+ return -180 - lat;
+ } else {
+ //System.out.println(" " + lat);
+ return lat;
+ }
+ }
+
+ private static double wrapLon(double lon) {
+ //System.out.println("wrapLon " + lon);
+ if (lon > 180) {
+ //System.out.println(" " + (lon - 360));
+ return lon - 360;
+ } else if (lon < -180) {
+ //System.out.println(" " + (lon + 360));
+ return lon + 360;
+ } else {
+ //System.out.println(" " + lon);
+ return lon;
+ }
+ }
+
+ private static void drawRectApproximatelyOnEarthSurface(String name, String color, double minLat, double maxLat, double minLon, double maxLon) {
+ int steps = 20;
+ System.out.println(" var " + name + " = WE.polygon([");
+ System.out.println(" // min -> max lat, min lon");
+ for(int i=0;i<steps;i++) {
+ System.out.println(" [" + (minLat + (maxLat - minLat) * i / steps) + ", " + minLon + "],");
+ }
+ System.out.println(" // max lat, min -> max lon");
+ for(int i=0;i<steps;i++) {
+ System.out.println(" [" + (maxLat + ", " + (minLon + (maxLon - minLon) * i / steps)) + "],");
+ }
+ System.out.println(" // max -> min lat, max lon");
+ for(int i=0;i<steps;i++) {
+ System.out.println(" [" + (minLat + (maxLat - minLat) * (steps-i) / steps) + ", " + maxLon + "],");
+ }
+ System.out.println(" // min lat, max -> min lon");
+ for(int i=0;i<steps;i++) {
+ System.out.println(" [" + minLat + ", " + (minLon + (maxLon - minLon) * (steps-i) / steps) + "],");
+ }
+ System.out.println(" // min lat, min lon");
+ System.out.println(" [" + minLat + ", " + minLon + "]");
+ System.out.println(" ], {color: \"" + color + "\", fillColor: \"" + color + "\"});");
+ System.out.println(" " + name + ".addTo(earth);");
+ }
+
+ private static void plotLatApproximatelyOnEarthSurface(String name, String color, double lat, double minLon, double maxLon) {
+ System.out.println(" var " + name + " = WE.polygon([");
+ double lon;
+ for(lon = minLon;lon<=maxLon;lon += (maxLon-minLon)/36) {
+ System.out.println(" [" + lat + ", " + lon + "],");
+ }
+ System.out.println(" [" + lat + ", " + maxLon + "],");
+ lon -= (maxLon-minLon)/36;
+ for(;lon>=minLon;lon -= (maxLon-minLon)/36) {
+ System.out.println(" [" + lat + ", " + lon + "],");
+ }
+ System.out.println(" ], {color: \"" + color + "\", fillColor: \"#ffffff\", opacity: " + (color.equals("#ffffff") ? "0.3" : "1") + ", fillOpacity: 0.0001});");
+ System.out.println(" " + name + ".addTo(earth);");
+ }
+
+ private static void plotLonApproximatelyOnEarthSurface(String name, String color, double lon, double minLat, double maxLat) {
+ System.out.println(" var " + name + " = WE.polygon([");
+ double lat;
+ for(lat = minLat;lat<=maxLat;lat += (maxLat-minLat)/36) {
+ System.out.println(" [" + lat + ", " + lon + "],");
+ }
+ System.out.println(" [" + maxLat + ", " + lon + "],");
+ lat -= (maxLat-minLat)/36;
+ for(;lat>=minLat;lat -= (maxLat-minLat)/36) {
+ System.out.println(" [" + lat + ", " + lon + "],");
+ }
+ System.out.println(" ], {color: \"" + color + "\", fillColor: \"#ffffff\", opacity: " + (color.equals("#ffffff") ? "0.3" : "1") + ", fillOpacity: 0.0001});");
+ System.out.println(" " + name + ".addTo(earth);");
+ }
+
+ // http://www.webglearth.org has API details:
+ public static void polysToWebGLEarth(List<double[][]> polys) {
+ System.out.println("<!DOCTYPE HTML>");
+ System.out.println("<html>");
+ System.out.println(" <head>");
+ System.out.println(" <script src=\"http://www.webglearth.com/v2/api.js\"></script>");
+ System.out.println(" <script>");
+ System.out.println(" function initialize() {");
+ System.out.println(" var earth = new WE.map('earth_div');");
+
+ int count = 0;
+ for (double[][] poly : polys) {
+ System.out.println(" var poly" + count + " = WE.polygon([");
+ for(int i=0;i<poly[0].length;i++) {
+ double lat = poly[0][i];
+ double lon = poly[1][i];
+ System.out.println(" [" + lat + ", " + lon + "],");
+ }
+ System.out.println(" ], {color: '#00ff00'});");
+ System.out.println(" poly" + count + ".addTo(earth);");
+ }
+
+ System.out.println(" WE.tileLayer('http://{s}.tile.openstreetmap.org/{z}/{x}/{y}.png',{");
+ System.out.println(" attribution: '© OpenStreetMap contributors'");
+ System.out.println(" }).addTo(earth);");
+ System.out.println(" }");
+ System.out.println(" </script>");
+ System.out.println(" <style>");
+ System.out.println(" html, body{padding: 0; margin: 0;}");
+ System.out.println(" #earth_div{top: 0; right: 0; bottom: 0; left: 0; position: absolute !important;}");
+ System.out.println(" </style>");
+ System.out.println(" <title>WebGL Earth API: Hello World</title>");
+ System.out.println(" </head>");
+ System.out.println(" <body onload=\"initialize()\">");
+ System.out.println(" <div id=\"earth_div\"></div>");
+ System.out.println(" </body>");
+ System.out.println("</html>");
+ }
+
+ // http://www.webglearth.org has API details:
+ public static void toWebGLEarth(double rectMinLatitude, double rectMaxLatitude,
+ double rectMinLongitude, double rectMaxLongitude,
+ double centerLatitude, double centerLongitude,
+ double radiusMeters) {
+ Rectangle box = Rectangle.fromPointDistance(centerLatitude, centerLongitude, radiusMeters);
+ System.out.println("<!DOCTYPE HTML>");
+ System.out.println("<html>");
+ System.out.println(" <head>");
+ System.out.println(" <script src=\"http://www.webglearth.com/v2/api.js\"></script>");
+ System.out.println(" <script>");
+ System.out.println(" function initialize() {");
+ System.out.println(" var earth = new WE.map('earth_div', {center: [" + centerLatitude + ", " + centerLongitude + "]});");
+ System.out.println(" var marker = WE.marker([" + centerLatitude + ", " + centerLongitude + "]).addTo(earth);");
+ drawRectApproximatelyOnEarthSurface("cell", "#ff0000", rectMinLatitude, rectMaxLatitude, rectMinLongitude, rectMaxLongitude);
+ System.out.println(" var polygonB = WE.polygon([");
+ StringBuilder b = new StringBuilder();
+ inverseHaversin(b, centerLatitude, centerLongitude, radiusMeters);
+ System.out.println(b);
+ System.out.println(" ], {color: '#00ff00'});");
+ System.out.println(" polygonB.addTo(earth);");
+ drawRectApproximatelyOnEarthSurface("bbox", "#00ff00", box.minLat, box.maxLat, box.minLon, box.maxLon);
+ System.out.println(" WE.tileLayer('http://{s}.tile.openstreetmap.org/{z}/{x}/{y}.png',{");
+ System.out.println(" attribution: '© OpenStreetMap contributors'");
+ System.out.println(" }).addTo(earth);");
+ plotLatApproximatelyOnEarthSurface("lat0", "#ffffff", 4.68, 0.0, 360.0);
+ plotLatApproximatelyOnEarthSurface("lat1", "#ffffff", 180-93.09, 0.0, 360.0);
+ plotLatApproximatelyOnEarthSurface("axisLat", "#00ff00", Rectangle.axisLat(centerLatitude, radiusMeters), box.minLon, box.maxLon);
+ plotLonApproximatelyOnEarthSurface("axisLon", "#00ff00", centerLongitude, box.minLat, box.maxLat);
+ System.out.println(" }");
+ System.out.println(" </script>");
+ System.out.println(" <style>");
+ System.out.println(" html, body{padding: 0; margin: 0;}");
+ System.out.println(" #earth_div{top: 0; right: 0; bottom: 0; left: 0; position: absolute !important;}");
+ System.out.println(" </style>");
+ System.out.println(" <title>WebGL Earth API: Hello World</title>");
+ System.out.println(" </head>");
+ System.out.println(" <body onload=\"initialize()\">");
+ System.out.println(" <div id=\"earth_div\"></div>");
+ System.out.println(" </body>");
+ System.out.println("</html>");
+ }
+
+ private static void inverseHaversin(StringBuilder b, double centerLat, double centerLon, double radiusMeters) {
+ double angle = 0;
+ int steps = 100;
+
+ newAngle:
+ while (angle < 360) {
+ double x = Math.cos(Math.toRadians(angle));
+ double y = Math.sin(Math.toRadians(angle));
+ double factor = 2.0;
+ double step = 1.0;
+ int last = 0;
+ double lastDistanceMeters = 0.0;
+ //System.out.println("angle " + angle + " slope=" + slope);
+ while (true) {
+ double lat = wrapLat(centerLat + y * factor);
+ double lon = wrapLon(centerLon + x * factor);
+ double distanceMeters = SloppyMath.haversinMeters(centerLat, centerLon, lat, lon);
+
+ if (last == 1 && distanceMeters < lastDistanceMeters) {
+ // For large enough circles, some angles are not possible:
+ //System.out.println(" done: give up on angle " + angle);
+ angle += 360./steps;
+ continue newAngle;
+ }
+ if (last == -1 && distanceMeters > lastDistanceMeters) {
+ // For large enough circles, some angles are not possible:
+ //System.out.println(" done: give up on angle " + angle);
+ angle += 360./steps;
+ continue newAngle;
+ }
+ lastDistanceMeters = distanceMeters;
+
+ //System.out.println(" iter lat=" + lat + " lon=" + lon + " distance=" + distanceMeters + " vs " + radiusMeters);
+ if (Math.abs(distanceMeters - radiusMeters) < 0.1) {
+ b.append(" [" + lat + ", " + lon + "],\n");
+ break;
+ }
+ if (distanceMeters > radiusMeters) {
+ // too big
+ //System.out.println(" smaller");
+ factor -= step;
+ if (last == 1) {
+ //System.out.println(" half-step");
+ step /= 2.0;
+ }
+ last = -1;
+ } else if (distanceMeters < radiusMeters) {
+ // too small
+ //System.out.println(" bigger");
+ factor += step;
+ if (last == -1) {
+ //System.out.println(" half-step");
+ step /= 2.0;
+ }
+ last = 1;
+ }
+ }
+ angle += 360./steps;
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6c219e99/lucene/test-framework/src/java/org/apache/lucene/geo/package-info.java
----------------------------------------------------------------------
diff --git a/lucene/test-framework/src/java/org/apache/lucene/geo/package-info.java b/lucene/test-framework/src/java/org/apache/lucene/geo/package-info.java
new file mode 100644
index 0000000..9f0340b
--- /dev/null
+++ b/lucene/test-framework/src/java/org/apache/lucene/geo/package-info.java
@@ -0,0 +1,21 @@
+/*
+ * 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.
+ */
+
+/**
+ * Reusable Geo test utilities.
+ */
+package org.apache.lucene.geo;
\ No newline at end of file
[2/2] lucene-solr:master: LUCENE-7163: refactor GeoRect, Polygon,
and GeoUtils tests to geo package in core.
Posted by nk...@apache.org.
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);