共计 3006 个字符，预计需要花费 8 分钟才能阅读完成。
GeoHash(1)- 实践篇
兄弟篇：GeoHash(2)- 实现篇
一、前言
最近有个需要，要计算出客户坐标左近 5 公里的所有门店，并依照步行间隔排序。
最间接的办法就是遍历该城市下的所有门店，然而该办法显著不可取，因为在门店数量微小，且还须要计算步行间隔并排序的状况下，工夫简单度过高。
忽然想到当年做图像遇见一个问题：给定一个视频中间断的三千帧，然而曾经乱序，通知你第一帧，将这三千帧进行排序。遍历图像的所有像素点同样不可取，过后的解决方案是利用感知哈希计算出所有图像的指纹，接着利用明氏间隔计算间隔第一张最近的图像作为第二张，而后计算间隔第二张最近的作为第三张，以此类推。
同样，必定也有哈希办法可将地理位置转换成某种编码，并且编码可用于天文计算。它就是 GeoHash。
二、相干常识
进入注释之前，先一起回顾一下初中天文：
本初子午线以西为西经，分十二区，每区 15 度共 180 度；以东为东经，同样分十二区，共 180 度。
赤道以北为北纬，共 90 度；以南为南纬，同样 90 度。
那么在计算机中，坐标示意为：
西经为正数，东经为负数，因而经度取值
[-180, 180]。北纬为负数，南纬为正数，因而纬度取值
[-90, 90]。
咱们晓得赤道长约四万公里，因而经度上每度约等于 111 公里。地球实际上是个不规则球体，但为了简便计算，咱们假如把纬度上每度约等于 222 公里。
三、初识 GeoHash
1. 计算二进制编码
首先计算二进制编码，经度上以 [-180, 180] 开始，纬度以 [-90, 90] 开始，每次将区间进行二分，若输出坐标小于两头值则编码为0，下次区间取左半区间；若大于则编码为1，下次区间取右半区间。以此类推，编码越长，越靠近坐标值，进而越准确。
以 118°04′04, 24°26′46 为例，首先计算经度的编码：
| 编码长度 | 区间 | 两头值 | 编码 | 阐明 | 精度（千米） |
|---|---|---|---|---|---|
| 1 | [-180, 180] | 0 | 1 | 118°04′04 大于 0°，因而编码 1，取右区间 | 19980 |
| 2 | [0, 180] | 90 | 1 | 118°04′04 大于 90° | 9990 |
| 3 | [90, 180] | 135 | 0 | 118°04′04 小于 135°，因而编码 0，取左区间 | 4995 |
| 4 | [90, 135] | 112.5 | 1 | 2497.5 | |
| 5 | [112.5, 135] | 123.75 | 0 | 1248.75 | |
| 6 | [112.5, 123.75] | 118.125 | 0 | 624.375 | |
| 7 | [112.5, 118.125] | 115.3125 | 1 | 312.188 | |
| 8 | [115.3125, 118.125] | 116.71875 | 1 | 156.094 | |
| 9 | [116.71875, 118.125] | 117.421875 | 1 | 78.047 | |
| 10 | [117.421875, 118.125] | 117.7734375 | 1 | 39.024 | |
| N | … | … | . | … |
同样情理，计算纬度得编码：
| 编码长度 | 区间 | 两头值 | 编码 | 阐明 | 精度（千米） |
|---|---|---|---|---|---|
| 1 | [-90, 90] | 0 | 1 | 24°26′46 大于 0°，因而编码 1，取右区间 | 19980 |
| 2 | [0, 90] | 45 | 0 | 24°26′46 小于 45°，因而编码 0，取左区间 | 9990 |
| 3 | [0, 45] | 22.5 | 1 | 4995 | |
| 4 | [22.5, 45] | 33.75 | 0 | 2497.5 | |
| 5 | [22.5, 33.75] | 28.125 | 0 | 1248.75 | |
| 6 | [22.5, 28.125] | 25.3125 | 0 | 624.375 | |
| 7 | [22.5, 25.3125] | 23.906 | 1 | 312.188 | |
| 8 | [23.906, 25.3125] | 24.609 | 0 | 156.094 | |
| 9 | [23.906, 24.609] | 24.2575 | 1 | 78.047 | |
| 10 | [24.2575, 24.609] | 24.433 | 0 | 39.024 | |
| N | … | … | . | … |
综上，假如咱们只取十位编码，经度上失去得编码为 1101001111，纬度上编码为 1010001010。
将两个编码就像经纬交错网一样进行交错：
最初失去经纬二进制编码为11100110000011101110，联合以上两表的精度数据，咱们晓得该编码其实代表的是一块长宽为 39.024 千米的矩形块。
2. 转换 base32 编码
二进制编码其实就能够用来作为地理位置编码，然而：
- 不便于查找周边邻块。计算邻块，须要解析成经、纬两个编码再做计算。而采纳 base32 编码后，可用查表法，减速计算。
- 二进制编码长度过长，不利于检索。
因而，GeoHash 采纳了 base32 和 base36 编码，因为大多数采纳 base32 编码，因而本文仅介绍 base32 编码。
| Decimal | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Base 32 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | B | C | D | E | F | G |
| Decimal | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Base 32 | H | J | K | M | N | P | Q | R | S | T | U | V | W | X | Y | Z |
base32 编码共 32 个编码，因而须要 5 个 bit，将 11100110000011101110 转换为 base32 编码：
最初失去编码为 WS7F。
四、计算邻近块
1. 通用法
通用法的输出是二进制编码，因而不像查表法有位数限度，实用于所有状况，流程简略。
首先将经纬交错的二进制编码拆分为经度、纬度，若要求输出地位以北，则将纬度加一；以南，则将纬度减一；以西，则将经度减一；以东，则将经度加一。须要留神的是，加减后必须放弃原有的有效位数（比方，11 + 01 = 00，放弃两位无效位）。最初将计算结果重新组合，失去要求地位的二进制编码。
过程如下图为例，不再赘述：
2. 查表法
查表法的计算比通用法快很多，不必将输出编码拆分成经纬度进行加减，但须要留神的是：输出的是 base32 编码，因而仅实用于二进制编码位数为 5 的倍数的GeoHash。
网上大部分文章仅讲诉如何利用查表法计算邻块，那么这个查表如何失去呢？失去了编码后，如何计算邻块？网上大部分文章仅讲诉如何利用查表法计算邻块，然而这个查表如何失去呢？
依据后面，咱们晓得编码由 5 个 bit 二进制，并经纬交错组成。因而，若该编码处于奇数位上，即 经 纬 经 纬 经 交错形式；若处于偶数位上，则 纬 经 纬 经 纬 交错形式。
那么，以 W 为例，二进制为 11100，若处于奇数位则在表中为 右 上 右 下 左 ，若处于偶数位则在表中为 上 右 下 左 下，因而 W 在查表中的地位如下图：
同样，求出其余编码的地位，后果为：
以 WS7F 为例，当初要求该地位的邻近块，取末位F，从偶数位表中能够看到，F 的邻近为E, G, D, 9, C，以及往右出了界的 5, 4, 1。因而5, 4, 1 三个邻块还须要看倒数第二位 7。从奇数表中能够看到，7 的左边没有超界（若超界了，看倒数第三位，以此类推），为K。
因而，失去四周邻块别离位 WS7E, WS7G, WS7D, WS79, WS7C, WSK5, WSK4, WSK1，地位关系如下：
五、总结
次要从实践上介绍：
- GeoHash 对地理位置点进行编码的办法：依据“递归二分”获取二进制，将二进制转换为 Base32 编码。
- GeoHash 邻块的疾速计算方法：取末位编码，依据偶数位表查找对应邻块编码，若某方向出界，则查找前一位编码，并依据奇 / 偶表查找相应方向的编码。
算法实现：【搬砖笔记】利用 GeoHash 为地理位置编码——实现篇
六、延申
- GeoHash 不仅能够用来对地位点进行编码，也能够用来对面进行编码，有助于解决点、面的多种组合关系计算。比方，判断点地位是否在门店的配送围栏之内。
-
GeoHash 其实就是 Peano 曲线 的一种利用，如下：
还有许多空间填充曲线，比方公认比拟好的，没有较大渐变的 Hilbert 曲线。
参考
- GeoHash 外围原理解析
- 基于疾速 GeoHash，如何实现海量商品与商圈的高效匹配？