GeoHash 经纬度坐标编码与解码算法

关于GeoHash的了解是我在做爬虫时发现一些网站比如美团、饿了么都会把一些地理位置进行编码，在检索时能够更快的进行地理空间上的检索，找到距离相近的位置。

GeoHash 原理

将二维的经纬度坐标点转换为一维的字符串，也就是编码，某一个字符串表示了某一个矩形区域，也就是说在这个矩形区域中的所有经纬度点都共享一套编码也就是字符串。 内部的实现采用的是GeoHash算法，其实质其实是二分法。 纬度范围在[-90,90]，经度范围在[-180,180] 拿到一个location时（116.389550， 39.928167） 对纬度区间[-90,90]二分，[-90,0]及[0,90],显然纬度39.928167在[0,90] 得到第一次二分的结果，得到第一次二分结果1 同样继续二分[0,90],[0,45]及[45,90]，39.928167在[0,45],得到第二次二分结果0。 不断进行二分，39.928167总是属于某个区间[a,b]。随着每次迭代区间[a,b]总在缩小，并越来越逼近39.928167。 而二分停止时区间的长度也就决定了编码的长度，也决定了所表示范围的精确程度。

这里写图片描述

这样纬度二分结束，可以得到一串0-1编码，纬度产生的编码为10111 00011，经度也是这样组码，经度产生的编码为11010 01011 偶数位放经度，奇数位放纬度，把2串编码组合生成新串：11100 11101 00100 01111，这里的偶数为是从0开始的。 最后采用base32进行编码，所谓的base32就是用0-9、b-z（去掉a, i, l, o）这32个字母进行编码。 先将0-1串转为十进制，28、29、4、15，0，13，对应表如下

这里写图片描述

因此（116.389550， 39.928167）就可以编码为wx4g0e。

GeoHash 编码特点

1）字符串越长，表示的范围越精确，5位的编码能表示10平方千米范围的矩形区域，而6位编码能表示更精细的区域（约0.34平方千米）

这里写图片描述

2）字符串相似的表示距离相近（特殊情况后文阐述），这样可以利用字符串的前缀匹配来查询附近的POI信息。一个在城区，一个在郊区，城区的GeoHash字符串之间比较相似，郊区的字符串之间也比较相似，而城区和郊区的GeoHash字符串相似程度要低些。

GeoHash编码的好处

查询复杂度高，通过计算位置的距离来查询与当前位置距离近的位置计算成本高，采用GeoHash编码后可以将二维坐标点转换为一维数据，进行排序，实现空间索引来进行查找。另外，就像是饿了么、美团在选餐时利用当前位置的GeoHash的字符串返回共享这一GeoHash字符串的矩形区域来推荐是一个查询速度快并且实用的策略。

GeoHash编码存在的问题

GeoHash 虽然能解决从二维到一维的转变，但也存在一些问题。比如我们在比较三个位置的距离时，最简单的方法是我们就利用路网距离，可能比较复杂，就用欧式距离来做，分别据算出任意两个位置的距离比较，从而获得距离最近的两个位置。但是如果现在不仅仅是三个位置，如果是几十万甚至是更多的位置，我们应该如何处理呢？如果还是求任意两个位置的欧式距离显然那是灾难性的。 而GeoHash对这些位置进行编码，通过前缀匹配，匹配度越高的位置就越相近，但是仔细想想如果两个位置被分到两个不同的矩形区域中，它们的匹配度很低，但是两个位置距离很近，比如下面的和红点距离近的绿点显然和红点是在一个矩形区域中，而和红点匹配度高的显然是和它在一个矩形区域中的另外一个绿点，这样就尴尬了。 出现这种问题的原因是因为GeoHash采用了Peano空间填充曲线，填充过程

这里写图片描述

我们在前面组码经纬纬度时就是这样的，经度纬度经度纬度的间隔组码，因此会出现上面所说的情况，匹配度很低，但是距离很近的情况。 解决的思路很简单，我们查询时，除了使用定位点的GeoHash编码进行匹配外，还使用周围8个区域的GeoHash编码，这样可以避免这个问题。