ruby - 最近点算法

Question

我有一个约 5000 个点的列表(指定为经度/纬度对)，我想找到其中最接近用户指定的另一个点的 5 个点。

谁能建议一个有效的算法来解决这个问题？我正在用 Ruby 实现它，所以如果有合适的库，那将是很好的了解，但我仍然对算法感兴趣!

更新:一些人要求提供有关该问题的更多具体细节。所以这里是:

• 这 5000 个点大部分位于同一城市内。它外面可能有一些，但可以安全地假设其中 99% 位于 75 公里半径内，并且所有它们都位于 200 公里半径内。
• 积分列表很少改变。为了便于讨论，假设它每天更新一次，那段时间我们必须处理几千个请求。

Answer 1

您可以通过使用 quad-tree 对二维空间进行分区来加速搜索或 kd-tree然后，一旦到达叶节点，就将剩余的距离一一比较，直到找到最接近的匹配项。

另见 this blog post这是指 this other blog post两者都讨论了在 Ruby 中使用 kd 树进行最近邻搜索。