algorithm - 查找给定节点和坐标列表的最近节点

Question

假设我有一系列位置及其 X、Y 坐标：

L1(X1, Y1) L2(X2, Y2) L3(X3, Y3) ... L10000(X10000, Y10000)

我有一个函数可以返回两个位置之间的距离：距离（L1，L2）= 5 英里

对于给定位置，我如何找到 100 英里内的所有位置？或者如果更简单，50 个最近的位置

我们的设置是位置及其邮政编码的 SQL Server 表。该函数采用 2 个邮政编码，查找每个邮政编码的纬度/经度并返回距离。我们可以缓存结果，因为它们不会经常更改。

Answer 1

如果您可以将所有位置存储在内存中（lat/lon/id），请使用 Kd-tree。请参阅我对另一个问题的回答 Kd-trees 允许有效的最近邻搜索和 k-最近邻搜索。平均时间复杂度为 O(log n)。如果您无法将所有位置存储在内存中，请检查您的数据库是否支持空间索引。

Answer 2

您将不得不遍历它们并简单地丢弃所有距离 100 英里远的位置，这将是 O(N)

SELECT Location FROM Table WHERE (POWER(Location.X-Selected.X,2) + POWER(Location.Y-Selected.Y,2)) < POWER(Distance,2)

位置将是位置条目。Selected 将是您选择的城市，只需将其 X 和 Y 替换为相应的位置。

我的 SQL 有点生疏了，如果有错误请大喊大叫，我会修复它。

Answer 3

你并没有真正给我们很多关于表结构的信息，所以很难给你一个准确的答案。但是，假设目标邮政编码作为参数 P1 提供给查询。进一步假设表 T 具有 id、name 和 zip 字段。要查找 100 英里内的所有位置，我们可以使用

select id, name, zip, distance(zip,P1) as distance
from T
where distance(zip,P1) <= 100

对于前 50 个查询

select top 50 id, name, zip, distance(zip,P1) as distance
from T
order by distance(zip,P1)

更好的解决方案是计算每个位置的纬度和经度并将其存储在数据库中。您可以考虑跳过函数中的纬度/经度查找并显着提高速度。我假设您已经获得了计算现有函数中大圆距离的代码。

Answer 4

一种解决方案是编写一个如下所示的通用函数，并允许切割：

Location[] findLocationsWithinDist(Location L1, Integer dist, LocationsList locations){
    LocationList results;
    foreach(location : locations){
        if(dist(L1, location) <= dist)
            results.add(location);
    }
    return results;
}

您可以拥有一个数据结构，将每个位置与特定范围内的位置列表一起存储。然后，每次添加新位置时都需要更新此数据结构。不过，这似乎是一个单独的问题。