You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by mi...@apache.org on 2015/08/07 22:49:54 UTC
svn commit: r1694748 - in /lucene/dev/branches/branch_5x: ./ lucene/
lucene/CHANGES.txt lucene/sandbox/
lucene/sandbox/src/java/org/apache/lucene/util/GeoHashUtils.java
lucene/sandbox/src/test/org/apache/lucene/util/TestGeoUtils.java
Author: mikemccand
Date: Fri Aug 7 20:49:54 2015
New Revision: 1694748
URL: http://svn.apache.org/r1694748
Log:
LUCENE-6724: add utility APIs to compute neighboring geohash cells
Modified:
lucene/dev/branches/branch_5x/ (props changed)
lucene/dev/branches/branch_5x/lucene/ (props changed)
lucene/dev/branches/branch_5x/lucene/CHANGES.txt (contents, props changed)
lucene/dev/branches/branch_5x/lucene/sandbox/ (props changed)
lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoHashUtils.java
lucene/dev/branches/branch_5x/lucene/sandbox/src/test/org/apache/lucene/util/TestGeoUtils.java
Modified: lucene/dev/branches/branch_5x/lucene/CHANGES.txt
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/CHANGES.txt?rev=1694748&r1=1694747&r2=1694748&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/CHANGES.txt (original)
+++ lucene/dev/branches/branch_5x/lucene/CHANGES.txt Fri Aug 7 20:49:54 2015
@@ -11,6 +11,9 @@ New Features
* LUCENE-6720: New FunctionRangeQuery wrapper around ValueSourceScorer
(returned from ValueSource/FunctionValues.getRangeScorer()). (David Smiley)
+* LUCENE-6724: Add utility APIs to GeoHashUtils to compute neighbor
+ geohash cells (Nick Knize via Mike McCandless).
+
Optimizations
* LUCENE-6708: TopFieldCollector does not compute the score several times on the
Modified: lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoHashUtils.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoHashUtils.java?rev=1694748&r1=1694747&r2=1694748&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoHashUtils.java (original)
+++ lucene/dev/branches/branch_5x/lucene/sandbox/src/java/org/apache/lucene/util/GeoHashUtils.java Fri Aug 7 20:49:54 2015
@@ -17,6 +17,9 @@ package org.apache.lucene.util;
* limitations under the License.
*/
+import java.util.ArrayList;
+import java.util.Collection;
+
/**
* Utilities for converting to/from the GeoHash standard
*
@@ -150,4 +153,112 @@ public class GeoHashUtils {
return BitUtil.flipFlop((geoHashLong >>> 4) << odd) << (((12 - level) * 5) + (MORTON_OFFSET - odd));
}
+
+ private static final char encode(int x, int y) {
+ return BASE_32[((x & 1) + ((y & 1) * 2) + ((x & 2) * 2) + ((y & 2) * 4) + ((x & 4) * 4)) % 32];
+ }
+
+ /**
+ * Calculate all neighbors of a given geohash cell.
+ *
+ * @param geohash Geohash of the defined cell
+ * @return geohashes of all neighbor cells
+ */
+ public static Collection<? extends CharSequence> neighbors(String geohash) {
+ return addNeighbors(geohash, geohash.length(), new ArrayList<CharSequence>(8));
+ }
+
+ /**
+ * Calculate the geohash of a neighbor of a geohash
+ *
+ * @param geohash the geohash of a cell
+ * @param level level of the geohash
+ * @param dx delta of the first grid coordinate (must be -1, 0 or +1)
+ * @param dy delta of the second grid coordinate (must be -1, 0 or +1)
+ * @return geohash of the defined cell
+ */
+ public final static String neighbor(String geohash, int level, int dx, int dy) {
+ int cell = BASE_32_STRING.indexOf(geohash.charAt(level -1));
+
+ // Decoding the Geohash bit pattern to determine grid coordinates
+ int x0 = cell & 1; // first bit of x
+ int y0 = cell & 2; // first bit of y
+ int x1 = cell & 4; // second bit of x
+ int y1 = cell & 8; // second bit of y
+ int x2 = cell & 16; // third bit of x
+
+ // combine the bitpattern to grid coordinates.
+ // note that the semantics of x and y are swapping
+ // on each level
+ int x = x0 + (x1 / 2) + (x2 / 4);
+ int y = (y0 / 2) + (y1 / 4);
+
+ if (level == 1) {
+ // Root cells at north (namely "bcfguvyz") or at
+ // south (namely "0145hjnp") do not have neighbors
+ // in north/south direction
+ if ((dy < 0 && y == 0) || (dy > 0 && y == 3)) {
+ return null;
+ } else {
+ return Character.toString(encode(x + dx, y + dy));
+ }
+ } else {
+ // define grid coordinates for next level
+ final int nx = ((level % 2) == 1) ? (x + dx) : (x + dy);
+ final int ny = ((level % 2) == 1) ? (y + dy) : (y + dx);
+
+ // if the defined neighbor has the same parent a the current cell
+ // encode the cell directly. Otherwise find the cell next to this
+ // cell recursively. Since encoding wraps around within a cell
+ // it can be encoded here.
+ // xLimit and YLimit must always be respectively 7 and 3
+ // since x and y semantics are swapping on each level.
+ if (nx >= 0 && nx <= 7 && ny >= 0 && ny <= 3) {
+ return geohash.substring(0, level - 1) + encode(nx, ny);
+ } else {
+ String neighbor = neighbor(geohash, level - 1, dx, dy);
+ return (neighbor != null) ? neighbor + encode(nx, ny) : neighbor;
+ }
+ }
+ }
+
+ /**
+ * Add all geohashes of the cells next to a given geohash to a list.
+ *
+ * @param geohash Geohash of a specified cell
+ * @param neighbors list to add the neighbors to
+ * @return the given list
+ */
+ public static final <E extends Collection<? super String>> E addNeighbors(String geohash, E neighbors) {
+ return addNeighbors(geohash, geohash.length(), neighbors);
+ }
+
+ /**
+ * Add all geohashes of the cells next to a given geohash to a list.
+ *
+ * @param geohash Geohash of a specified cell
+ * @param length level of the given geohash
+ * @param neighbors list to add the neighbors to
+ * @return the given list
+ */
+ public static final <E extends Collection<? super String>> E addNeighbors(String geohash, int length, E neighbors) {
+ String south = neighbor(geohash, length, 0, -1);
+ String north = neighbor(geohash, length, 0, +1);
+ if (north != null) {
+ neighbors.add(neighbor(north, length, -1, 0));
+ neighbors.add(north);
+ neighbors.add(neighbor(north, length, +1, 0));
+ }
+
+ neighbors.add(neighbor(geohash, length, -1, 0));
+ neighbors.add(neighbor(geohash, length, +1, 0));
+
+ if (south != null) {
+ neighbors.add(neighbor(south, length, -1, 0));
+ neighbors.add(south);
+ neighbors.add(neighbor(south, length, +1, 0));
+ }
+
+ return neighbors;
+ }
}
Modified: lucene/dev/branches/branch_5x/lucene/sandbox/src/test/org/apache/lucene/util/TestGeoUtils.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/sandbox/src/test/org/apache/lucene/util/TestGeoUtils.java?rev=1694748&r1=1694747&r2=1694748&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/sandbox/src/test/org/apache/lucene/util/TestGeoUtils.java (original)
+++ lucene/dev/branches/branch_5x/lucene/sandbox/src/test/org/apache/lucene/util/TestGeoUtils.java Fri Aug 7 20:49:54 2015
@@ -17,6 +17,10 @@ package org.apache.lucene.util;
* limitations under the License.
*/
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+
import org.junit.BeforeClass;
import org.junit.Test;
@@ -82,6 +86,121 @@ public class TestGeoUtils extends Lucene
}
}
+ /**
+ * Pass condition: lat=42.6, lng=-5.6 should be encoded as "ezs42e44yx96",
+ * lat=57.64911 lng=10.40744 should be encoded as "u4pruydqqvj8"
+ */
+ @Test
+ public void testEncode() {
+ String hash = GeoHashUtils.stringEncode(-5.6, 42.6, 12);
+ assertEquals("ezs42e44yx96", hash);
+
+ hash = GeoHashUtils.stringEncode(10.40744, 57.64911, 12);
+ assertEquals("u4pruydqqvj8", hash);
+ }
+
+ /**
+ * Pass condition: lat=52.3738007, lng=4.8909347 should be encoded and then
+ * decoded within 0.00001 of the original value
+ */
+ @Test
+ public void testDecodePreciseLongitudeLatitude() {
+ final String geohash = GeoHashUtils.stringEncode(4.8909347, 52.3738007);
+ final long hash = GeoHashUtils.mortonEncode(geohash);
+
+ assertEquals(52.3738007, GeoUtils.mortonUnhashLat(hash), 0.00001D);
+ assertEquals(4.8909347, GeoUtils.mortonUnhashLon(hash), 0.00001D);
+ }
+
+ /**
+ * Pass condition: lat=84.6, lng=10.5 should be encoded and then decoded
+ * within 0.00001 of the original value
+ */
+ @Test
+ public void testDecodeImpreciseLongitudeLatitude() {
+ final String geohash = GeoHashUtils.stringEncode(10.5, 84.6);
+
+ final long hash = GeoHashUtils.mortonEncode(geohash);
+
+ assertEquals(84.6, GeoUtils.mortonUnhashLat(hash), 0.00001D);
+ assertEquals(10.5, GeoUtils.mortonUnhashLon(hash), 0.00001D);
+ }
+
+ @Test
+ public void testDecodeEncode() {
+ final String geoHash = "u173zq37x014";
+ assertEquals(geoHash, GeoHashUtils.stringEncode(4.8909347, 52.3738007));
+ final long mortonHash = GeoHashUtils.mortonEncode(geoHash);
+ final double lon = GeoUtils.mortonUnhashLon(mortonHash);
+ final double lat = GeoUtils.mortonUnhashLat(mortonHash);
+ assertEquals(52.37380061d, GeoUtils.mortonUnhashLat(mortonHash), 0.000001d);
+ assertEquals(4.8909343d, GeoUtils.mortonUnhashLon(mortonHash), 0.000001d);
+
+ assertEquals(geoHash, GeoHashUtils.stringEncode(lon, lat));
+ }
+
+ @Test
+ public void testNeighbors() {
+ String geohash = "gcpv";
+ List<String> expectedNeighbors = new ArrayList<>();
+ expectedNeighbors.add("gcpw");
+ expectedNeighbors.add("gcpy");
+ expectedNeighbors.add("u10n");
+ expectedNeighbors.add("gcpt");
+ expectedNeighbors.add("u10j");
+ expectedNeighbors.add("gcps");
+ expectedNeighbors.add("gcpu");
+ expectedNeighbors.add("u10h");
+ Collection<? super String> neighbors = new ArrayList<>();
+ GeoHashUtils.addNeighbors(geohash, neighbors );
+ assertEquals(expectedNeighbors, neighbors);
+
+ // Border odd geohash
+ geohash = "u09x";
+ expectedNeighbors = new ArrayList<>();
+ expectedNeighbors.add("u0c2");
+ expectedNeighbors.add("u0c8");
+ expectedNeighbors.add("u0cb");
+ expectedNeighbors.add("u09r");
+ expectedNeighbors.add("u09z");
+ expectedNeighbors.add("u09q");
+ expectedNeighbors.add("u09w");
+ expectedNeighbors.add("u09y");
+ neighbors = new ArrayList<>();
+ GeoHashUtils.addNeighbors(geohash, neighbors);
+ assertEquals(expectedNeighbors, neighbors);
+
+ // Border even geohash
+ geohash = "u09tv";
+ expectedNeighbors = new ArrayList<>();
+ expectedNeighbors.add("u09wh");
+ expectedNeighbors.add("u09wj");
+ expectedNeighbors.add("u09wn");
+ expectedNeighbors.add("u09tu");
+ expectedNeighbors.add("u09ty");
+ expectedNeighbors.add("u09ts");
+ expectedNeighbors.add("u09tt");
+ expectedNeighbors.add("u09tw");
+ neighbors = new ArrayList<>();
+ GeoHashUtils.addNeighbors(geohash, neighbors );
+ assertEquals(expectedNeighbors, neighbors);
+
+ // Border even and odd geohash
+ geohash = "ezzzz";
+ expectedNeighbors = new ArrayList<>();
+ expectedNeighbors.add("gbpbn");
+ expectedNeighbors.add("gbpbp");
+ expectedNeighbors.add("u0000");
+ expectedNeighbors.add("ezzzy");
+ expectedNeighbors.add("spbpb");
+ expectedNeighbors.add("ezzzw");
+ expectedNeighbors.add("ezzzx");
+ expectedNeighbors.add("spbp8");
+ neighbors = new ArrayList<>();
+ GeoHashUtils.addNeighbors(geohash, neighbors );
+ assertEquals(expectedNeighbors, neighbors);
+ }
+
public static double randomLatFullRange() {
return (180d * random().nextDouble()) - 90d;
}