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

Question

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

从DB中选择所有位置然后逐个浏览它们似乎并不是非常有效,从起始位置获取距离以查看它们是否在指定距离内.有没有一种很好的方法来缩小DB中最初选择的位置？一旦我(或没有？)一组缩小的位置,我是否仍然逐个检查距离,或者有更好的方法吗？

我这样做的语言并不重要.谢谢!

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公里是地球的平均半径)

这种方法的计算要求是最小的.然而,对于小距离,结果非常准确.

然后,如果它在给定距离内,或多或少,则使用更准确的方法.

GeographicLib是我所知道的最准确的实现,尽管也可以使用Vincenty逆公式.

如果您使用的是RDBMS,请将纬度设置为主键,将经度设置为辅助密钥.如上所述,查询纬度范围或纬度/经度范围,然后计算结果集的精确距离.

请注意,所有主要RDBMS的现代版本本身都支持地理数据类型和查询.

Answer 2

根据当前用户的纬度,经度和您想要查找的距离,下面给出了sql查询.

SELECT * FROM(
    SELECT *,(((acos(sin((@latitude*pi()/180)) * sin((Latitude*pi()/180))+cos((@latitude*pi()/180)) * cos((Latitude*pi()/180)) * cos(((@longitude - Longitude)*pi()/180))))*180/pi())*60*1.1515*1.609344) as distance FROM Distances) t
WHERE distance <= @distance

@latitude和@longitude是该点的经度和经度.纬度和经度是距离表的列.pi的值是22/7

Answer 3

Tank's Yogihosting

我的数据库中有一组来自 Open Streep Maps 的表，我测试成功。

以米为单位的距离工作正常。

SET @orig_lat=-8.116137;
SET @orig_lon=-34.897488;
SET @dist=1000;

SELECT *,(((acos(sin((@orig_lat*pi()/180)) * sin((dest.latitude*pi()/180))+cos((@orig_lat*pi()/180))*cos((dest.latitude*pi()/180))*cos(((@orig_lon-dest.longitude)*pi()/180))))*180/pi())*60*1.1515*1609.344) as distance FROM nodes AS dest HAVING distance < @dist ORDER BY distance ASC LIMIT 100;

Answer 4

PostgreSQL GIS扩展可能会有所帮助 - 因为它可能已经实现了您正在考虑实现的许多功能.

Answer 5

你需要的是空间搜索。您可以使用Solr 空间搜索。它还内置了纬度/经度数据类型，请查看此处。