从给定的经纬度位置开始，找出所有距离该位置一定距离范围内的所有经纬度位置的算法。

Question

假设有一个包含了经度和纬度信息的地点数据库，例如40.8120390, -73.4889650，如何找到距离特定位置一定距离内的所有位置？

从数据库中选择所有位置，然后逐个计算与起始位置之间的距离来确定它们是否在指定距离内似乎不是很高效。有没有好的方法来缩小最初从数据库中选择的位置范围？一旦我有了（或没有）缩小后的位置集合，我仍然需要逐个检查它们之间的距离吗？或者有更好的方法吗？

使用什么编程语言都可以。谢谢！

- Val Schuman

---

这可能是你所需要的：http://en.wikipedia.org/wiki/K-d_tree。 - biziclop

难道不能用一个SQL查询解决吗？SELECT * FROM Places WHERE (Lat - :Lat)^2 + (Long - :Long)^2 <= :Distance^2（当然，地球是球形的，还涉及其他一些数学问题，这只是一个例子） - Dialecticus

@Ashu, nOiAd，很遗憾我不得不放弃那个项目，所以最终我没有选择解决方案。如果你们在项目中使用了其中一种解决方案，我和其他人会非常感谢你们在这里留下对它的评论。 - Val Schuman

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 的现代版本都原生支持地理数据类型和查询。

- Lior Kogan

---

提醒一下，第一个链接坏了。 - kunruh

@kunruh：谢谢。链接指向Ed Williams的航空公式，但现在似乎已经离线了。我已经用一个公式替换了这个链接。 - Lior Kogan

这个链接解释了几乎所有与此主题相关的内容 https://www.movable-type.co.uk/scripts/latlong.html?from=48.6093070,-122.4259880&to=48.5928360,-122.4216130 - madeinQuant

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。

- yogihosting

---

@distance参数是以公里还是英里为单位？ - garfbradaz

我假设距离单位是公里，否则我的脚本将出错，请有人回答上面的问题。 - Umer Abbas

Answer 3

Tank's Yogihosting

我在我的数据库中有一组Open Street 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;

- Helmut Kemper

---

世界不是一个球体！ - Toby Speight

您有什么建议？ - Helmut Kemper

Answer 4

PostgreSQL GIS扩展可能会有所帮助——也就是说，它可能已经实现了你想要实现的大部分功能。

- Gian

Answer 5

你需要的是空间搜索。你可以使用Solr空间搜索。它还内置了经纬度数据类型，在这里查看。

- Zimbabao

---

虽然这理论上回答了问题，但最好在此处包含答案的基本部分，并提供参考链接。 - Toby Speight

Answer 6

像biziclop提到的那样，某种度量空间树可能是您最好的选择。 我有使用kd树和四叉树来执行这些范围查询的经验，它们非常快速； 它们也不难编写。 我建议您研究其中一种结构，因为它们还可以回答其他有趣的问题，例如“我的数据集中离此其他点最近的点是什么？”

- templatetypedef

---

虽然这可能是解决问题的有价值提示，但答案真正需要展示解决方案。请编辑以提供示例代码以展示您的意思。或者，考虑将其编写为评论。 - Toby Speight

我认为在这里放置代码会分散注意力 - 它会过于特定于包含树结构的库和所选择的特定语言（请注意，此问题未标记语言）。 - templatetypedef

Answer 7

既然您说任何语言都可以，那么自然的选择就是PostGIS：

SELECT * FROM places
WHERE ST_DistanceSpheroid(geom, $location, $spheroid) < $max_metres;

如果您想使用WGS基准面，您应该将$spheroid设置为'SPHEROID["WGS 84",6378137,298.257223563]'

假设您已经通过geom列对places进行了索引，这应该是相当高效的。

- Toby Speight

Answer 8

你可以将经纬度转换为UTM格式，这是一种度量格式，有助于计算距离。然后你就可以轻松判断点是否落在特定位置。

- Hamdi

---

虽然这可能是解决问题的有价值提示，但答案真正需要展示解决方案。请编辑以提供示例代码以展示您的意思。或者，考虑将其编写为评论。 - Toby Speight

Answer 9

感谢@yogihosting提供的解决方案，我能够使用下面展示的代码从MySQL的无模式列中实现类似的结果：

// @params - will be bound to named query parameters
$criteria = [];
$criteria['latitude'] = '9.0285183';
$criteria['longitude'] = '7.4869546';
$criteria['distance'] = 500;
$criteria['skill'] = 'software developer';

// Get doctrine connection 
$conn = $this->getEntityManager()->getConnection();

        $sql = '
               SELECT DISTINCT m.uuid AS phone, (((acos(sin((:latitude*pi()/180)) * sin((JSON_EXTRACT(m.location, "$.latitude")*pi()/180))+cos((:latitude*pi()/180)) * 
              cos((JSON_EXTRACT(m.location, "$.latitude")*pi()/180)) * 
              cos(((:longitude - JSON_EXTRACT(m.location, "$.longitude"))*pi()/180))))*180/pi())*60*1.1515*1.609344) AS distance FROM member_profile AS m 
               INNER JOIN member_card_subscription mcs ON mcs.primary_identity = m.uuid
               WHERE mcs.end > now() AND JSON_SEARCH(m.skill_logic, "one", :skill) IS NOT NULL  AND (((acos(sin((:latitude*pi()/180)) * sin((JSON_EXTRACT(m.location, "$.latitude")*pi()/180))+cos((:latitude*pi()/180)) * 
              cos((JSON_EXTRACT(m.location, "$.latitude")*pi()/180)) * 
              cos(((:longitude - JSON_EXTRACT(m.location, "$.longitude"))*pi()/180))))*180/pi())*60*1.1515*1.609344) <= :distance ORDER BY distance
               ';
        $stmt = $conn->prepare($sql);
        $stmt->execute(['latitude'=>$criteria['latitude'], 'longitude'=>$criteria['longitude'], 'skill'=>$criteria['skill'], 'distance'=>$criteria['distance']]);
        var_dump($stmt->fetchAll());

请注意上面的代码片段使用了Doctrine DB连接和PHP。

- Frederick Eze

Answer 10

你可以检查一下这个方程式，我认为它会有所帮助。

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;

- Emad Elmogy

---

尽管这段代码可能有助于解决问题，但它并没有解释为什么以及如何回答这个问题。提供这种额外的上下文将显著提高其长期教育价值。请编辑您的答案以添加说明，包括适用的限制和假设。特别是，魔术值3959和37来自哪里？ - Toby Speight