java: Найти ближайшие позиции GPS из заданного местоположения GPS

Question

Мне нужно написать программу java для поиска с заданного местоположения GPS P, ближайший набор (2 позиции) позиций GPS (из набора позиций GPS) am GPS должность. Ситуация проиллюстрирована на рисунке. Здесь все позиции отмечены позициями GPS. Из данной позиции P, я хочу найти набор точек, ближайших к P, в данном случае (B,C).

Было бы очень полезно, если бы кто-нибудь может поделиться алгоритм или код snippnet, связанные с этим.

Answer 1

Вы должны вычислить расстояние между P и всеми другими точками, затем взять мин. Это была очевидная часть.

Трудная часть состоит в том, чтобы вычислить расстояние между двумя координатами gps. GPS использует геодезическую систему WGS84 для представления точек на земле. Существуют также различные способы вычисления расстояния на шаре (основные расстояния между лаксодромом и большим кругом). Эвклидовое расстояние всегда ложно на сфере (даже не закрыто), потому что на ненулевой широте, 1 ° Lat < 1 ° Lon ...
См. Distance using WGS84-ellipsoid для вычислений самостоятельно или GDAL, если вы принимаете lib, который будет сделайте это за вас.

Вы можете использовать GDAL для преобразования представлений точек в других геодезических системах. Вы можете, например, указать точки проекта на геодезической системе плана, затем использовать координаты (x, y, z), затем вычислить расстояния (или лучше: квадрат расстояния = x² + y² + z²).

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

Answer 2

Если вы ищете алгоритмическую реализацию, проверьте R-деревья. Они могут быть хорошим способом поиска точечных или ограничивающих типов запросов.

Существует большая библиотека, которую я использую в течение некоторого времени, которая хорошо работает для меня, которая реализовала алгоритм R-Tree. Проверьте JSI, Пространственный индекс Java (http://jsi.sourceforge.net/).

Я оставлю исследование API для вас. Удачи!

Answer 3

Возможно, вы сделаете из данных Quadtree. Это способ представления двухмерных пространственных данных, упрощающих поиск ближайших соседей в log (n) времени. Конструкция дерева - nlog (n), хотя, если вам нужно рассмотреть конструкцию и ближайшего соседа, тогда у вас будет сложность nlog (n).

Нетрудно найти алгоритм ближайшего соседа для квадранта (который является всего лишь 2-й версией дерева k-d). Wiki дает общее представление об этом here

Для дальнейшего чтения, если вам нужно развернуть это на любое другое количество измерений, вы должны прочитать на K-D Trees.

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

Answer 4

Сохраните точки в списке, а затем найдите соседние точки или минимальные расстояния.

This post может быть полезно.