Получить следующие N ближайших Geo-Points

Question

У меня в приложении для Android есть таблица базы данных с географическими точками (лат и долг - значения в десятичных градусах), около 1000 точек. И мне нужно выбрать 20 ближайших точек к определенной географической точке.

Я нашел в Stackoverflow ответ о том, как вычислить расстояние между двумя географическими точками, и был очень счастлив, пока не попытался написать свой запрос. Я обнаружил, что невозможно использовать тригонометрические функции во встроенном sqlite Android.

Но тогда у меня есть идея. Мне действительно не нужно вычислять расстояние. Ближайшая точка находится к другой, меньшая разница в их географических координатах должна быть.

Как я мог использовать этот факт? Достаточно ли упорядочить сохраненные точки по (lat_0 - lat_n) ^ 2 + (lon0-lon_n) ^ 2, где lat_0 и lon_0 - географические координаты данной точки?

Спасибо,

Mur

UPD

Итак, лучший способ получить ответ на мой вопрос - проверить подход, который я описал выше.

Работает довольно хорошо, но не совсем точно по сравнению с точным расстоянием.

Так что, если вам просто нужно вычислить расстояние, это решение в порядке, но в моем случае мне также нужно было упорядочить станции по расстоянию и я не мог использовать это решение.

Благодарю Джона в CashCommons и Philip. Спасибо, ребята

Answer 1

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

РЕДАКТИРОВАТЬ: На основе комментария Филиппа ниже, вы должны масштабировать один из компонентов. Германия находится примерно на 50 градусов северной широты, поэтому умножение долготы на (cos 50 градусов) будет лучше.

Answer 2

Да. :-) Фактическое расстояние равно sqrt ((lat_0 - lat_n) ^ 2 + (lon0-lon_n) ^ 2), но достаточно упорядочить по (lat_0 - lat_n) ^ 2 + (lon0-lon_n) ^ 2.

Answer 3

Хм ... Я не уверен, как этот порядок будет работать?Разве вам не нужен другой порядок для каждой точки, чтобы указать ее соседей.

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

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