Алгоритм расчета расстояний между многими географическими точками

Question

У меня есть матрица, имеющая около 1000 геопространственных точек (долгота, широта), и я пытаюсь найти точки, которые находятся в диапазоне 1 км.

ПРИМЕЧАНИЕ: «Точки динамические, представьте, что 1000 транспортных средств движутся, поэтому мне приходится пересчитывать все расстояния каждые несколько секунд»

Я выполнил некоторые поиски и прочитал об алгоритмах Графа, таких как (Флойд-Варшалл), чтобы решить эту проблему, и у меня появилось много ключевых слов, и сейчас я немного потерян. Я рассматриваю производительность и, поскольку радиус поиска короткий, я не буду учитывать кривизну Земли.

По сути, мне кажется, что мне нужно вычислить расстояние между каждой точкой до каждой другой точки, затем отсортировать расстояния, начиная с каждой точки в матрице, и получить точки, которые находятся в ее диапазоне. Поэтому, если у меня 1000 координат, я должен выполнить этот процесс (1000 ^ 2-1000) раз, и я не верю, что это оптимальное решение. Спасибо.

Answer 1

Если вы делаете модель с шагом сетки 1 км:

  0   1    2    3
 ___|____|____|____
0   |    |    |
   c|   b|a   |   d
 ___|____|____|____
1   |    |    |
    |    |f   |
 ___|e___|____|____
2   |    |g   | 

давайте предположим, что ваша отправная точка -. Если ваша сетка имеет размер 1 км, точки на расстоянии 1 км должны находиться в той же ячейке или в одном из 8 соседей (точки b, d, e, f).

Любая другая клетка может быть проигнорирована (c, g).

В то время как d почти равно расстоянию до a, что и c, c может быть отброшено рано, потому что есть 2 барьера для пересечения, в то время как a и d лежат на противоположных участках их границы, и поэтому находятся почти в 2 км от друг с другом.

При досрочном отбрасывании элемента вы можете исключить, достаточно проверить x- или y-часть координаты. Поскольку a принадлежит (0,2), если x равен 0 или меньше или> 3, точка уже находится вне диапазона.

После фильтрации только нескольких кандидатов вы можете использовать исчерпывающий поиск.

Answer 2

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

К вашему сведению, MongoDB использует geohash внутри, и он работает превосходно.

Answer 3

Попробуйте с R-Tree.R-дерево поддерживает операцию по нахождению всех точек, ближайших к данной точке, которые находятся не дальше указанного радиуса.Время выполнения является оптимальным, и я думаю, что это O (number_of_points_in_the_result).

Answer 4

У меня была такая же проблема, но в разработке веб-сервиса. В моем случае, чтобы избежать проблемы времени вычисления, я использовал простое решение «разделяй и властвуй»: идея состояла в том, чтобы начать вычисление расстояния между новой точкой и другими в каждомдобавление новых данных, так что мое приложение имеет прямой доступ к расстоянию между теми точками буксировки, которые уже были рассчитаны и помещены в мою базу данных

Answer 5

У меня есть что-то похожее на веб-странице, над которой я работал, я думаю. Пользователь щелкает местоположение на карте и вводит радиус, а функция возвращает все местоположения в базе данных в пределах данного радиуса. Вы имеете в виду, что пытаетесь найти точки, которые находятся в пределах 1 км от одной из точек в радиусе? Или вы пытаетесь найти точки, которые находятся в пределах 1 км друг от друга? Я думаю, ты должен сделать что-то вроде этого.

radius = given radius
x1 = latitude of given point;
y1 = longitude of given point;
x2 = null;
y2 = null;
x = null;
y = null;
dist = null;

for ( i=0; i<locationArray.length; i++ ) {
    x2 = locationArray[i].latitude;
    y2 = locationArray[i].longitude;
    x = x1 - x2;
    y = y1 - y2;
    dist = sqrt(x^2 + y^2);
    if (dist <= radius)
        these are your points
}

Если вы пытаетесь вычислить все точки, которые находятся в пределах 1 км от другой точки, вы можете добавить внешний цикл, дающий информацию о x1 и y1, который затем заставит внутренний цикл проверить расстояние между данной точкой каждая другая точка дает каждую точку в вашей матрице в качестве входных данных. Расчеты не должны занимать слишком много времени, поскольку они очень простые.

Answer 6

Если вы хотите найти матрицу для каждой точки относительно каждой точки, то вы уже получили правильную формулу (1000 ^ 2-1000). Там нет никаких ярлыков для этого расчета. Однако, когда вы знаете, с чего начать поиск, и хотите найти точки в радиусе 1 км, вы можете использовать сетку или пространственный алгоритм для ускорения поиска. Скорее всего, он использует алгоритм «разделяй и властвуй», и самым дешевым из них является геохеш или кривая z. Вы также можете попробовать kd-дерево. Может быть, это еще проще. Но если ваши точки находятся в евклидовом пространстве, тогда этот планарный метод описан здесь: http://en.wikipedia.org/wiki/Closest_pair_of_points_problem.

Редактировать: Когда я говорю 1000 ^ 2-1000, я имею в виду размер сетки, но на самом деле это 1000 ^ (1000 - 1) / 2 пары точек, что намного меньше математики.

Answer 7

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