发布时间:2022-11-19 15:30
在我们平时使用美团,饿了么等app进行订餐,或者使用猫眼进行订电影票的时候,都有一个距离的排序,表明该家店距离我们当前的位置,这种基于地理位置的服务,统一被称为LBS(Location Based Service),而LBS的实现则是借助于GIS,WC(无线通信)等信息技术来实现。而今天我们所要讨论的就是这个距离的实现。
GIS,Geographic information system,地理信息系统。
由于地球是一个椭圆形,我们在计算的时候有点麻烦,所以我们更常用的方式是将地球作为一个球形来计算,而计算球面上任意两点之间的距离的公式通常有两种:Great-circle distance和Haversine formula,而目前大多数公司都是用的是Haversine公式,原因可以参考:
Great-circle distance公式用到了大量余弦函数, 而两点间距离很短时(比如地球表面上相距几百米的两点),余弦函数会得出0.999…的结果, 会导致较大的舍入误差。而Haversine公式采用了正弦函数,即使距离很小,也能保持足够的有效数字。
而有关这两者的介绍可以参考维基百科:Haversine formula 维基百科,Great-circle distance 维基百科。而最终该公式的形式为:
至于为什么是这种形式,其实目前网上有许多推导公式,感兴趣的可以看一下推导过程,顺便回忆一下自己当年学过的数学知识:
1. 关于已知两点经纬度求球面最短距离的公式推导
2. 根据经纬度计算两点之间的距离的公式推导过程以及google.maps的测距函数
而如果要考虑到高度的影响的话,可以参考:https://stackoverflow.com/questions/3694380/calculating-distance-between-two-points-using-latitude-longitude
另外,还有一种方式是 Vincenty’s formulae,该方式也是用于计算球体表面两点之间距离的方式,而它所基于的就是地球是扁球体的形状,因此这种方式比假设地球是球体的方式应该更加准确,但实现起来比较麻烦。感兴趣的可以查看下维基百科:Vincenty’s formulae 维基百科
接下来说几点概念:
3.1 地球半径
由于地球不是一个完美的球体,所以并不能用一个特别准确的值来表示地球的实际半径,不过由于地球的形状很接近球体,用[6357km] 到 [6378km]的范围值可以涵盖需要的所有半径。并且通常情况下,地球半径有几个常用值:
极半径,从地球中心至南极或北极的距离, 相当于6356.7523km;
赤道半径,从地球中心到赤道的距离,大约6378.137km;
平均半径,6371.393km,表示地球中心到地球表面所有各点距离的平均值;
RE,地球半径,有时被使用作为距离单位, 特别是在天文学和地质学中常用,大概距离是6370.856km;
所以我们通过地球半径进行计算的时候,通常情况下,我们可以使用上面的每一个值都可以进行计算,不过或多或少都会有误差的,但这样的误差是也是允许存在的。这里参考自维基百科:维基百科-地球半径
同样,在MySQL中实现该功能,计算公式还是通过Haversine公式。不过在Google Map中,已经提供了相应的实现方式,我们先来看一下。
SELECT
id,
(
3959 * acos(
cos( radians( 37 ) ) * cos( radians( lat ) ) * cos( radians( lng ) - radians(- 122 ) ) + sin( radians( 37 ) ) * sin( radians( lat ) )
)
) AS distance
FROM
markers
HAVING
distance < 25
ORDER BY
distance
LIMIT 0,
20;
而如果我们要查询公里,将3959英里也就是地球半径,修改为6371即可。
Google Maps地址:Creating a Store Locator on Google Maps php&MySQL
4.2 st_distance函数
MySQL其实在很早就提供了这种存储经纬度及相关运算的功能,这种数据类型叫做空间数据类型,而对应的索引被称为空间索引,但由于MySQL之前的版本对InnoDB支持的并不是太好,所以使用的并不多。不过MySQL5.6和MySQL5.7对此进行了优化,添加了st_distance等相关函数来支持经纬度相关的计算。
SELECT
s.*,
( st_distance ( point ( lng, lat ), point (- 122.083235, 37.38714 ) ) * 111195 ) AS distance
FROM
markers s
ORDER BY
distance
其中,point是MySQL的空间数据类型,先不多说这块。就这样,我们只需要通过st_distance函数就计算出了我们所需要查询的结果,不过这里需要说一下:
st_distance 函数返回的单位是degrees,也就是空间单位的度数,我们如果要将degrees转换为米或者千米的话,需要乘以 EARTH_RADIUS * PI/180, EARTH_RADIUS 也就是地球半径,至于是米还是千米,就看该变量的单位。
该运算其实就相当于对地球半径进行弧度与角度的转换,也就是Math.toRadians,而上面我们写的111195其实是一个有误差的值,该值就是通过该计算得出的结果。
其实,MySQL有提供直接查询结果是米的函数:st_distance_sphere,并且该函数的计算结果要比st_distance转换为米的结果更精确。不过该函数是MySQL5.7之后才引入的,5.7之前还是需要通过计算转换成米。更多可参考官方文档地址:MySQL 5.7 ST_Distance_Sphere(g1, g2 [, radius])
5 Geohash算法
Geohash是目前比较主流的范围搜索的算法,比如说搜索附近500米内的地点这种问题。Geohash算法将二维的经纬度编码为一个字符串,每个字符串代表了某一矩形区域,也就是说,这个矩形区域内所有的点(经纬度坐标)都共享相同的GeoHash字符串,这样在查询的时候就可以对该字符串做索引,然后根据该字符串进行过滤。
Geohash算法的最大用途其实就是附近地址搜索了,不过,从geohash的编码算法中可以看出它的一个缺点,也就是边界问题:虽然两个地点距离很近,但恰好位于分界点的两侧,这样geohash字符串就会不相同,然后匹配的时候就会有问题。不过要解决这个问题也很简单,就是计算的时候,计算出8个分别分布在周围8个区域的地点。
原文