Geo Hash

作者: 悠扬前奏 | 来源:发表于2021-09-27 21:26 被阅读0次

    工作需要,实现了一下Geo Hash算法。
    尽量直接使用位操作,比网上常见的字符串判断位值得写法效率应该高一点。
    TODO:循环的写法可以再优雅一点;注释可以再清晰一点。

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

    代码中用到得Gps类:

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

    相关文章

      网友评论

          本文标题:Geo Hash

          本文链接:https://www.haomeiwen.com/subject/yimknltx.html