常见算法之八：GeoHash地理位置距离计算

项目中用到了一个地图页面，而且很多信息是基于LBS的，早期的做法是上传自己的位置经纬度以及半径阈值，用这信息来控制server端的信息返回，确定附近有哪些点需要显示。这种做法能实现功能，但是很笨重，需要服务器进行大量计算，更好是做法是使用GeoHash。

基本原理

GeoHash是一种地址编码方法。他能够把二维的空间经纬度数据编码成一个字符串。我们知道经线是地球仪上的竖线，lng，子午线为0°，分为西经和东经，都是0-180°，经线是角度数值；纬线是地球仪上的横线，lat，赤道是最大的纬线，从赤道开始分为北纬和南纬，都是0-90°，纬线也是角度数值。

为了便于理解，将地球看成一个基于经纬度线的坐标系。故纬度范围可表示为[-90°, 0°)用二进制0代表，（0°, 90°]用二进制1代表，经度范围可表示为[-180°, 0°)用二进制0代表，（0°, 180°]用二进制1代表。

这些范围是确定的，将地球表面分了四个区域，所以四个区域就可以用00,01,10,11来代表。范围可以不断的对半调整，来提高位置区域的精度。

二进制数据可以调整为16进制，或者其他，来压缩网络信息。这样就可以用单个字符串来表示一定精度的位置信息。

算法实现

GeoHash的计算过程分为三步：

第一步：将经纬度转换成二进制
比如这样一个点（39.923201, 116.390705）
纬度的范围是（-90，90），其中间值为0。对于纬度39.923201，在区间（0，90）中，因此得到一个1；（0，90）区间的中间值为45度，纬度39.923201小于45，因此得到一个0，依次计算下去，即可得到纬度的二进制表示，如下表：

最后得到纬度的二进制表示为：

1	10111000110001111001

同理可以得到经度116.390705的二进制表示为：

1	11010010110001000100

第二步：合并纬度、经度的二进制
合并方法是将经度、纬度二进制按照奇偶位合并：

1	11100 11101 00100 01111 00000 01101 01011 00001

第三步：按照Base32进行编码
Base32编码表的其中一种如下，是用0-9、b-z（去掉a, i, l, o）这32个字母进行编码。具体操作是先将上一步得到的合并后二进制转换为10进制数据，然后对应生成Base32码。同理，将编码转换成经纬度的解码算法与之相反，具体不再赘述。

将上述合并后二进制编码后结果为：

wx4g0ec1

特点

Geohash比直接用经纬度的高效很多，而且使用者可以发布地址编码，既能表明自己位于北海公园附近，又不至于暴露自己的精确坐标，有助于隐私保护。

GeoHash用一个字符串表示经度和纬度两个坐标。在数据库中可以实现在一列上应用索引（某些情况下无法在两列上同时应用索引）
GeoHash表示的并不是一个点，而是一个矩形区域
GeoHash编码的前缀可以表示更大的区域。例如wx4g0ec1，它的前缀wx4g0e表示包含编码wx4g0ec1在内的更大范围。这个特性可以用于附近地点搜索

精度

编码越长，表示的范围越小，位置也越精确。因此我们就可以通过比较GeoHash匹配的位数来判断两个点之间的大概距离。
下表摘自维基百科：

可以看出，当geohash base32编码长度为8时，精度在19米左右，而当编码长度为9时，精度在2米左右，编码长度需要根据数据情况进行选择。

算法原理

为什么分别给经度和维度编码？
为什么需要将经纬度两串编码交叉组合成一串编码？

我们紧接着第一小节来说，当将空间划分为四块时候，编码的顺序分别是左下角00，左上角01，右下脚10，右上角11，也就是类似于Z的曲线，当我们递归的将各个块分解成更小的子块时，编码的顺序是自相似的（分形），每一个子快也形成Z曲线，这种类型的曲线被称为Peano空间填充曲线。

这种类型的空间填充曲线的优点是将二维空间转换成一维曲线（事实上是分形维），对大部分而言，编码相似的距离也相近，但Peano空间填充曲线最大的缺点就是突变性，有些编码相邻但距离却相差很远，比如0111与1000，编码是相邻的，但距离相差很大。

除Peano空间填充曲线外，还有很多空间填充曲线，如图所示，其中效果公认较好是Hilbert空间填充曲线，相较于Peano曲线而言，Hilbert曲线没有较大的突变。为什么GeoHash不选择Hilbert空间填充曲线呢？可能是Peano曲线思路以及计算上比较简单吧，事实上，Peano曲线就是一种四叉树线性编码方式。