附近地点搜索初探

附近地点搜索初探

原文:http://blog.charlee.li/location-search/

附近地点搜索,顾名思义,就是搜索用户附近有哪些地点。随着GPS和带有GPS功能的移动设备的普及, 附近地点搜索也变得炙手可热。不过在网上却很少有这方面的讨论。本文的方法并不算最好, 但足以应付一般的应用了。

本文中,数据库采用MySQL,语言采用python。理论上别的数据库和语言也没问题, 但我们要在经纬度上设置两个索引,所以如果你的数据库不支持索引,或者不支持在一个查询中使用两个索引, 那就只能想别的办法了。

球面最短距离公式

球面上任意两点之间的距离计算公式可以参考维基百科上的下述文章,这里就不再赘述了。

值得一提的是,维基百科推荐使用Haversine公式,理由是Great-circle distance公式用到了大量余弦函数, 而两点间距离很短时(比如地球表面上相距几百米的两点),余弦函数会得出0.999…的结果, 会导致较大的舍入误差。而Haversine公式采用了正弦函数,即使距离很小,也能保持足够的有效数字。 以前采用三角函数表计算时的确会有这个问题,但经过实际验证,采用计算机来计算时,两个公式的区别不大。 稳妥起见,这里还是采用Haversine公式。

distance-haversin-distance.png

其中

distance-haversin.png

  • R为地球半径,可取平均值 6371km;
  • φ1, φ2 表示两点的纬度;
  • Δλ 表示两点经度的差值。

距离计算函数

下面就是计算球面间两点(lat0, lng)-(lat1, lng1)之间距离的函数。

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_hav(lat0, lng0, lat1, lng1):
    "用haversine公式计算球面两点间的距离。"
    # 经纬度转换成弧度
    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

范围搜索算法

在庞大的地理数据库中搜索地点,索引是很重要的。但是,我们的需求是搜索附近地点, 例如,坐标(39.91, 116.37)附近500米内有什么地点?搜索条件是地点坐标与当前坐标之间的距离, 显然是无法应用索引的。

那么换个思路:首先算出“给定坐标附近500米”这个范围的坐标范围。 虽然它是个圆,但我们可以先求出该圆的外接正方形,然后拿正方形的经纬度范围去搜索数据库。

distance-map.png

如图,红色部分为要求的搜索范围,绿色部分为实际搜索范围。

先来求东西两侧的的范围边界。在haversin公式中令φ1 = φ2,可得

distance-lng.png

写成python代码就是

dlng = 2 * asin(sin(distance / (2 * EARTH_RADIUS)) / cos(lat))
dlng = degrees(dlng)        # 弧度转换成角度

然后求南北两侧的范围边界,在haversin公式中令 Δλ = 0,可得

distance-lat.png

写成python代码就是

dlat = distance / EARTH_RADIUS
dlng = degrees(dlat)     # 弧度转换成角度

这样,根据当前点坐标,我们可以得出搜索范围为

left-top    : (lat + dlat, lng - dlng)
right-top   : (lat + dlat, lng + dlng)
left-bottom : (lat - dlat, lng - dlng)
right-bottom: (lat - dlat, lng + dlng)

然后利用这个范围构造SQL语句,即可实现范围查询:

SELECT * FROM place WHERE lat > lat1 AND lat < lat2 AND lng > lng1 AND lng < lng2;

latlng列上建立索引,能从一定程度上提高范围查询的效率。

不过,这样查询到的地点是正方形范围内的地点,一些结果与当前点的距离可能会超出给定的距离。 如果要求严格,可以遍历结果并计算与当前点之间的距离,并过滤掉不符合要求的结果。

总结

附近地点搜索条件是距离,而数据库中一般只保存地点的经纬度,因此无法直接查询。 本文将距离转化成经纬度范围,利用经纬度上的索引,提高查询效率。

 

geohash:用字符串实现附近地点搜索

上回说到了用经纬度范围实现附近地点搜索。 一些小型应用中这样做没问题,但在大型应用中它有个显著的缺点:速度慢。慢的原因有两个, 第一是范围比较的索引利用率并不高,第二是SQL语句极其不稳定(不同的当前位置会产生完全不同的SQL查询),很难缓存。

可以考虑使用geohash算法。

geohash是一种地址编码,它能把二维的经纬度编码成一维的字符串。比如,北海公园的编码是wx4g0ec1。

geohash-intro-01.png

geohash有以下几个特点:

首先,geohash用一个字符串表示经度和纬度两个坐标。某些情况下无法在两列上同时应用索引 (例如MySQL 4之前的版本,Google App Engine的数据层等),利用geohash,只需在一列上应用索引即可。

其次,geohash表示的并不是一个点,而是一个矩形区域。比如编码wx4g0ec19,它表示的是一个矩形区域。 使用者可以发布地址编码,既能表明自己位于北海公园附近,又不至于暴露自己的精确坐标,有助于隐私保护。

第三,编码的前缀可以表示更大的区域。例如wx4g0ec1,它的前缀wx4g0e表示包含编码wx4g0ec1在内的更大范围。 这个特性可以用于附近地点搜索。首先根据用户当前坐标计算geohash(例如wx4g0ec1)然后取其前缀进行查询 (SELECT * FROM place WHERE geohash LIKE 'wx4g0e%'),即可查询附近的所有地点。

geohash-intro-02.png

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。

纬度范围 划分区间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。

最后,用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的编码算法中可以看出它的一个缺点:位于格子边界两侧的两点,
虽然十分接近,但编码会完全不同。实际应用中,可以同时搜索当前格子周围的8个格子,即可解决这个问题。

以geohash的python库为例,相关的geohash操作如下:

>>> import geohash
>>> geohash.encode(39.92324, 116.3906, 5)  # 编码,5表示编码长度
'wx4g0'
>>> geohash.expand('wx4g0')                # 求wx4g0格子及周围8个格子的编码
['wx4ep', 'wx4g1', 'wx4er', 'wx4g2', 'wx4g3', 'wx4dz', 'wx4fb', 'wx4fc', 'wx4g0']

最后,我们来看看本文开头提出的两个问题:速度慢,缓存命中率低。使用geohash查询附近地点,用的是字符串前缀匹配:

SELECT * FROM place WHERE geohash LIKE 'wx4g0%';

而前缀匹配可以利用geohash列上的索引,因此查询速度不会太慢。另外,即使用户坐标发生微小的变化, 也能编码成相同的geohash,这就保证了每次执行相同的SQL语句,使得缓存命中率大大提高。

相关资源

Comments are closed.