geocoding 用中纬度实现附近低点搜索(转载)

2013-01-23

geocoding 用经纬度实现附近低点搜索(转载)其中R为地球半径，可取平均值 6371km；φ1, φ2?表示两点的纬度；Δλ

geocoding 用经纬度实现附近低点搜索(转载)

其中

$\haversin (\theta) = \sin^2(\theta/2) = (1-\cos(\theta))/2$

R为地球半径，可取平均值 6371km；
φ_{1, φ_{2?表示两点的纬度；}}
Δλ 表示两点经度的差值。
距离计算函数
下面就是计算球面间两点(lat0, lng)-(lat1, lng1)之间距离的函数。
```
from math import sin, asin, cos, radians, fabs, sqrtEARTH_RADIUS=6371           # 地球平均半径，6371kmdef hav(theta):    s = sin(theta / 2)    return s * sdef 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公式中令φ_{1?= φ_2，可得}
$\Delta\lambda = 2\arcsin \left( {\sin d/2R \over cos\varphi} \right)$
写成python代码就是
```
dlng = 2 * asin(sin(distance / (2 * EARTH_RADIUS)) / cos(lat))dlng = degrees(dlng)        # 弧度转换成角度
```
然后求南北两侧的范围边界，在haversin公式中令 Δλ = 0，可得
$\Delta\varphi = { d \over R }$
写成python代码就是
```
dlat = distance / EARTH_RADIUSdlng = 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;
```
在lat和lng列上建立索引，能从一定程度上提高范围查询的效率。
不过，这样查询到的地点是正方形范围内的地点，一些结果与当前点的距离可能会超出给定的距离。如果要求严格，可以遍历结果并计算与当前点之间的距离，并过滤掉不符合要求的结果。
总结
附近地点搜索条件是距离，而数据库中一般只保存地点的经纬度，因此无法直接查询。本文将距离转化成经纬度范围，利用经纬度上的索引，提高查询效率。

热点排行

编程

geocoding 用中纬度实现附近低点搜索(转载)

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

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