Расчет ближайшей точки в Голанге - PullRequest
Новая
       19

Расчет ближайшей точки в Голанге

0 голосов
/ 23 сентября 2018

Я пишу лямбда-функцию , которая должна возвращать ближайшую точку к другой.Я думаю, что должен быть лучший способ, чем вычислять расстояние до всех 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
}

Если бы вы могли просмотреть код и указать на библиотекиЯ должен использовать, я был бы очень признателен.Также я хотел бы сравнить различные подходы, поэтому мне интересно, как это определить.Я думаю, что в настоящее время мой подход занимает ~ 0,025 с в моей системе i7.Возможно, что я делаю здесь, это преждевременная оптимизация?Поскольку данные моей автобусной остановки, вероятно, не превысят 10 тыс. Баллов.

1 Ответ

0 голосов
/ 23 сентября 2018

Вы можете разбить всю плоскость на сетки, которые могут быть определены O (1) операцией широты и долготы точек, как (int(lat) / 10, int(lng) /10).Выполните предварительный расчет для каждой из 5000 точек и каждой сетки, чтобы определить максимальное и минимальное расстояние между сеткой и точкой.Поддерживайте для каждой сетки набор точек, которые могут дать минимальное расстояние.При хороших алгоритмах деления (обычно достаточно просто делить широту и долготу с определенным числом), набор должен быть очень маленьким, например, не более 10 точек.

Поэтому, когда вы получаете запрос, вы можетеполучить сетку, в которой находится точка, и имеет небольшой список точек, которые могут быть шкафом.Просто обведите его и найдите его.

Расчет минимального и максимального расстояния тривиален, просто будьте осторожны с некоторыми особыми случаями.Поддержание набора может быть выполнено путем сохранения тока (min, max): когда вычисляется новая пара (minI, maxI), сравните ее с текущими.Если maxI max, ничего не происходит.Иначе, просто добавьте новую пару и обновите мин / макс соответственно.

Я сейчас на мобильном телефоне, поэтому не могу предоставить код.Если вам нужен код, чтобы увидеть, как это делается, я добавлю его позже.

...