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

Question

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

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

我有一个函数返回两个位置之间的距离:distance(L1, L2) = 5 英里

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

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

Answer 1

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