geohash查找附近的人

admin 2022年5月17日02:44:39安全博客 安全闲碎评论9 views2321字阅读7分44秒阅读模式

微信、默默等查找附近的人最简单的方法就是遍历一遍,然后使用经纬度计算距离。计算公式是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是将区域划分为一个个规则矩形,并对每个矩形进行编码,目标点在靠近边界的时候,可能会出现:本区域内有一个距离稍远的,但是编码相同,而边界隔壁有一个距离很近的,但是编码不同。解决的思路很简单,我们查询时,除了使用定位点的GeoHash编码进行匹配外,还使用周围8个区域的GeoHash编码,这样可以避免这个问题,也就是上面的expand方法。

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

特别标注: 本站(CN-SEC.COM)所有文章仅供技术研究,若将其信息做其他用途,由用户承担全部法律及连带责任,本站不承担任何法律及连带责任,请遵守中华人民共和国安全法.
  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年5月17日02:44:39
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                  geohash查找附近的人 http://cn-sec.com/archives/1013476.html

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: