Как определить входит ли геоточка(с широтой, долготой) в радиус?

Question

[Gasoid]

Т.е. есть окружность на карте с центром, например [51.526613503445766, 46.02093849218558]

есть радиус — 5 км.



Требуется определить какие точки входят в этот радиус, какие нет.



Библиотеку по определению дистанции нашел.

code.google.com/p/geopy

UPD: используйте библиотеку) решение в лоб будет работать плохо

Answer 1

[Gasoid]

Вообщем алгоритм такой, есть база с пользователями, у каждого пользователя есть поля координат lat, lon
нужно например найти всех пользователей в квадрате 20 км

пример для django

        dist = 20 #дистанция 20 км
        mylon = 51.5289156201 # долгота центра
        mylat = 46.0209384922 # широта 
        lon1 = mylon-dist/abs(math.cos(math.radians(mylat))*111.0) # 1 градус широты = 111 км
        lon2 = mylon+dist/abs(math.cos(math.radians(mylat))*111.0)
        lat1 = mylat-(dist/111.0)
        lat2 = mylat+(dist/111.0)
        profiles = UserProfile.objects.filter(lat__range=(lat1, lat2)).filter(lon__range=(lon1, lon2))

Comments

[Алексей Гусейнов]

Плохое решение. Такой запрос может использовать индекс по одной координате, но будет вынужден сделать полный перебор по второй координате. Выхода два:
Использовать георасширение для СУБД и использовать пространственный индекс из него. Это самый правильный вариант.
Если это невозможно, то надо считать geohash от координат, класть в базу и делать запрос, вытаскивающий объекты с geohash'ем, попадающим в нужные диапазоны (таких диапазоно может быть до четырех).

[0xC0CAC01A]

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

[Алексей Гусейнов]

Если geohash использовать, то логарифмический, а если так, как предложил автор, то линейный.

[Gasoid]

как вычислять geohash?

[Developer]

Это неверное решение.
Проверь на координатах, близких к полюсам.
Там нет никакого квадрата.

Answer 2

[Skull]

Зачем библиотека? Есть формула в 1 строку, определяет расстояние в метрах.
$distance = 2 * asin(sqrt( pow(sin(deg2rad( ($lat1-$lat2) / 2)), 2) +
cos(deg2rad($lat1)) * cos(deg2rad($lat2)) *
pow(sin(deg2rad(($lng1- $lng2) / 2)), 2))) * 6378245;

Если точки в БД хранятся — выбирайте не все, а только в определнных пределах. А для них уже вычислять расстояние

Comments

[couatl]

Можно вписать окружность в квадрат и не рассматривать то, что в этот квадрат не входит.
Говорить о принадлежности к квадрату легче.

[Gasoid]

да можно поподробнее, тоже об этом подумал

[Gasoid]

т.е. определяем точки квадрата с нашим центром, а конкретно как точки определить?

Answer 3

[alexmuz]

Считаете расстояние от точки до центра вашей окружности, если расстояние меньше или равно 5 км, значит входит, если больше значит не входит.

Comments

[Gasoid]

а больше никак?
трудозатратный вариант

[alexmuz]

У вас так много точек или почему трудозатратный? Как у вас точки хранятся? В БД, если да то в какой? В mongodb, например, есть индекс www.mongodb.org/display/DOCS/Geospatial+Indexing/, с помощью которого можно очень быстро выбирать все точки в заданном радиусе от заданных координат.
Вообще, если вы хотите получить квалифицированный ответ на ваш вопрос, то более подробно опишите что вам нужно.

[Gasoid]

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

Answer 4

[Gasoid]

По оптимизации поиска по вхождению точки в квадрат для Mysql
www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL

Answer 5

[Александр Скакунов]

Есть маленькая, но всё-таки разница между «входит в радиус» и «входит в квадрат». Квадратное решение проще, для него вообще серьёзная ГИС-артиллерия не нужна, да и работает молниеносно.

Делается это так:
0. Предполагаю, что координаты точки в радианах у вас хранятся в базе данных, в полях lat и lng.
1. Создаёте один индекс на оба поля для ускорения запросов.
2. В коде переводите 10 км в радианы (кажется, в одном метре 0,1988 радиан, но проверьте).
3. Чтобы определить, какие точки входят в квадрат со стороной 10 км с заданной точкой в центре, пишете такой запрос:

SET @lat = 51.526613503445766; # дано в условии
SET @lng = 46.02093849218558;
SET @half= [10 км в радианах] / 2 ;


SELECT id
FROM points
WHERE lat BETWEEN @lat - @half AND @lat + @half
  AND lng BETWEEN @lng - @half AND @lng + @half;

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

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

Comments

[Gasoid]

спс

[Николай Кокоулин]

Это решение верно только для экватора.
Для любой другой широты радианы долготы и широты различаются

Answer 6

[Алексей Гусейнов]

Не с этого надо начинать. Каковы требования по точности и скорости работы алгоритма? Много ли точек надо проверять на вхождение в одну окружность? Все ла равно вам на сплющенность Земли, а также на рельеф? Понимаете ли вы, что окружность на карте не будет выглядеть, как окружность?

Answer 7

[iwitaly]

Если правильно вас понял, просто из уравнения окружности (x — x_0)^2 + (y — y_0)^2 <= R^2 где x_0 и y_0 — координаты центра в вашей системе координат. Просто берете координаты точки и проверяете.

Comments

[Дядька Серёжа]

Подскажите почему данная формула не работает, с географическими координатами не так все просто?

Answer 8

[webmeddoc]

Ответил на фрилансим , вкратце это будет выглядеть так:

import  math
dist = math.hypot(x-Sx, y-Sy)
if  dist < r: print("Входит")
else: print("Не входит")

Answer 9

[spleanfan]

так нужно отвечать тут или на фл?

Answer 10

[Hoksmur]

Пользоваться или нет данными внешних ресурсов, как то от Google или другое - решать ТС.
Если не пользоваться или допустимо взять сферу за поверхность Земли, то надо считать длину дуги на сфере между двумя точками. Формула в вики находится легко, есть даже по широте и долготе
Можно даже от тригонометрии избавится, остатвив +-*/ если допустима линейная аппроксимация.