给定具有经纬度位置的地点数据库,例如 40.8120390、-73.4889650,我如何找到特定位置给定距离内的所有位置?
从数据库中选择所有位置,然后一个一个地遍历它们,获取与起始位置的距离,看它们是否在指定距离内,这似乎效率不高。有什么好的方法可以缩小最初从数据库中选择的位置?一旦我有了(或没有?)一组缩小的位置,我是否仍然一个一个地检查它们以检查距离,还是有更好的方法?
我使用的语言并不重要。谢谢!
最佳答案
首先比较纬度之间的距离。每个纬度相距大约 69 英里(111 公里)。范围从赤道的 68.703 英里(110.567 公里)到两极的 69.407(111.699 公里)不等(由于地球略呈椭圆形)。两个位置之间的距离将等于或大于它们的纬度之间的距离。
请注意,这不适用于经度 - 每个经度的长度取决于纬度。但是,如果您的数据限于某个区域(例如单个国家/地区)- 您也可以计算经度的最小和最大范围。
继续进行假设为球形地球的低精度、快速距离计算:
坐标为 {lat1,lon1} 和 {lat2,lon2} 的两点之间的大圆距离 d 由下式给出:
d = acos(sin(lat1)*sin(lat2)+cos(lat1)*cos(lat2)*cos(lon1-lon2))
一个数学上等效的公式,它对短距离的舍入误差较小:
d = 2*asin(sqrt((sin((lat1-lat2)/2))^2 +
cos(lat1)*cos(lat2)*(sin((lon1-lon2)/2))^2))
d 是以弧度为单位的距离
distance_km ≈ radius_km * distance_radians ≈ 6371 * d
(6371 公里是 average radius of the earth )
此方法的计算要求极低。然而,对于小距离,结果非常准确。
然后,如果在给定的距离内,或多或少,使用更准确的方法。
GeographicLib是我所知道的最准确的实现,尽管 Vincenty inverse formula也可以使用。
如果您使用的是 RDBMS,请将纬度设置为主键,将经度设置为辅助键。如上所述查询纬度范围或纬度/经度范围,然后计算结果集的准确距离。
请注意,所有主要 RDBMS 的现代版本都原生支持地理数据类型和查询。
关于查找距给定 Lat Lng 位置一定距离内的所有纬度经度位置的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5031268/