GeographyUtil.java

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);
            }
        }
    }
}

GeographyUtilTest.java

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));
    }
}

matrix.md

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