Geo Hash

import java.util.Arrays;
import java.util.BitSet;
import java.util.HashMap;

/**
 * GeoHash编码
 * 采用base32格式编码，5位一编码，存在经纬度精度不一致的情况，此时经度的经度优先
 *
 * @author pengjz <br>
 * @version 1.0 <br>
 * @description GeoHash <br>
 * @date 2021/9/24 16:50 <br>
 */
public class GeoHash {

    public static final int BASE_BIT_NUM = 5;

    public static final double MIN_LAT = -90;
    public static final double MAX_LAT = 90;
    public static final double MIN_LON = -180;
    public static final double MAX_LON = 180;

    private final int hashLength;
    /**
     * 二进制长
     */
    private final int bitLength;

    /**
     * 单独经纬度的长（单数取维度优先）
     */
    private final int latLength;

    /**
     * 该精度下最小维度
     */
    private double minLat;
    /**
     * 该精度下最小经度
     */
    private double minLon;

    private final static char[] DIGITS = {'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'};

    /**
     * 定义编码映射关系
     */
    final static HashMap<Character, Integer> LOOKUP = new HashMap<>();

    /*
      初始化编码映射内容
     */
    static {
        int i = 0;
        for (char c : DIGITS) {
            LOOKUP.put(c, i++);
        }
    }

    /**
     * 构造函数，参数为hash编码长度，长度越长经度越高
     * 经度的经度优先
     *
     * @param hashLength hash编码长度
     */
    public GeoHash(int hashLength) {
        this.hashLength = hashLength;
        this.latLength = (int) ((hashLength * BASE_BIT_NUM + 0.5) / 2 + 0.5);
        this.bitLength = latLength * 2;
        /*
         * Hash编码长度，也就是hash表示的经度
         */
        int scaleTime = hashLength * BASE_BIT_NUM / 2;
        minLat = MAX_LAT - MIN_LAT;
        for (int i = 0; i < scaleTime; i++) {
            minLat /= 2.0;
        }
        minLon = MAX_LON - MIN_LON;
        for (int i = 0; i < latLength; i++) {
            minLon /= 2.0;
        }
    }


    /**
     * hash编码
     *
     * @param lat 纬度
     * @param lon 经度
     * @return geo hash
     */
    public String encode(double lat, double lon) {
        // 经纬度的位编码
        BitSet latBits = getBits(lat, MIN_LAT, MAX_LAT);
        BitSet lonBits = getBits(lon, MIN_LON, MAX_LON);
        BitSet gpsBits = new BitSet();
        /*
         * 把位编码整合，上一步低精度在低位，高精度在高位，这里需要翻转
         */
        for (int i = 0; i < latLength; i++) {
            if (lonBits.get(i)) {
                gpsBits.set(bitLength - i * 2 - 1);
            }
            if (latBits.get(i)) {
                gpsBits.set(bitLength - i * 2 - 2);
            }
        }
        // 对整合后的位进行编码
        return bsToBase32(gpsBits);
    }

    public String encode(Gps gps) {
        return encode(gps.getLat(), gps.getLon());
    }

    /**
     * 将二进制编码转换为hash字符串
     *
     * @param bitSet 二进制编码
     * @return hash字符串
     */
    private String bsToBase32(BitSet bitSet) {
        StringBuilder sb = new StringBuilder();
        for (int i = bitLength; i >= BASE_BIT_NUM; i -= BASE_BIT_NUM) {
            final BitSet aSet = bitSet.get(i - BASE_BIT_NUM, i);
            final long[] longs = aSet.toLongArray();
            if (longs.length > 0) {
                sb.append(DIGITS[(int) longs[0]]);
            } else {
                sb.append(DIGITS[0]);
            }
        }
        return sb.toString();
    }

    public Gps decode(String geoHash) {

        /*
         * 整合位编码
         * 上一步高精度在高位，需要翻转
         */
        BitSet bitSet = base32ToBs(geoHash);
        BitSet latSet = new BitSet();
        BitSet lonSet = new BitSet();
        for (int i = 0; i < latLength; i++) {
            // 偶数位，经度
            if (bitSet.get(hashLength * BASE_BIT_NUM - 1 - i * 2)) {
                lonSet.set(i);
            }
            // 奇数位，维度
            if (hashLength * BASE_BIT_NUM - 2 - i * 2 > 0
                    && bitSet.get(hashLength * BASE_BIT_NUM - 2 - i * 2)) {
                latSet.set(i);
            }
        }
        // 算出来是格子靠近0，0的角，需要加挪到格子中间更准
        return new Gps(
                decodeLat(latSet, MIN_LAT, MAX_LAT) + minLat / 2,
                decodeLat(lonSet, MIN_LON, MAX_LON) + minLon / 2
        );
    }

    private double decodeLat(BitSet bitSet, double minLat, double maxLat) {
        double mid = 0;
        for (int i = 0; i < bitSet.length(); i++) {
            mid = (minLat + maxLat) / 2;
            if (bitSet.get(i)) {
                minLat = mid;
            } else {
                maxLat = mid;
            }
        }
        return mid;
    }

    private BitSet base32ToBs(String base32) {
        BitSet bitSet = new BitSet();
        for (int i = 0; i < this.hashLength; i++) {
            int int32 = LOOKUP.get(base32.charAt(i));
            for (int j = 0; j < BASE_BIT_NUM; j++) {
                final int i1 = 1 << j;
                if ((int32 & i1) == i1) {
                    bitSet.set((this.hashLength - 1 - i) * BASE_BIT_NUM + j);
                }
            }
        }
        return bitSet;
    }

    /**
     * 获取经纬度的二进制编码
     *
     * @param lat    经度/纬度
     * @param minLat 最小经度/维度
     * @param maxLat 最大经度/维度
     * @return 二进制编码
     */
    private BitSet getBits(double lat, double minLat, double maxLat) {
        BitSet bitSet = new BitSet(latLength);
        for (int i = 0; i < latLength; i++) {
            double mid = (minLat + maxLat) / 2;
            if (lat >= mid) {
                bitSet.set(i);
                minLat = mid;
            } else {
                maxLat = mid;
            }
        }
        return bitSet;
    }

    public String[][] getAroundGeoHash(Gps gps) {
        return getAroundGeoHash(gps.getLat(), gps.getLon());
    }

    /**
     * 根据hash code获取周围的hashcode
     *
     * @param hashCode 中心点的hashcode
     * @return 以hashcode为中心点的周围九个格子的hashcode
     */
    public String[][] getAroundGeoHash(String hashCode) {
        Gps gps = this.decode(hashCode);
        return getAroundGeoHash(gps.getLat(), gps.getLon());
    }

    /**
     * 获取包含周围格子的geoHash字符串
     * 返回值为二维数组，对应其方位
     * 西北   正北  东北
     * 正西   中间  正东
     * 西南   正南  东南
     *
     * @param lat 中心点维度
     * @param lon 中心点经度
     * @return 周围的geoHash字符串
     */
    public String[][] getAroundGeoHash(double lat, double lon) {
        // 结果矩阵
        String[][] result = new String[3][3];
        // 北边格子的维度
        double northLat = lat + minLat;
        // 南边格子的维度
        double southLat = lat - minLat;
        // 东边各自的经度
        double eastLon = lon + minLon;
        // 西边各自的经度
        double westLon = lon - minLon;
        // 西北
        result[0][0] = encode(northLat, westLon);
        // 正北
        result[0][1] = encode(northLat, lon);
        // 东北
        result[0][2] = encode(northLat, eastLon);
        // 正西
        result[1][0] = encode(lat, westLon);
        // 正中
        result[1][1] = encode(lat, lon);
        // 正东
        result[1][2] = encode(lat, eastLon);
        // 西南
        result[2][0] = encode(southLat, westLon);
        // 正南
        result[2][1] = encode(southLat, lon);
        // 东南
        result[2][2] = encode(southLat, eastLon);
        return result;
    }

    /**
     * 验证：http://www.geohash.cn/
     *
     * @param args 参数
     */
    public static void main(String[] args) {
        Gps gps = new Gps(37.384482, 76.649411);
        System.out.println(gps.getLon() + "," + gps.getLat());

        final GeoHash geoHash6 = new GeoHash(6);
        String centerHash = geoHash6.encode(gps);
        System.out.println(centerHash);
        final String[][] aroundGeoHash6 = geoHash6.getAroundGeoHash(gps);
        for (String[] geoHash : aroundGeoHash6) {
            System.out.println(Arrays.toString(geoHash));
        }
        Gps gpsDecode = geoHash6.decode(centerHash);
        System.out.println(gpsDecode.getLon() + "," + gpsDecode.getLat());

        final GeoHash geoHash7 = new GeoHash(7);
        centerHash = geoHash7.encode(gps);
        System.out.println(centerHash);
        final String[][] aroundGeoHash7 = geoHash7.getAroundGeoHash(gps);
        for (String[] geoHash : aroundGeoHash7) {
            System.out.println(Arrays.toString(geoHash));
        }
        gpsDecode = geoHash7.decode(centerHash);
        System.out.println(gpsDecode.getLon() + "," + gpsDecode.getLat());

    }

}

public class Gps {

    double lat;
    double lon;

    public Gps(double lat, double lon) {
        this.lat = lat;
        this.lon = lon;
    }

    public double getLat() {
        return lat;
    }

    public void setLat(double lat) {
        this.lat = lat;
    }

    public double getLon() {
        return lon;
    }

    public void setLon(double lon) {
        this.lon = lon;
    }
}