寻找最近点的Golang计算

在寻找距离给定点最近点的 Go 语言函数中，现有的解决方案需要逐个计算到所有点之间的距离，效率低下。为了优化这一过程，建议将平面划分为网格，并预先计算每个网格与每个点之间的最大和最小距离。当收到查询时，可以快速确定查询点所在的网格，并从该网格中维护的一组候选点中找到距离最近的点。这种方法将查询时间复杂度从 O(n) 降低到 O(1)，从而显著提高了效率。

我正在编写一个 lambda 函数，它需要返回距离另一个点最近的点。我想一定有比每次计算到所有 5000 个点的距离更好的方法。

func (places Places) closest(w place) (c place) {
    c = places[0]
    closestSoFar := w.Point.GreatCircleDistance(c.Point)
    for _, p := range places[1:] {
        distance := w.Point.GreatCircleDistance(p.Point)
        if distance < closestSoFar {
            // Set the return
            c = p
            // Record closest distance
            closestSoFar = distance
        }
    }
    return
}

如果您可以查看代码并指出我应该使用的库，我将不胜感激。另外，我想对不同的方法进行基准测试，所以我想知道如何定义它。我认为目前我的方法在我的 i7 系统上大约需要 0.025 秒。也许我在这里所做的是过早优化？因为我的公交车站数据可能不会超过10k点。

解决方案

您可以将整个平面分割成网格，这些网格可以通过点的纬度和经度的 O(1) 运算来确定，例如 (int(lat) / 10, int(lng) /10)。预先计算 5000 个点中的每个点和每个网格的网格与点之间的最大和最小距离。为每个网格维护一组可能产生最小距离的点。有了好的划分算法（通常只需将经纬度除以一定的数字就足够了），集合应该非常小，比如不超过10个点。

因此，当您收到查询时，您可以立即获取该点所在的网格，并且有一个可以作为壁橱的点的小列表。只需循环它并找到那个即可。

计算最小和最大距离很简单，只是要小心一些特殊情况。维护该集合可以通过保留当前的 ​​(min,max) 来完成：计算一对新的 (minI,maxI) 时，将其与当前的进行比较。如果 maxI < min，则丢弃我们拥有的所有内容并使用新的一对。 如果 minI > max，则什么也不会发生。否则，只需添加新的对并相应地更新最小/最大。

我目前使用的是移动设备，因此无法提供代码。如果您需要代码来了解它是如何完成的，我会稍后添加。

到这里，我们也就讲完了《寻找最近点的Golang计算》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于的知识点！