我有一个〜5000点的列表（指定为经度/纬度对），我想从用户指定的另一点中找到最近的5个点。最近点的算法
任何人都可以提出一个有效的算法来解决这个问题吗？我在Ruby中实现了这个功能，所以如果有一个合适的库，那么这将是很好的知道，但我仍然对算法感兴趣！
更新：有几个人问过关于这个问题的更多具体细节。所以这里是：
你可以使用曼哈顿距离（比例为纬度）距离非常快速上限估计，这应该是足够好拒绝考生的99.9％，如果他们不密切（编辑：从那以后你告诉我们它们很接近，在这种情况下，你的指标应该是距离平方，按照Lars H的评论）。 考虑相当于拒绝球形矩形边界框外的任何东西（作为圆形边界框的近似）。 我不这样做的Ruby所以这里是算法伪代码：
让纬度，你参照点P（PA，PO）的经度和另一点X（XA，XO）。 预先计算ka，纵向距离的纬度比例因子：ka（= cos（pa in°））。 （严格地说，KA =常数是在P附近的线性近似）
然后距离估计是：D(X,P) = ka*|xa-pa| + |xo-po| = ka*da + do
其中| Z |意味着abs（z）。在最坏情况下，这会高估真实距离√2（当da == do时），因此我们允许如下：
做一个运行搜索并保持Dmin，第五小缩放曼哈顿距离 - 估计。 因此，您可以预先剔除D（X，P）>√2* Dmin（因为它们必须至少远离√（（ka * da）2 +do²）的所有点 - 应该消除99.9％点）。 用D（X，P）保留所有剩余候选点的列表< =√2* Dmin。如果发现新的第五个最小的D，则更新Dmin。优先级队列，否则（coord，D）列表是良好的数据结构。 请注意，我们从未计算欧几里得距离，我们只使用浮点乘法和加法。
（这一类似，只是过滤掉一切，除了我们所感兴趣的区域，因此无需计算准确的距离前期或建立数据结构四叉树。）
如果您告诉我们预期的蔓延这将有助于在纬度，经度（度数，分钟或什么？）中，如果所有点都接近，则此估计器中的√2因子将过于保守，并将每个点标记为候选者;基于查找表的距离估计器将是更可取的。）
Pseudocode：
initialize Dmin with the fifth-smallest D from the first five points in list
for point X in list:
if D(X,P) <= √2 * Dmin:
insert the tuple (X,D) in the priority-queue of candidates
if (Dmin>D): Dmin = D
# after first pass, reject candidates with D > √2 * Dmin (use the final value of Dmin)
# ...
# then a second pass on candidates to find lowest 5 exact distances
你可以通过加速与quad-tree或kd-tree划分二维空间的搜索，然后，一旦你达到你一个比较剩下的距离，一个叶节点，直到找到最接近的匹配。
另请参见this blog post这是指this other blog post这两个讨论最近的邻居搜索与Ruby中的kd-trees。
一般来说 - 一个好主意，但有5000点，创建数据结构需要更长的时间，而不是手动计算所有可能的距离。 – Gleno
取决于〜5000点的列表更改的频率 –
既然你的名单很短，我会强烈推荐蛮力。只需比较所有5000到用户指定的点。这将是O（N），你会得到报酬。
除此之外，四叉树或Kd树是空间细分的常用方法。但在你的情况下，你最终会在树中进行线性插入，然后进行常数对数查找......这有点浪费，如果你可能更适合做线性数目的距离比较和完成它。
现在，如果您想查找N个最近的点，您正在计算计算出的距离并对第一个N进行排序，但这仍然是O（n log n）ish。
编辑：值得注意的是，如果您要重复使用多个查询点的列表，那么构建空间树就变得有价值。
既然你有这么几点，我会建议做一个蛮力搜索，尝试所有点对彼此的影响是O(n^2)操作，n = 5000，或大约2550万次迭代的合适算法，并只存储相关结果。这在C中会有100毫秒的执行时间，所以我们最多在Ruby中查看一两秒钟。
当用户选择一个点时，您可以使用您存储的数据以恒定时间给出结果。
编辑我重新读你的问题，似乎用户提供了自己的最后一点。在这种情况下，每当用户提供一个点时，通过您的设置执行O(n)线性搜索会更快。
而不是纯粹的蛮力，对于5000个节点，我会计算每个节点的单独x + y距离，而不是直线距离。
一旦您对该列表进行了排序，例如，第五个节点的x + y为38，可以排除x或y距离大于38的任何节点。这样，您可以排除很多节点而无需计算直线距离。然后蛮力计算剩余节点的直线距离。
这些算法不容易解释，因此我只会给你一些正确方向的提示。你应该寻找Voronoi Diagrams。使用Voronoi图，您可以轻松地预先计算O（n^2 log n）时间内的图形，并在O（log n）时间内搜索最近的点。
预计算是在晚上完成一个cron工作并且搜索是实时的。这符合你的规格。
现在，您可以保存5000个点中每个点的k个闭合对，然后从Voronoi图的最近点开始搜索剩下的4个点。
但是要警告，这些算法不是很容易实现。
一个很好的参考是：
如果你需要这个多次重复，以不同的用户输入的位置，但不想实现四叉树（或不能找到库实现），那么你可以使用相当直观的局部敏感哈希（种类）方法：
然后当给定一个点（X，Y），
所有你正在做的是说，附近的一个点必须有一个类似x和类似的Y值...
如果是几个点这是确定一个走一个。 – Andrey
无论您选择哪种算法，您都可以通过比较平方距离而不是实际距离来节省一些时间。如果您不需要知道实际距离，则无需执行平方根操作。 –