Формулы для расчета географической близости
мне нужно реализовать поиск гео близости в моем приложении, но я очень смущен относительно правильной формулы для использования. После некоторых поисков в интернете и в StackOverflow я обнаружил, что решения являются:
- использовать Формула Гаверсинуса
использовать Формула Расстояния Большого Круга- использовать Пространственная Поисковая Система в базе
Формула Haversine http://i46.tinypic.com/30shbn6.png
приведенный выше снимок экрана был взят из awesome Гео (близость) поиск с MySQL бумага, и использует следующие функции:
ASIN, SQRT, POWER, SIN, PI, COS
я также видел варианты от та же формула (сферический закон косинусов), вот так:
(3956 * ACOS(COS(RADIANS(o_lat)) * COS(RADIANS(d_lat)) * COS(RADIANS(d_lon) - RADIANS(o_lon)) + SIN(RADIANS(o_lat)) * SIN(RADIANS(d_lat))))
использует следующие функции:
ACOS, COS, RADIANS, SIN
я не эксперт в математике, но эти формулы одинаковы? Я наткнулся на некоторые больше вариаций и формул (например,сферический закон косинусов и Vincenty этоформулы - который, кажется, самый точный), и это заставляет меня еще больше запутаться...
мне нужно выбрать хорошую формулу общего назначения для реализации в PHP / MySQL. Может ли кто-нибудь объяснить мне различия между формулами, которые я упомянул выше?
- какой из них самый быстрый для вычисления?
- какой из них обеспечивает наиболее точную результаты?
- какой из них является лучшим с точки зрения скорости / точности результатов?
я ценю ваше понимание этих вопросов.
на основе ответа theonlytheory я проверил следующие формулы расстояния Большого Круга:
- Формула Vincenty
- Формула Гаверсинуса
- сферический закон косинусов
The Формула Vincenty однако он очень медленный это довольно точно (до 0,5 мм).
The Формула Гаверсинуса это намного быстрее, чем Формула Vincenty, я смог запустить 1 миллион вычислений примерно за 6 секунд, что в значительной степени приемлемо для моих потребностей.
The сферический закон косинусов Формула показала почти в два раза быстрее как Формула Гаверсинуса, и разница в точности пренебрежение для большинства случаев использования.
вот некоторые тестовые места:
-
Google HQ (
37.422045,-122.084347) -
Сан-Франциско (
37.77493,-122.419416) -
Эйфелева Башня, Франция (
48.8582,2.294407) -
Оперный Театр, Сидней (
-33.856553,151.214696)
Google HQ-Сан-Франциско, Ка:
- Vincenty Формуле:
49 087.066 meters - Haversine Формуле:
49 103.006 meters - косинусов:
49 103.006 meters
Google HQ-Эйфелева башня, Франция:
- Vincenty Формуле:
8 989 724.399 meters - Haversine Формуле:
8 967 042.917 meters - косинусов:
8 967 042.917 meters
Google HQ-Opera House, Сидней:
- Vincenty Формуле:
11 939 773.640 meters - Haversine Формуле:
11 952 717.240 meters - косинусов:
11 952 717.240 meters
Как видите есть нет заметной разницы между Формула Гаверсинуса и косинусов, однако оба расстояние смещает до 22 километров по сравнению с Формулой Винсенти, потому что она использует эллипсоид приближение земли вместо сферического.
2 ответа:
закон косинусов и Формула Гаверсинуса будут давать идентичные результаты при условии машины с бесконечной точностью. Формула Гаверсинуса более устойчиво к плавающей ошибки точек. Тем не менее, сегодняшние машины имеют двойную точность порядка 15 значимых цифр, и закон косинусов может работать просто отлично для вас. Обе эти формулы предполагают сферическую землю, тогда как итерационное решение Висенти (наиболее точное) предполагает эллипсоидную землю (на самом деле Земля даже не эллипсоид - это геоид). Несколько ссылок: http://www.movable-type.co.uk/scripts/gis-faq-5.1.html
это становится лучше: обратите внимание, что широта, которая будет использоваться в законе косинусов, а также Haversine-это геоцентрическая широта, которая отличается от геодезической широты. Для сферы это одно и то же.
какой из них быстрее всего вычислить?
в порядке от самого быстрого к самому медленному являются: закон косинусов (5 тригонометрии. звонки) - > haversine (включает в себя sqrt) - > Vicenty (должны решить это итеративно в цикле for)
какой из них самый точный?
.Что лучше, когда скорость и точность считаются?
Если ваша проблемная область такова, что для расстояний, которые вы пытаетесь вычислить, Земля может рассматриваться как плоская, то вы можете разработать (я не буду приводить подробности) формулу вида x = kx * разница в долготе, y = ky * разница в широте. Затем расстояние = sqrt (dxdx + dydy). Если ваша проблемная область такова, что ее можно решить с помощью квадрата расстояния, то вам не нужно будет принимать sqrt, и эта формула будет так же быстро, как вы можете получить. Он имеет дополнительное преимущество, что вы можете вычислить вектор расстояние-x-расстояние в восточном направлении, а y-расстояние в северном направлении. В противном случае поэкспериментируйте с 3 и выберите то, что лучше всего работает в вашей ситуации.
Итак, вы хотите:
- сортировать записи по расстоянию от p0
- выберите только записи, расстояние которых от p0 меньше r
хитрость в том, что вам точно не нужно вычислять расстояние большого круга для этого! Вы можете сделать с любой функция от пары точек до реального значения что строго растет с большим расстоянием круга между точками. Есть много таких функций, и некоторые из них намного быстрее чтобы вычислить, чем различные формулы для точного расстояния большого круга. Одна из таких функции является Эвклидово расстояние в 3D. Преобразования широты и долготы в 3D-точки На сфере не предполагает обратных тригонометрических функций.
Как только у вас есть x,Y,Z, вы можете понять, что вам на самом деле не нужно расстояние от p0 до вашей точки, потому что вы также можете использовать расстояние от касательной плоскости в p0. Это расстояние также строго растет с расстоянием большого круга и является вычисляется из X,Y, Z как линейная комбинация - даже квадратный корень не требуется. Вам просто нужно предварительно вычислить коэффициенты и расстояние отсечки, которое соответствует желаемому расстоянию большого круга.