Ответ 1
В вашем случае вы должны смотреть GeoHash, что позволяет быстро запросить координаты на заданном расстоянии.
FYI, MongoDB использует geohash внутри, и он отлично работает.
Алгоритм для вычисления расстояний между многими гео-точками
У меня есть матрица, имеющая около 1000 геопространственных точек (долгота, широта), и я пытаюсь найти точки, находящиеся в диапазоне 1KM.
ПРИМЕЧАНИЕ: "Точки динамические, представьте, что движутся 1000 автомобилей, поэтому я должен повторно рассчитать все расстояния каждые несколько секунд"
Я сделал некоторые поиски и прочитал о алгоритмах Graph, таких как (Floyd-Warshall), чтобы решить эту проблему, и у меня появилось много ключевых слов, и теперь я немного потерялся. Я рассматриваю производительность, и поскольку радиус поиска короткий, я не буду рассматривать кривизну земли.
В принципе, кажется, что я должен рассчитать расстояние между каждой точкой и каждой другой точкой, а затем сортировать расстояния, начиная с каждой точки матрицы, и получать точки, находящиеся в его диапазоне. Поэтому, если у меня 1000 координат, я должен выполнить этот процесс (1000 ^ 2-1000) раз, и я не верю, что это оптимальное решение. Спасибо.
Ответы
Ответ 2
Если вы создадите модель с сеткой с шагом 1 км:
0 1 2 3
___|____|____|____
0 | | |
c| b|a | d
___|____|____|____
1 | | |
| |f |
___|e___|____|____
2 | |g |
допустим, что ваша отправная точка - это a. Если ваша сетка имеет размер 1 км, точки в расстоянии 1 км должны находиться в одной и той же ячейке или одном из 8 соседей (точки b, d, e, f).
Любая другая ячейка может быть проигнорирована (c, g).
В то время как d почти на таком же расстоянии от c, c может быть отброшен раньше, потому что есть два препятствия для пересечения, а a и d лежат на противоположных участках их границы и, следовательно, находятся почти на 2 км от друг друга.
Для раннего удаления элемента вы можете исключить, достаточно проверить x- или y-часть координаты. Так как a принадлежит (0,2), если x равно 0 или меньше, или > 3, точка уже вне допустимого диапазона.
После фильтрации только нескольких кандидатов вы можете использовать исчерпывающий поиск.
Ответ 3
Вы можете вычислить геокоды шириной 1 км вокруг каждой из этих 1000 координат и проверить, находятся ли некоторые точки в этом диапазоне. Может быть, это не оптимально, но вы сохраните себе некоторую сортировку.
Ответ 4
Если вы хотите найти матрицу для каждой точки по отношению к каждой точке, то вы уже получили правильную формулу (1000 ^ 2-1000). Для этого расчета нет никакого ярлыка. Однако, когда вы знаете, с чего начать поиск, и вы хотите искать точки в радиусе 1KM, вы можете использовать сетку или пространственный алгоритм для ускорения поиска. Скорее всего, он использует алгоритм деления и покорения, а самый дешевый из них - геостат или кривая z. Вы также можете попробовать kd-дерево. Может быть, это еще проще. Но если ваши точки находятся в эвклидовом пространстве, то здесь описан этот планарный метод: http://en.wikipedia.org/wiki/Closest_pair_of_points_problem.
Edit: Когда я говорю 1000 ^ 2-1000, то я имею в виду размер сетки, но на самом деле 1000 ^ (1000 - 1)/2 пары точек, поэтому намного меньше математики.
Ответ 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, которая затем сделает внутреннюю проверку цикла расстоянием между данной точкой и каждая другая точка дает каждую точку в вашей матрице в качестве входных данных. Вычисления не должны занимать слишком много времени, так как это так важно.
Ответ 6
Попробуйте использовать R-Tree. R-Tree поддерживает операцию, чтобы найти все точки, наиболее близкие к заданной точке, которые находятся не дальше заданного радиуса. Время выполнения является оптимальным, и я думаю, что это O (number_of_points_in_the_result).
Ответ 7
У меня была такая же проблема, но в разработке веб-сервисов В моем случае, чтобы избежать проблемы с расчетом, я использовал простое решение для разделения и завоевания. Идея заключалась в том, чтобы начать вычисление расстояния между новой точкой и другими в каждой новой вставке данных, чтобы мое приложение напрямую достигало расстояния между этими пункты буксировки, которые уже были рассчитаны и помещены в мою базу данных