Skip to content

Instantly share code, notes, and snippets.

@zhoulifu
Created December 27, 2017 09:08
Show Gist options
  • Save zhoulifu/482b850ec3b12a6978f81baf86c82190 to your computer and use it in GitHub Desktop.
Save zhoulifu/482b850ec3b12a6978f81baf86c82190 to your computer and use it in GitHub Desktop.
import static java.lang.Math.abs;
import static java.lang.Math.acos;
import static java.lang.Math.cos;
import static java.lang.Math.sin;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class GeographyUtil {
public static final double RADIUS_OF_EARTH = 6371.0088; //kilometers
public static final double ANGLE_TO_RADIAN = Math.PI / 180;
private static final int BITS = 6 * 5;
private static final char[] BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz".toCharArray();
private GeographyUtil() {
}
public static boolean isValid(double lat, double lon) {
return (-90 <= lat && lat <= 90) && (-180 <= lon && lon <= 180);
}
public static String geohash(double lat, double lon) throws IllegalArgumentException {
if (!isValid(lat, lon)) {
throw new IllegalArgumentException(
"invalid coordinate pair. lat:" + lat + " , lon:" + lon);
}
return encode(lat, lon);
}
public static List<String> neighbours(String geohash) {
return NeighbourProvider.expand(geohash);
}
private static String encode(double lat, double lon) {
byte[] latBits = getBits(lat, -90, 90);
byte[] lonBits = getBits(lon, -180, 180);
StringBuilder result = new StringBuilder();
int idx = 0, latBit, lonBit;
for (int i = 0, j = 0; i < BITS; i++) {
lonBit = lonBits[i];
latBit = latBits[i];
idx = (idx << 2) | (lonBit << 1 | latBit);
j += 2;
if (j >= 5) {
j -= 5;
result.append(BASE32[(idx & (31 << j)) >>> j]);
idx &= ((1 << j) - 1);
}
}
return result.toString();
}
private static byte[] getBits(double value, double floor,
double ceiling) throws IllegalArgumentException {
byte[] buffer = new byte[BITS];
for (int i = 0; i < BITS; i++) {
double mid = (floor + ceiling) / 2;
if (value > mid) {
buffer[i] = 1;
floor = mid;
continue;
}
ceiling = mid;
}
return buffer;
}
/**
* Calculate the shortest distance between two points on the surface of Earth.
*
* @param lat1 latitude of first point
* @param lon1 longitude of first point
* @param lat2 latitude of second point
* @param lon2 longitude of second point
* @return distance between two points
*/
public static double getDistance(double lat1, double lon1, double lat2, double lon2) {
if (!isValid(lat1, lon1) || !isValid(lat2, lon2)) {
throw new IllegalArgumentException("invalid geographic coordinate");
}
return calculate(lat1, lon1, lat2, lon2);
}
private static double calculate(double lat1, double lon1, double lat2, double lon2) {
double radLat1 = lat1 * ANGLE_TO_RADIAN;
double radLon1 = lon1 * ANGLE_TO_RADIAN;
double radLat2 = lat2 * ANGLE_TO_RADIAN;
double radLon2 = lon2 * ANGLE_TO_RADIAN;
return RADIUS_OF_EARTH * acos(
sin(radLat1) * sin(radLat2) +
cos(radLat1) * cos(radLat2) * cos(abs(radLon1 - radLon2)));
}
private static class NeighbourProvider {
private static final int TOP = 0;
private static final int RIGHT = 1;
private static final int BOTTOM = 2;
private static final int LEFT = 3;
private static final int EVEN = 0;
private static final int ODD = 1;
private static char[][][] NEIGHBOURS;
private static char[][][] BORDERS;
static {
NEIGHBOURS = new char[2][4][];
BORDERS = new char[2][4][];
BORDERS[ODD][TOP] = "bcfguvyz".toCharArray();
BORDERS[ODD][RIGHT] = "prxz".toCharArray();
BORDERS[ODD][BOTTOM] = "0145hjnp".toCharArray();
BORDERS[ODD][LEFT] = "028b".toCharArray();
BORDERS[EVEN][TOP] = BORDERS[ODD][RIGHT];
BORDERS[EVEN][RIGHT] = BORDERS[ODD][TOP];
BORDERS[EVEN][BOTTOM] = BORDERS[ODD][LEFT];
BORDERS[EVEN][LEFT] = BORDERS[ODD][BOTTOM];
NEIGHBOURS[ODD][TOP] = "238967debc01fg45kmstqrwxuvhjyznp".toCharArray();
NEIGHBOURS[ODD][RIGHT] = "14365h7k9dcfesgujnmqp0r2twvyx8zb".toCharArray();
NEIGHBOURS[ODD][BOTTOM] = "bc01fg45238967deuvhjyznpkmstqrwx".toCharArray();
NEIGHBOURS[ODD][LEFT] = "p0r21436x8zb9dcf5h7kjnmqesgutwvy".toCharArray();
NEIGHBOURS[EVEN][TOP] = NEIGHBOURS[ODD][RIGHT];
NEIGHBOURS[EVEN][RIGHT] = NEIGHBOURS[ODD][TOP];
NEIGHBOURS[EVEN][BOTTOM] = NEIGHBOURS[ODD][LEFT];
NEIGHBOURS[EVEN][LEFT] = NEIGHBOURS[ODD][BOTTOM];
}
static List<String> expand(String geohash) {
List<String> list = new LinkedList<>();
String top = calculate(geohash, TOP);
String bottom = calculate(geohash, BOTTOM);
addNonNull(list, calculate(geohash, LEFT)); // left
addNonNull(list, calculate(geohash, RIGHT)); // right
addNonNull(list, top);
addNonNull(list, bottom);
addNonNull(list, calculate(top, LEFT));
addNonNull(list, calculate(top, RIGHT));
addNonNull(list, calculate(bottom, LEFT));
addNonNull(list, calculate(bottom, RIGHT));
return list;
}
private static String calculate(String geohash, int direction) {
if (geohash == null) {
return null;
}
char[] chars = geohash.toCharArray();
final int len = geohash.length();
int parity = len & 1;
int lastIdx = len - 1;
while (lastIdx >= 0 && Arrays.binarySearch(BORDERS[parity][direction], chars[lastIdx]) > -1) {
lastIdx--;
parity ^= 1;
}
if (lastIdx == -1) {
return null; // out of range
}
char lastChar;
while (lastIdx < len) {
lastChar = chars[lastIdx];
chars[lastIdx++] = NEIGHBOURS[parity][direction][Arrays.binarySearch(BASE32, lastChar)];
parity ^= 1;
}
return new String(chars);
}
private static <T> void addNonNull(List<? super T> list, T obj) {
if (obj != null) {
list.add(obj);
}
}
}
}
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import org.junit.Test;
public class GeographyUtilTest {
@Test
public void testGeohash() {
assertEquals(geohash(-90.0, -180.0), "000000000000");
assertEquals(geohash(90, 180), "zzzzzzzzzzzz");
// See the test case at https://en.wikipedia.org/wiki/Geohash#Service
assertEquals(geohash(57.64911, 10.40744).substring(0, 11), "u4pruydqqvj");
}
@Test
public void testGetDistance() {
// Compare the calculated value of the equator with the exact one
assertTrue((getDistance(0, 0, 0, 180) * 2 / 40075.017) >= 0.998);
}
@Test
public void testNearbyHashValues() {
testNearby("wvg0bsqy0pjg",
Arrays.asList("wvg0bsqy0pjf", "wvg0bsqy0pju", "wvg0bsqy0pje",
"wvg0bsqy0pjd", "wvg0bsqy0pjs", "wvg0bsqy0pn4",
"wvg0bsqy0pn5", "wvg0bsqy0pnh"));
testNearby("wx4g0",
Arrays.asList("wx4er", "wx4g2", "wx4g3", "wx4ep", "wx4g1", "wx4dz",
"wx4fb", "wx4fc"));
testNearby("zzzzzz", Arrays.asList("zzzzzx", "zzzzzw", "zzzzzy"));
}
private void testNearby(String geohash, List<String> actualNeighbours) {
List<String> expected = neighbours(geohash);
Collections.sort(expected);
Collections.sort(actualNeighbours);
assertTrue(expected.equals(actualNeighbours));
}
}

Geohash matrix

This matrix was used to determine the neighbor relationship lookup tables.

// odd length

 b  c  f  g  u  v  y  z | b  c  f  g  u  v  y  z
 8  9  d  e  s  t  w  x | 8  9  d  e  s  t  w  x
 2  3  6  7  k  m  q  r | 2  3  6  7  k  m  q  r
 0  1  4  5  h  j  n  p | 0  1  4  5  h  j  n  p
 -  -  -  -  -  -  -  - + -  -  -  -  -  -  -  -
 b  c  f  g  u  v  y  z | b  c  f  g  u  v  y  z
 8  9  d  e  s  t  w  x | 8  9  d  e  s  t  w  x
 2  3  6  7  k  m  q  r | 2  3  6  7  k  m  q  r
 0  1  4  5  h  j  n  p | 0  1  4  5  h  j  n  p


 // Even length

 p  r  x  z | p  r  x  z
 n  q  w  y | n  q  w  y
 j  m  t  v | j  m  t  v
 h  k  s  u | h  k  s  u
 5  7  e  g | 5  7  e  g
 4  6  d  f | 4  6  d  f
 1  3  9  c | 1  3  9  c
 0  2  8  b | 0  2  8  b
 -  -  -  - + -  -  -  -
 p  r  x  z | p  r  x  z
 n  q  w  y | n  q  w  y
 j  m  t  v | j  m  t  v
 h  k  s  u | h  k  s  u
 5  7  e  g | 5  7  e  g
 4  6  d  f | 4  6  d  f
 1  3  9  c | 1  3  9  c
 0  2  8  b | 0  2  8  b
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment