查找距给定 Lat Lng 位置一定距离内的所有纬度经度位置的算法 [英] Algorithm to find all Latitude Longitude locations within a certain distance from a given Lat Lng location

问题描述

给定一个包含纬度 + 经度位置的地点数据库，例如 40.8120390、-73.4889650，我如何找到特定位置给定距离内的所有位置?

Given a database of places with Latitude + Longitude locations, such as 40.8120390, -73.4889650, how would I find all locations within a given distance of a specific location?

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

It doesn't seem very efficient to select all locations from the DB and then go through them one by one, getting the distance from the starting location to see if they are within the specified distance. Is there a good way to narrow down the initially selected locations from the DB? Once I have (or don't?) a narrowed down set of locations, do I still go through them one by one to check the distance, or is there a better way?

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

The language I do this in doesn't really matter. Thanks!

推荐答案

首先比较纬度之间的距离.每个纬度相距约 69 英里(111 公里).范围从赤道的 68.703 英里(110.567 公里)到两极的 69.407(111.699 公里)不等(由于地球略呈椭圆形).两个位置之间的距离将等于或大于它们的纬度之间的距离.

Start by Comparing the distance between latitudes. Each degree of latitude is approximately 69 miles (111 kilometers) apart. The range varies (due to the earth's slightly ellipsoid shape) from 68.703 miles (110.567 km) at the equator to 69.407 (111.699 km) at the poles. The distance between two locations will be equal or larger than the distance between their latitudes.

请注意，这不适用于经度 - 每个经度的长度取决于纬度.但是，如果您的数据仅限于某个区域(例如单个国家/地区) - 您也可以计算经度的最小和最大范围.

Note that this is not true for longitudes - the length of each degree of longitude is dependent on the latitude. However, if your data is bounded to some area (a single country for example) - you can calculate a minimal and maximal bounds for the longitudes as well.

继续进行假设为球形地球的低精度、快速距离计算:

Continue will a low-accuracy, fast distance calculation that assumes spherical earth:

坐标为 {lat1,lon1} 和 {lat2,lon2} 的两点之间的大圆距离 d 由下式给出:

The great circle distance d between two points with coordinates {lat1,lon1} and {lat2,lon2} is given by:

d = acos(sin(lat1)*sin(lat2)+cos(lat1)*cos(lat2)*cos(lon1-lon2))

一个数学上等价的公式是:

A mathematically equivalent formula, which is less subject to rounding error for short distances is:

d = 2*asin(sqrt((sin((lat1-lat2)/2))^2 +
    cos(lat1)*cos(lat2)*(sin((lon1-lon2)/2))^2))

d 是以弧度表示的距离

d is the distance in radians

distance_km ≈ radius_km * distance_radians ≈ 6371 * d

(6371 公里是地球的平均半径)

此方法的计算要求最低.但是，对于小距离，结果非常准确.

This method computational requirements are mimimal. However the result is very accurate for small distances.

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

Then, if it is in a given distance, more or less, use a more accurate method.

GeographicLib 是我所知道的最准确的实现，虽然 Vincenty 逆公式 也可以使用.

GeographicLib is the most accurate implementation I know, though Vincenty inverse formula may be used as well.

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

If you are using an RDBMS, set the latitude as the primary key and the longitude as a secondary key. Query for a latitude range, or for a latitude/longitude range, as described above, then calculate the exact distances for the result set.

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

Note that modern versions of all major RDBMSs support geographical data-types and queries natively.

这篇关于查找距给定 Lat Lng 位置一定距离内的所有纬度经度位置的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！