Use GeoHash to encode a location

Using Geohashes to encode geographic locations — Theory
One, foreword

This article introduces the implementation of the GeoHash algorithm in Java. Any mistakes or suggestions would be appreciated.
Second, the implementation

See GitHub for the full code
Let’s first list the functions implemented:
To convert latitude and longitude to binary encoding, seegetBinaryFunction.
To convert binary encoding to Base32 encoding, seegetBase32Function.
(General method) To obtain the binary code of adjacent block in the corresponding direction according to the binary code and direction, seegetNeighborWithDirectionFunction.
(General method) According to the binary code, obtain the binary code of the adjacent nine grids, seegetNeighborsFunction.
(Table lookup method) Obtain the base32 encoding of adjacent blocks in the corresponding direction according to the base32 encoding and direction, seegetNeighborsByTableFunction.
(Lookup table method) According to the base32 encoding, obtain the base32 encoding of the adjacent nine grid, seegetNeighborsByTableFunction.
The implementation code is as follows:
import java.util.HashMap;
import java.util.Map;

public class GeoHash {

    /** * minimum longitude */
    private static final double MIN_LONGTITUDE = -180.0;

    /** * maximum longitude */
    private static final double MAX_LONGTITUDE = 180.0;

    /** * latitude minimum */
    private static final double MIN_LATITUDE = -90.0;

    /** * maximum latitude */
    private static final double MAX_LATITUDE = 90.0;

    /** * The binary representation is up to 64 bits */
    private static final Integer MAX_BINARY_BITS = 64;

    /** * Base32 encoding is up to 13 bits, because 5*13 = 65 > 64 */
    private static final Integer MAX_BASE32_LENGTH = 13;

    /** * Every five bits are converted to base32 encoding */
    private static final int ENCODE_EVERY_BITS = 5;

    /** * base32 encoding table */
    private static final char[] BASE32_LOOKUP = {'0'.'1'.'2'.'3'.'4'.'5'.'6'.'7'.'8'.'9'.'b'.'c'.'d'.'e'.'f'.'g'.'h'.'j'.'k'.'m'.'n'.'p'.'q'.'r'.'s'.'t'.'u'.'v'.'w'.'x'.'y'.'z'};

    /** * base32 reverse encoding mapping table */
    private final static Map<Character, Integer> BASE32_DECODE_LOOKUP = new HashMap<>();

    /** * encode 0 to populate the table */
    private static final String[] PADDING_LOOKUP = {""."0"."00"."000"."0000"};

    /** * direction enumeration */
    private enum Direction {
        Top,
        Right,
        Bottom,
        Left;
    }

    /** ** ** /
    private static Map<Direction, String> ODD_LOOKUP = new HashMap<>(4);

    /** * even */
    private static Map<Direction, String> EVEN_LOOKUP = new HashMap<>(4);

    /** * odd number of table boundaries */
    private static Map<Direction, String> ODD_BORDERS = new HashMap<>(4);

    /** ** even table boundaries */
    private static Map<Direction, String> EVEN_BORDERS = new HashMap<>(4);

    /** ** the first mark in 64bit */
    private static final long FIRST_BIT_FLAGGED = 0x8000000000000000L;

    /** * static block */
    static {
        for (int i = 0; i < BASE32_LOOKUP.length; i++) {
            BASE32_DECODE_LOOKUP.put(BASE32_LOOKUP[i], i);
        }
        ODD_LOOKUP.put(Direction.Top, "238967debc01fg45kmstqrwxuvhjyznp");
        ODD_LOOKUP.put(Direction.Right, "14365h7k9dcfesgujnmqp0r2twvyx8zb");
        ODD_LOOKUP.put(Direction.Bottom, "bc01fg45238967deuvhjyznpkmstqrwx");
        ODD_LOOKUP.put(Direction.Left, "p0r21436x8zb9dcf5h7kjnmqesgutwvy");
        EVEN_LOOKUP.put(Direction.Top, "14365h7k9dcfesgujnmqp0r2twvyx8zb");
        EVEN_LOOKUP.put(Direction.Right, "238967debc01fg45kmstqrwxuvhjyznp");
        EVEN_LOOKUP.put(Direction.Bottom, "p0r21436x8zb9dcf5h7kjnmqesgutwvy");
        EVEN_LOOKUP.put(Direction.Left, "bc01fg45238967deuvhjyznpkmstqrwx");
        ODD_BORDERS.put(Direction.Top, "bcfguvyz");
        ODD_BORDERS.put(Direction.Right, "prxz");
        ODD_BORDERS.put(Direction.Bottom, "0145hjnp");
        ODD_BORDERS.put(Direction.Left, "028b");
        EVEN_BORDERS.put(Direction.Top, "prxz");
        EVEN_BORDERS.put(Direction.Right, "bcfguvyz");
        EVEN_BORDERS.put(Direction.Bottom, "028b");
        EVEN_BORDERS.put(Direction.Left, "0145hjnp");
    }

    /** * Convert latitude and longitude to binary encoding **@paramLon lon *@paramLat latitude *@paramPrecision, for example, 13 represents 13 bits of binary for each dimension, with warp and weft combined for a total of 26 bits of binary. The maximum accuracy is 32. *@returnBinary encoding */
    public static String getBinary(double lon, double lat, int precision) {
        if (lon <= MIN_LONGTITUDE || lon >= MAX_LONGTITUDE) {
            throw new IllegalArgumentException(String.format("The longitude ranges are (%f, %f)", MIN_LONGTITUDE, MAX_LONGTITUDE));
        }
        if (lat <= MIN_LATITUDE || lat >= MAX_LATITUDE) {
            throw new IllegalArgumentException(String.format("Latitude ranges from (%f, %f)", MIN_LATITUDE, MAX_LATITUDE));
        }
        if ((precision << 1) > MAX_BINARY_BITS) {
            throw new IllegalArgumentException("Accuracy up to 32 bits");
        }

        // The latitude identifier is 0 for longitude and 1 for latitude
        int xyFlag = 0;
        int bits = 1;
        int binaryBits = precision << 1;
        double[] lon_range = {MIN_LONGTITUDE, MAX_LONGTITUDE};
        double[] lat_range = {MIN_LATITUDE, MAX_LATITUDE};
        StringBuilder result = new StringBuilder();
        while (bits <= binaryBits) {
            char divideResult;
            if (xyFlag == 0) {
                divideResult = divideConquer(lon_range, lon);
            } else {
                divideResult = divideConquer(lat_range, lat);
            }
            result.append(divideResult);
            bits++;
            xyFlag = xyFlag ^ 0x1;
        }
        return result.toString();
    }

    /** * Convert binary encoding to base32 encoding * [!] Note that there should be a limit of 5 multiples for binary digits, but in order to achieve different precision can be base32 encoding, shorten the encoding length, there is no restriction, * but the calculated encoding can not be used for table lookup method, only through the general method, longitude and latitude parsing method to calculate the proximity. * *@paramBinary Binary encoding *@returnBase32 encoding * /
    public static String getBase32(final String binary) {
        valideBinary(binary);
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < binary.length(); i += ENCODE_EVERY_BITS) {
            int delta = Math.min(ENCODE_EVERY_BITS, binary.length() - i);
            String tmp = binary.substring(i, i + delta);
            int decimal = Integer.parseInt(tmp, 2);
            result.append(BASE32_LOOKUP[decimal]);
        }
        return result.toString();
    }

    /** * Convert base32 encoding to binary encoding **@paramBase32 Base32 encoding *@paramBits Indicates the binary length *@returnBinary encoding */
    public static String getBinary(final String base32, int bits) {
        valideBase32(base32);
        int[] region = {(base32.length() - 1) * ENCODE_EVERY_BITS, base32.length() * ENCODE_EVERY_BITS};
        if (bits <= region[0] || bits > region[1]) {
            throw new IllegalArgumentException(String.format("Precision does not match base32 encoding, base32 encoding of length %d should have binary length (%d, %d]", base32.length(), region[0], region[1]));
        }
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < base32.length(); ++i) {
            int decimal = BASE32_DECODE_LOOKUP.get(base32.charAt(i));
            String binary = Integer.toBinaryString(decimal);
            // The number of digits needed to complement 0
            int padding = Math.min(ENCODE_EVERY_BITS - binary.length(), bits - result.length());
            binary = PADDING_LOOKUP[padding] + binary;
            result.append(binary);
        }
        return result.toString();
    }

    /** ** query table method to obtain the current base32 encoding block formed by the nine grid, in accordance with the encoding order, as follows: * 0 1 2 * 3 4 5 * 6 7 8 * [!] Note that table lookup only works for multiples of binary length 5. For non-5 multiples, please use the general method. * *@paramBase32 Base32 encoding *@returnBase32 encoded array */
    public static String[] getNeighborsByTable(final String base32) {
        valideBase32(base32);
        String[] result = new String[9];
        result[4] = base32;
        result[1] = getNeighborWithDirectionByTable(base32, Direction.Top);
        result[0] = getNeighborWithDirectionByTable(result[1], Direction.Left);
        result[2] = getNeighborWithDirectionByTable(result[1], Direction.Right);
        result[5] = getNeighborWithDirectionByTable(base32, Direction.Right);
        result[7] = getNeighborWithDirectionByTable(base32, Direction.Bottom);
        result[3] = getNeighborWithDirectionByTable(base32, Direction.Left);
        result[6] = getNeighborWithDirectionByTable(result[7], Direction.Left);
        result[8] = getNeighborWithDirectionByTable(result[7], Direction.Right);
        return result;
    }

    /** * query table method, according to the input base32 encoding and direction, get the corresponding direction of the adjacent base32 encoding **@paramBase32 Base32 encoding *@paramDire direction *@returnBase32 encodes */ in adjacent directions
    public static String getNeighborWithDirectionByTable(final String base32, Direction dire) {
        valideBase32(base32);
        boolean isOdd = (base32.length() & 0x1) = =0x1;
        String prefix = base32.substring(0, base32.length() - 1);
        char lastChar = base32.charAt(base32.length() - 1);
        // Whether is at the boundary
        boolean inBorder;
        char postfix;
        if(isOdd) { inBorder = ODD_BORDERS.get(dire).indexOf(lastChar) ! = -1;
            postfix = ODD_LOOKUP.get(dire).charAt(BASE32_DECODE_LOOKUP.get(lastChar));
        } else{ inBorder = EVEN_BORDERS.get(dire).indexOf(lastChar) ! = -1;
            postfix = EVEN_LOOKUP.get(dire).charAt(BASE32_DECODE_LOOKUP.get(lastChar));
        }
        // If you are at the boundary, continue to recurse
        if (inBorder) {
            prefix = getNeighborWithDirectionByTable(prefix, dire);
        }
        String result = prefix + postfix;
        return result;
    }

    /** * Universal method, according to the input base32 encoding and direction, get the corresponding direction of the adjacent Base32 encoding **@paramBinary Binary encoding *@paramDire direction *@returnBase32 encodes */ in adjacent directions
    public static String getNeighborWithDirection(final String binary, final Direction dire) {
        if (binary.length() <= 1) {
            throw new IllegalArgumentException("Binary code length of at least 2");
        }
        String result = binary;
        String lat, lon;
        int decimal;
        switch (dire) {
            case Top:
                lat = extractEveryTwoBit(binary, 1);
                decimal = Integer.parseInt(lat, 2);
                decimal += 1;
                lat = maskLastNBit(decimal, lat.length());
                result = integrateEveryTwoBit(result, 1, lat);
                break;
            case Right:
                lon = extractEveryTwoBit(binary, 0);
                decimal = Integer.parseInt(lon, 2);
                decimal += 1;
                lon = maskLastNBit(decimal, lon.length());
                result = integrateEveryTwoBit(result, 0, lon);
                break;
            case Bottom:
                lat = extractEveryTwoBit(binary, 1);
                decimal = Integer.parseInt(lat, 2);
                decimal -= 1;
                lat = maskLastNBit(decimal, lat.length());
                result = integrateEveryTwoBit(result, 1, lat);
                break;
            case Left:
                lon = extractEveryTwoBit(binary, 0);
                decimal = Integer.parseInt(lon, 2);
                decimal -= 1;
                lon = maskLastNBit(decimal, lon.length());
                result = integrateEveryTwoBit(result, 0, lon);
                break;
        }
        return result;
    }

    /** * universal method, according to the binary code, calculate the adjacent nine cells * 0 1 2 * 3 4 5 * 6 7 8 *@paramBinary Binary encoding *@returnBinary encoding */ in adjacent directions
    public static String[] getNeighbors(final String binary) {
        valideBinary(binary);
        String[] result = new String[9];
        result[4] = binary;
        result[1] = getNeighborWithDirection(binary, Direction.Top);
        result[0] = getNeighborWithDirection(result[1], Direction.Left);
        result[2] = getNeighborWithDirection(result[1], Direction.Right);
        result[5] = getNeighborWithDirection(binary, Direction.Right);
        result[7] = getNeighborWithDirection(binary, Direction.Bottom);
        result[3] = getNeighborWithDirection(binary, Direction.Left);
        result[6] = getNeighborWithDirection(result[7], Direction.Left);
        result[8] = getNeighborWithDirection(result[7], Direction.Right);
        return result;
    }

    /** * takes the last n bit ** in decimal@paramDecimal *@paramN Last digit *@returnThe last n bits of the string */
    private static String maskLastNBit(long decimal, int n) {
        long mask = 0xffffffffffffffffL;
        decimal <<= (MAX_BINARY_BITS - n);
        long nBit = decimal & mask;
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < n; ++i, nBit <<= 1) {
            if ((nBit & FIRST_BIT_FLAGGED) == FIRST_BIT_FLAGGED) {
                res.append('1');
            } else {
                res.append('0'); }}return res.toString();
    }

    /** * Extract the value ** every other bit in binary, starting with index start@paramBinary Binary encoding *@paramStart Indicates the start index *@returnBinary encoding The */ value of every other bit in binary
    private static String extractEveryTwoBit(String binary, int start) {
        if (start >= binary.length()) {
            throw new IllegalArgumentException("Start table below exceeds length limit");
        }
        StringBuilder res = new StringBuilder();
        for (int i = start; i < binary.length(); i += 2) {
            res.append(binary.charAt(i));
        }
        return res.toString();
    }

    /** * Integrate starts with index start. Integrate is set to every other bit of binary **@paramBinary Binary encoding *@paramStart Indicates the start index *@paramIntegrate Code to be integrated *@returnIntegrated binary encoding */
    private static String integrateEveryTwoBit(String binary, int start, String integrate) {
        if (start >= binary.length()) {
            throw new IllegalArgumentException("Start table below exceeds length limit");
        }
        StringBuilder res = new StringBuilder(binary);
        for (int i = start, j = 0; i < binary.length() && j < integrate.length(); i += 2, ++j) {
            res.replace(i, i + 1, integrate.substring(j, j + 1));
        }
        return res.toString();
    }

    /** * binary, according to the interval, calculate the intermediate value, greater than the given value to 0, less than the given value to 1 **@paramThe range interval *@paramTarget Specifies the value *@returnGreater than the given value is given 0, less than the given value is given 1 */
    private static char divideConquer(double[] range, double target) {
        // Prevent trespassing
        double mid = (range[1] - range[0) /2 + range[0];
        if (target < mid) {
            range[1] = mid;
            return '0';
        } else {
            range[0] = mid;
            return '1'; }}/** * Validates base32 encoding, throws an exception if validation fails@paramBase32 Base32 encoding */
    private static void valideBase32(String base32) throws IllegalArgumentException {
        if (base32 == null || base32.length() == 0) {
            throw new IllegalArgumentException("Base32 encoding cannot be null.");
        }
        if (base32.length() > MAX_BASE32_LENGTH) {
            throw new IllegalArgumentException("Base32 encoding up to 13 bits"); }}/** * Validates base32 encoding, throws an exception if validation fails@paramBinary base32 encoding */
    private static void valideBinary(String binary) throws IllegalArgumentException {
        if (binary == null || binary.length() == 0) {
            throw new IllegalArgumentException("Binary code cannot be null.");
        }
        if (binary.length() > MAX_BINARY_BITS) {
            throw new IllegalArgumentException("Binary code up to 64 bits"); }}}Copy the code
One, foreword

Second, the implementation

Related Posts

One’s deceased father grind data structure Storage structure of chapter 6 figure | figure 3. The productive capacity table 4. Adjacent multiple tables

A detailed explanation of join method in multithreaded programming

Potholes encountered by Spring Initiative ZationBean and analytical thinking
