geohash查找附近的人

微信、默默等查找附近的人最简单的方法就是遍历一遍，然后使用经纬度计算距离。计算公式是http://en.wikipedia.org/wiki/Haversine_formula

$$ havarsin(\frac{d}{R}) = haversin(l_{2} - l_{1}) + cos(l_{1})cos(l_{2})haversin(Δk) $$

其中

$$havarsin(θ) = sin^{2}(\frac{θ}{2}) = \frac{1 - cos(θ)}{2}$$

R是地球半径，$l_{1} l_{2}$是两点纬度，Δk是两点经度的差。

使用Python实现就是

from math import sin, asin, cos, radians, fabs, sqrt

EARTH_RADIUS=6371           # 地球平均半径，6371km

def hav(theta):
    s = sin(theta / 2)
    return s * s

def get_distance(lat0, lng0, lat1, lng1):
    # 经纬度转换成弧度
    lat0 = radians(lat0)
    lat1 = radians(lat1)
    lng0 = radians(lng0)
    lng1 = radians(lng1)

    dlng = fabs(lng0 - lng1)
    dlat = fabs(lat0 - lat1)
    h = hav(dlat) + cos(lat0) * cos(lat1) * hav(dlng)
    distance = 2 * EARTH_RADIUS * asin(sqrt(h))

    return distance

这样的话，每次搜索附近的人，都可以通过公式计算出来附近x km的经纬度范围，然后去数据库查询。这样的缺点就是每次生成的sql语句都不一样，很难缓存，毕竟附近的人不是特别精确的，只要两个人在同一个范围内就可以认为是在一起的。

目前常见的一个解决方案就是geohash，将经纬度映射到一个字符串上。

下面以(39.92324, 116.3906)为例，介绍一下geohash的编码算法。首先将纬度范围(-90, 90)平分成两个区间(-90, 0)、(0, 90)， 如果目标纬度位于前一个区间，则编码为0，否则编码为1。由于39.92324属于(0, 90)，所以取编码为1。然后再将(0, 90)分成 (0, 45), (45, 90)两个区间，而39.92324位于(0, 45)，所以编码为0。以此类推，直到精度符合要求为止，得到纬度编码为1011 1000 1100 0111 1001。经度也用同样的算法，对(-180, 180)依次细分，得到116.3906的编码为1101 0010 1100 0100 0100。

接下来将经度和纬度的编码合并，奇数位是纬度，偶数位是经度，得到编码 11100 11101 00100 01111 00000 01101 01011 00001。最后，用0-9、b-z（去掉a, i, l, o）这32个字母进行base32编码，得到(39.92324, 116.3906)的编码为wx4g0ec1。

http://code.google.com/p/python-geohash/有一个Python的geohash库，相关的api有

r = encode(50.231, 15.234, precision=5)
print r
print bbox(r)
print expand(r)
"""
u2fvf
{'s': 50.2294921875, 'e': 15.2490234375, 'w': 15.205078125, 'n': 50.2734375}
['u2fvc', 'u2fvg', 'u2fy1', 'u2fy4', 'u2fy5', 'u2fv9', 'u2fvd', 'u2fve', 'u2fvf']
"""

由上面的计算公式可以得到，编码长度为3的时候，一个编码能表示大约155km边长的正方形，4位的时候代表大约40km * 20km的矩形，5位的时候能代表5km * 5km的正方形。

还有一个误差对照表

由于GeoHash是将区域划分为一个个规则矩形，并对每个矩形进行编码，目标点在靠近边界的时候，可能会出现：本区域内有一个距离稍远的，但是编码相同，而边界隔壁有一个距离很近的，但是编码不同。解决的思路很简单，我们查询时，除了使用定位点的GeoHash编码进行匹配外，还使用周围8个区域的GeoHash编码，这样可以避免这个问题，也就是上面的expand方法。

现有的GeoHash算法使用的是Peano空间填充曲线，这种曲线会产生突变，造成了编码虽然相似但距离可能相差很大的问题，因此在查询的时候，需要首先筛选GeoHash编码相似的POI点，然后进行实际距离计算。

Peano空间填充曲线最大的缺点就是突变性，有些编码相邻但距离却相差很远，比如0111与1000，编码是相邻的，但距离相差很大。

参考
http://blog.charlee.li/geohash-intro/

http://www.cnblogs.com/LBSer/p/3310455.html

http://www.zhihu.com/question/19596950

MathJax.Hub.Config({
extensions: ["tex2jax.js"],
jax: ["input/TeX", "output/HTML-CSS"],
tex2jax: {
inlineMath: [ ['$','$'], ["\\(","\\)"] ],
displayMath: [ ['$$','$$'], ["\\[","\\]"] ],
processEscapes: true
},
"HTML-CSS": { availableFonts: ["TeX"] }
});

FROM :strcpy.me | Author:strcpy