GeoHash 是空间索引的一种方式,其基本原理是将地球理解为一个二维平面,通过把二维的空间经纬度数据编码为一个字符串,可以把平面递归分解成更小的子块,每个子块在一定经纬度范围内拥有相同的编码。以经纬度为(121.43737,31.192932)为例。
第一步:将经纬度转换为二进制
编码规则为:先将纬度范围(-90, 90)平分成两个区间(-90, 0)和(0, 90),如果目标维度位于前一个区间,则编码为 0,否则编码为 1,然后根据目标纬度所落的区间再平均分成两个区间进行编码,以此类推,直到精度满足要求,经度也用同样的算法。
序号 | 纬度范围 | 划分区间0 | 划分区间1 | 31.192932所属区间 |
1 | (-90,90) | (-90,0) | (0,90) | 1 |
2 | (0,90) | (0,45) | (45,90) | 0 |
3 | (0,45.0) | (0,22.5) | (22.5,45.0) | 1 |
4 | (22.5,45.0) | (22.5,33.75) | (33.75,45.0) | 0 |
5 | (22.5,33.75) | (22.5,28.125) | (28.125,33.75) | 1 |
…… | …… | …… | …… | …… |
最后得到纬度的二进制编码为:101011000101110, 用同样的方式可以得到经度(121.43737)的二进制编码:110101100101101
第二步:将经纬度的二进制编码合并,从偶数 0 开始,经度占偶数位,纬度占奇数位。经度
110101100101101,纬度 101011000101110,得到的二进制编码为:111001100111100000110011110110
| 偶 | 奇 | 偶 | 奇 | 偶 | 奇 | 偶 | 奇 | 偶 | 奇 | 偶 | 奇 | … | 偶 | 奇 | 偶 | 奇 | 偶 | 奇 | 偶 | 奇 | 偶 | 奇 |
索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | … | 12 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 |
经纬度 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | … | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 |
第三步:将合并后的二进制数做 Base32 编码
按照每 5 位一组,分成 6 组,每组计算其对应的十进制数值,按照 Base32 表进行编码。
11100 11001 11100 00011 00111 10110 转换成十进制是 28 25 28 3 7 22,查表编码得到最终结果,wtw37q。
林老师想编写一个 Python 程序,输入编码后的字符串,输出该编码对应的经纬度范围,运行结果如图 a 所示:
图a |