Как рассчитать ближайшие координаты к заданной точке из списка координат

Question

В основном у меня есть текущее местоположение пользователей.После этого у меня будет список координат.

Как мне рассчитать ближайший набор координат из списка по текущему местоположению пользователя.Мое приложение написано на Java для платформы Android

Answer 1

Если точки в списке довольно равномерно распределены в области, это должно работать:

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

По заданной координате x найдите квадрант, которому она принадлежит, вычислите расстояния только для точек в том же квадранте (если их там нет, добавьте точки из соседних квадрантов, до успеха), выберите k ближайших точек p_i.

Проверьте, пересекает ли круг c (центр = x, радиус = max (p_i-x)) какие-либо квадранты, которые еще не были проверены, и, если это так, вычислите расстояния до точек из этих квадрантов. Возврат всего множества ближайших k точек.

Вместо выбора всех квадрантов в круге c, вы можете захотеть проверять ближайшие квадранты внутри c, которые содержат точки, пока не найдете k ближайших точек p_i, чтобы все квадранты в c (x, max (p_i-x)) были пустыми или проверил. Ускорьте поиск ближайшего квадранта с O (n) до O (log n): вам необходимо реализовать древовидную структуру: квадранты из 4 квадрантов и т. Д., Которые отслеживают количество точек в каждом квадранте. Когда точки перемещаются, обновите его (O (журнал)). Во всяком случае, для 200 очков это, вероятно, излишнее.

edit: вместо «древовидной структуры» просто используйте хеш-таблицу и простую хеш-функцию, например: (x div 10 ^ p, y div 10 ^ p)

Answer 2

http://developer.android.com/reference/android/location/Location.html

Location location = new Location("");
location.setLatitude(lat);
location.setLongitude(lon);

проверка для методов distanceTo или distanceBetween.

Или вы можете вручную рассчитать расстояние между координатами и найти наименьшее расстояние для расчета расстояния, которое вы можете найти по ссылке http://www.zipcodeworld.com/samples/distance.java.html

Answer 3

Существует алгоритм «разделяй и властвуй», чтобы найти закрывающую пару точек в O (nlogn).Хотя это может быть излишним для вашего размера набора данных.Подробнее об этом здесь