假设我有一系列位置及其 X、Y 坐标:
L1(X1, Y1) L2(X2, Y2) L3(X3, Y3) ... L10000(X10000, Y10000)
我有一个函数返回两个位置之间的距离:distance(L1, L2) = 5 英里
对于给定位置，我如何找到 100 英里内的所有位置？或者，如果更简单的话，50 个最近的位置
我们的设置是一个包含位置及其邮政编码的 SQL Server 表。该函数采用 2 个邮政编码，查找每个邮政编码的纬度/经度并返回距离。我们可以缓存结果，因为它们不会经常更改。
最佳答案
如果您可以将所有位置存储在内存中(lat/lon/id)，请使用 Kd 树。请参阅我对 another question 的回答 Kd-trees 允许高效的最近邻搜索和 k-最近邻搜索。平均时间复杂度为 O(log n)。 如果您不能将所有位置存储在内存中，请检查您的数据库是否支持空间索引。
关于algorithm - 在给定节点和坐标列表的情况下查找最近的节点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13210966/