php附近的商家实现方法—geohash算法原理
最近有一个需求是根据自身的定位，查找附近的商家，之前看过geohash算法可以实现，今天这篇文章主要介绍geohash算法的原理和实现，以便日后使用
geohash算法基本原理:
GeoHash是一种地址编码方法。他能够把二维的空间经纬度数据编码成一个字符串
Geohash的最简单的解释就是：将一个经纬度信息，转换成一个可以排序，可以比较的字符串编码
我们知道，经度范围是东经180到西经180，纬度范围是南纬90到北纬90，我们设定西经为负，南纬为负，所以地球上的经度范围就是[-180， 180]，纬度范围就是[-90，90]。如果以本初子午线、赤道为界，地球可以分成4个部分。
如果纬度范围[-90°, 0°)用二进制0代表，（0°, 90°]用二进制1代表，经度范围[-180°, 0°)用二进制0代表，（0°, 180°]用二进制1代表，那么地球可以分成如下4个部分
如果在小块范围内递归对半划分呢？
可以看到，划分的区域更多了，也更精确了。geohash算法就是基于这种思想，划分的次数更多，区域更多，区域面积更小了。通过将经纬度编码，给地理位置分区.
Geohash算法三个步骤：
第一步：首先将经纬度变成二进制
比如这样一个点（39.92324, 116.3906），纬度的范围是（-90，90），其中间值为0。对于纬度39.923201，在区间（0，90）中，因此得到一个1；（0，90）区间的中间值为45度，纬度39.923201小于45，因此得到一个0，依次计算下去，即可得到纬度的二进制表示，如下表：
纬度范围 | 划分区间0 | 划分区间1 | 39.92324所属区间 |
(-90, 90) | (-90, 0.0) | (0.0, 90) | 1 |
(0.0, 90) | (0.0, 45.0) | (45.0, 90) | 0 |
(0.0, 45.0) | (0.0, 22.5) | (22.5, 45.0) | 1 |
(22.5, 45.0) | (22.5, 33.75) | (33.75, 45.0) | 1 |
(33.75, 45.0) | (33.75, 39.375) | (39.375, 45.0) | 1 |
(39.375, 45.0) | (39.375, 42.1875) | (42.1875, 45.0) | 0 |
(39.375, 42.1875) | (39.375, 40.7812) | (40.7812, 42.1875) | 0 |
(39.375, 40.7812) | (39.375, 40.0781) | (40.0781, 40.7812) | 0 |
(39.375, 40.0781) | (39.375, 39.7265) | (39.7265, 40.0781) | 1 |
(39.7265, 40.0781) | (39.7265, 39.9023) | (39.9023, 40.0781) | 1 |
(39.9023, 40.0781) | (39.9023, 39.9902) | (39.9902, 40.0781) | 0 |
(39.9023, 39.9902) | (39.9023, 39.9462) | (39.9462, 39.9902) | 0 |
(39.9023, 39.9462) | (39.9023, 39.9243) | (39.9243, 39.9462) | 0 |
(39.9023, 39.9243) | (39.9023, 39.9133) | (39.9133, 39.9243) | 1 |
(39.9133, 39.9243) | (39.9133, 39.9188) | (39.9188, 39.9243) | 1 |
(39.9188, 39.9243) | (39.9188, 39.9215) | (39.9215, 39.9243) | 1 |
经度也用同样的算法，对(-180, 180)依次细分，得到116.3906的编码为1101 0010 1100 0100 0100。
经度范围 | 划分区间0 | 划分区间1 | 116.3906所属区间 |
(-180, 180) | (-180, 0.0) | (0.0, 180) | 1 |
(0.0, 180) | (0.0, 90.0) | (90.0, 180) | 1 |
(90.0, 180) | (90.0, 135.0) | (135.0, 180) | 0 |
(90.0, 135.0) | (90.0, 112.5) | (112.5, 135.0) | 1 |
(112.5, 135.0) | (112.5, 123.75) | (123.75, 135.0) | 0 |
(112.5, 123.75) | (112.5, 118.125) | (118.125, 123.75) | 0 |
(112.5, 118.125) | (112.5, 115.312) | (115.312, 118.125) | 1 |
(115.312, 118.125) | (115.312, 116.718) | (116.718, 118.125) | 0 |
(115.312, 116.718) | (115.312, 116.015) | (116.015, 116.718) | 1 |
(116.015, 116.718) | (116.015, 116.367) | (116.367, 116.718) | 1 |
(116.367, 116.718) | (116.367, 116.542) | (116.542, 116.718) | 0 |
(116.367, 116.542) | (116.367, 116.455) | (116.455, 116.542) | 0 |
(116.367, 116.455) | (116.367, 116.411) | (116.411, 116.455) | 0 |
(116.367, 116.411) | (116.367, 116.389) | (116.389, 116.411) | 1 |
(116.389, 116.411) | (116.389, 116.400) | (116.400, 116.411) | 0 |
(116.389, 116.400) | (116.389, 116.394) | (116.394, 116.400) | 0 |
第二步：就是将经纬度合并
接下来将经度和纬度的编码合并，奇数位是纬度，偶数位是经度，得到编码 11100 11101 00100 01111 00000 01101 01011 00001。
第三步：按照Base32进行编码
最后，用0-9、b-z（去掉a, i, l, o）这32个字母进行base32编码，得到(39.92324, 116.3906)的编码为wx4g0ec1。
十进制 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
base32 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | b | c | d | e | f | g |
十进制 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
base32 | h | j | k | m | n | p | q | r | s | t | u | v | w | x | y | z |
解码算法与编码算法相反，先进行base32解码，然后分离出经纬度，最后根据二进制编码对经纬度范围进行细分即可，这里不再赘述
Geohash比直接用经纬度的高效很多，而且使用者可以发布地址编码，既能表明自己位于北海公园附近，又不至于暴露自己的精确坐标，有助于隐私保护。
- GeoHash用一个字符串表示经度和纬度两个坐标。在数据库中可以实现在一列上应用索引（某些情况下无法在两列上同时应用索引）
- GeoHash表示的并不是一个点，而是一个矩形区域
- GeoHash编码的前缀可以表示更大的区域。例如wx4g0ec1，它的前缀wx4g0e表示包含编码wx4g0ec1在内的更大范围。 这个特性可以用于附近地点搜索
编码越长，表示的范围越小，位置也越精确。因此我们就可以通过比较GeoHash匹配的位数来判断两个点之间的大概距离。
问题
geohash算法有两个问题。首先是边缘问题。
如图，如果车在红点位置，区域内还有一个黄点。相邻区域内的绿点明显离红点更近。但因为黄点的编码和红点一样，最终找到的将是黄点。这就有问题了。
要解决这个问题，很简单，只要再查找周边8个区域内的点，看哪个离自己更近即可。
另外就是曲线突变问题。
本文第2张图片比较好地解释了这个问题。其中0111和1000两个编码非常相近，但它们的实际距离确很远。所以编码相近的两个单位，并不一定真实距离很近，这需要实际计算两个点的距离才行。
代码实现将再下篇文章中介绍
参考资料：