Алгоритм поиска всех местоположений широты и долготы на определенном расстоянии от заданного местоположения широты и долготы

Question

Учитывая базу данных мест с местоположениями Широта + Долгота, таких как 40.8120390, -73.4889650, как мне найти все места на заданном расстоянии от определенного места?

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

Язык, на котором я это делаю, не имеет большого значения. Спасибо!

Answer 1

Начните с сравнения расстояния между широтами.Каждый градус широты составляет приблизительно 69 миль (111 километров) друг от друга.Диапазон варьируется (из-за слегка эллипсоидальной формы Земли) от 68,703 миль (110,567 км) на экваторе до 69,407 (111,699 км) на полюсах.Расстояние между двумя точками будет равно или больше расстояния между их широтами.

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

---

Продолжение будет с малой точностью, быстрое расстояниевычисление, в котором предполагается сферическая земля:

Величина большого круга d между двумя точками с координатами {lat1, lon1} и {lat2, lon2} определяется по формуле:

d = acos(sin(lat1)*sin(lat2)+cos(lat1)*cos(lat2)*cos(lon1-lon2))

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

d = 2*asin(sqrt((sin((lat1-lat2)/2))^2 +
    cos(lat1)*cos(lat2)*(sin((lon1-lon2)/2))^2))

d - расстояние в радианах

distance_km ≈ radius_km * distance_radians ≈ 6371 * d

(6371 км - средний радиус Земли)

Требования к вычислительным методам минимальны.Однако результат очень точен для небольших расстояний.

---

Затем, если он находится на заданном расстоянии, более или менее, используйте более точный метод.

GeographicLib - наиболее точная из известных мне реализаций, хотя может использоваться и обратная формула Винсента .

---

Если вы используете RDBMS, установите широту в качестве первичного ключа идолгота в качестве вторичного ключа.Запросите диапазон широты или диапазон широты / долготы, как описано выше, затем вычислите точные расстояния для набора результатов.

Обратите внимание, что современные версии всех основных РСУБД поддерживают географические типы данных и выполняют собственные запросы.

Answer 2

Исходя из широты, долготы текущего пользователя и расстояния, которое вы хотите найти, запрос sql приведен ниже.

SELECT * FROM(
    SELECT *,(((acos(sin((@latitude*pi()/180)) * sin((Latitude*pi()/180))+cos((@latitude*pi()/180)) * cos((Latitude*pi()/180)) * cos(((@longitude - Longitude)*pi()/180))))*180/pi())*60*1.1515*1.609344) as distance FROM Distances) t
WHERE distance <= @distance

@ широта и @longitude - широта и долгота точки. Широта и долгота являются столбцами таблицы расстояний. Значение пи составляет 22/7

Answer 3

Расширения PostgreSQL ГИС могут быть полезны - поскольку в нем уже может быть реализована большая часть функций, о которых вы думаете.

Answer 4

Попробуйте это для хорошего решения: Поиск геолокации

Answer 5

Танк Йогихостинг

У меня в базе данных есть несколько таблиц из Open Streep Maps, и я успешно проверил.

Дистанционная работа в метрах.

SET @orig_lat=-8.116137;
SET @orig_lon=-34.897488;
SET @dist=1000;

SELECT *,(((acos(sin((@orig_lat*pi()/180)) * sin((dest.latitude*pi()/180))+cos((@orig_lat*pi()/180))*cos((dest.latitude*pi()/180))*cos(((@orig_lon-dest.longitude)*pi()/180))))*180/pi())*60*1.1515*1609.344) as distance FROM nodes AS dest HAVING distance < @dist ORDER BY distance ASC LIMIT 100;

Answer 6

Как уже упоминалось в biziclop, какое-то дерево метрических пространств, вероятно, будет вашим лучшим вариантом.У меня есть опыт использования kd-деревьев и quad-деревьев для выполнения таких запросов диапазона, и они удивительно быстрые;их тоже не так сложно написать.Я бы посоветовал взглянуть на одну из этих структур, поскольку они также позволяют вам ответить на другие интересные вопросы, такие как «какая точка в моем наборе данных ближе к этой другой точке?»

Answer 7

Вам могут пригодиться эти вопросы:

• Формулы для расчета географической близости
• Максимальная длина десятичной широты / долготы Градус?

Answer 8

Вам нужен пространственный поиск.Вы можете использовать Solr Пространственный поиск .Он также имеет встроенный тип данных lat / long, проверьте здесь .

Answer 9

Поскольку вы говорите, что любой язык приемлем, естественным выбором является PostGIS:

SELECT * FROM places
WHERE ST_DistanceSpheroid(geom, $location, $spheroid) < $max_metres;

Если вы хотите использовать базовые данные WGS, вы должны установить $spheroid на 'SPHEROID["WGS 84",6378137,298.257223563]'

Предполагая, что вы проиндексировали places по столбцу geom, это должно быть достаточно эффективным.

Answer 10

вы можете проверить это уравнение я думаю, что это поможет

SELECT id, ( 3959 * acos( cos( radians(37) ) * cos( radians( lat ) ) * cos( radians( lng ) - radians(-122) ) + sin( radians(37) ) * sin( radians( lat ) ) ) ) AS distance FROM markers HAVING distance < 25 ORDER BY distance LIMIT 0 , 20;