附近地点搜索初探

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

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

球面最短距离公式

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

• Great-circle distance
• Haversine formula

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

其中

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

距离计算函数

下面就是计算球面间两点(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米”这个范围的坐标范围。 虽然它是个圆，但我们可以先求出该圆的外接正方形，然后拿正方形的经纬度范围去搜索数据库。

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

先来求东西两侧的的范围边界。在haversin公式中令φ₁ = φ₂，可得

写成python代码就是

dlng = 2 * asin(sin(distance / (2 * EARTH_RADIUS)) / cos(lat))

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

写成python代码就是

dlat = distance / EARTH_RADIUS

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

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;

在lat和lng列上建立索引，能从一定程度上提高范围查询的效率。

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

总结

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