Как рассчитать расстояние / близость между одним местоположением и другим (c #)

Question

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

* пример сценария; Пользователь мобильного приложения перемещается в непосредственной близости (30 футов) от одного из своих приложений во многие указанные местоположения ... (как бы рассчитать эту близость между двумя местоположениями, т.е. мобильным пользователем и другими местоположениями)

заранее спасибо

Answer 1

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

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

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

ни в коем случае НЕ выполнять полный поиск (сравнивая ваше текущее местоположение со всем набором сохраненных местоположений). временная сложность такого алгоритма сильно зависит от количества проверяемых местоположений, чем меньше вы проводите сравнение, тем быстрее вы находите решение. полный поиск требует слишком большого количества сравнений, и, если количество местоположений слишком велико по сравнению с вычислительной мощностью вашего устройства, вы заставите мобильное устройство остановиться, прежде чем найти ближайшее местоположение.

Answer 2

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

var distance = Math.Sqrt(a*a + b*b);

Answer 3

Самый простой способ сделать это - использовать класс GeoCoordinate, у которого есть метод GetDistanceTo , который принимает другой метод и возвращает разрыв между ними.

Answer 4

Чтобы расширить ответ Кона выше, это именно то, что я начал делать для приложения, над которым я сейчас работаю. Вероятно, это лучший способ работы с относительно небольшим количеством точек.

В моем приложении, однако, я мог бы сравнить десятки тысяч путевых точек, вместо того, чтобы повторять математику снова и снова, я немного углубился в эту идею. Поскольку все точки находятся в пределах Великобритании, я выбрал три фиксированные точки (в моем случае - точку у Северной Шотландии, одну у Корнуолла и одну у Ла-Манша около Дувра), и когда я сохраняю новую путевую точку, я вычисляю каждая из этих фиксированных точек. Если мне нужно вывести точки, близкие к другому известному местоположению, я могу довольно просто сравнить расстояния от этих путевых точек в базе данных и отодвинуть только те, которые находятся близко. Используя триангуляцию, математика оказывается тривиальной, и я видел значительное увеличение скорости.

РЕДАКТИРОВАТЬ Я также собираюсь проверить ссылку NNS Адриана Плиссона сейчас, чтобы увидеть, поможет ли это мне еще дальше. :)