查找距给定 Lat Lng 位置一定距离内的所有纬度经度位置的算法

Question

给定具有经纬度位置的地点数据库，例如 40.8120390、-73.4889650，我如何找到特定位置给定距离内的所有位置？

从数据库中选择所有位置，然后一个一个地遍历它们，获取与起始位置的距离，看它们是否在指定距离内，这似乎效率不高。有什么好的方法可以缩小最初从数据库中选择的位置？一旦我有了(或没有？)一组缩小的位置，我是否仍然一个一个地检查它们以检查距离，还是有更好的方法？

我使用的语言并不重要。谢谢!

Answer 1

首先比较纬度之间的距离。每个纬度相距大约 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 的现代版本都原生支持地理数据类型和查询。