Формулы для вычисления геопространственности

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

Используйте формулу Haversine
Используйте формулу расстояния большого круга
Используйте систему пространственного поиска в базе данных

Вариант № 3 действительно не вариант для меня банкомат. Теперь я немного сбит с толку, поскольку всегда считал, что Формула Великого Круга и Формула Хаверсин были синонимами, но, видимо, я ошибался?

Приведенный выше снимок экрана был взят из удивительного поиска Geo (близости) с бумагой 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

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

Мне нужно выбрать хорошую формулу общего назначения для реализации в PHP/MySQL. Может кто-нибудь объяснить мне различия между формулами, которые я упомянул выше?

Какой из них самый быстрый для вычисления?
Какой из них дает наиболее точные результаты?
Какой из них является лучшим с точки зрения скорости/точности результатов?

Я ценю ваше понимание этих вопросов.

Основываясь на единственном теоретическом ответе, я проверил следующие формулы расстояния большого круга:

Винсенти Формула
Формула Haversine
Сферический закон косинусов

Формула Винсенти очень медленная, но довольно точная (до 0,5 мм).

Формула Хаверсайна намного быстрее, чем Формула Винсенти, я смог выполнить 1 миллион вычислений примерно за 6 секунд, что вполне приемлемо для моих нужд.

Сферическая формула закона косинусов показала, что она почти в два раза быстрее формулы Хаверсина, а разница в точности - пренебрежение для большинства случаев использования.

Вот несколько тестовых локаций:

Google HQ (37.422045, -122.084347)
Сан-Франциско, Калифорния (37.77493, -122.419416)
Эйфелева башня, Франция (48.8582, 2.294407)
Оперный театр, Сидней (-33.856553, 151.214696)

Google HQ - Сан-Франциско, Калифорния:

49 087.066 meters Формула: 49 087.066 meters
Формула Haversine: 49 103.006 meters
Сферический закон косинусов: 49 103.006 meters

Google HQ - Эйфелева башня, Франция:

Винсенти Формула: 8 989 724.399 meters
Формула Haversine: 8 967 042.917 meters
Сферический закон косинусов: 8 967 042.917 meters

Google HQ - Opera House, Сидней:

Винсенти Формула: 11 939 773.640 meters
Формула Haversine: 11 952 717.240 meters
Сферический закон косинусов: 11 952 717.240 meters

Как вы можете видеть, нет заметной разницы между формулой Хаверсин и сферическим законом косинусов, однако оба имеют смещение расстояний до 22 километров по сравнению с формулой Винсенти, поскольку она использует эллипсоидальное приближение Земли вместо сферического.

Ответ 1

Закон Косинеса и Формула Хаверсина дадут одинаковые результаты, предполагая машину с бесконечной точностью. Формула Хаверсина более устойчива к ошибкам с плавающей запятой. Однако сегодня машины имеют двойную точность порядка 15 значащих цифр, и закон косинусов может отлично работать для вас. Обе эти формулы предполагают сферическую землю, тогда как итеративное решение Vicenty (наиболее точное) предполагает эллипсоидальную землю (на самом деле земля не является даже эллипсоидом - это геоид). Некоторые ссылки: http://www.movable-type.co.uk/scripts/gis-faq-5.1.html

Получается лучше: обратите внимание на широту, которая будет использоваться в законе косинусов, а также Haversine - геоцентрическая широта, которая отличается от геодезической широты. Для сферы эти два одинаковы.

Какой из них наиболее быстрый для вычисления?

В порядке от самого быстрого до самого медленного: закон косинусов (5 триггерных вызовов) → haversine (включает sqrt) → Vicenty (нужно решить эту итеративно в цикле for)

Какой из них наиболее точным?

Vicenty.

Какой из них лучше, когда скорость и точность считаются?

Если ваша проблемная область такова, что для расстояний, которые вы пытаетесь вычислить, земля может считаться плоской, тогда вы можете решить (я не буду приводить подробностей) формулу формы x = kx * разница в долготе, y = ky * разница в широте. Тогда distance = sqrt (dxdx + dydy). Если ваш проблемный домен таков, что его можно решить с помощью квадрата расстояния, вам не придется брать sqrt, и эта формула будет такой же быстрой, как вы, возможно, получите. У этого есть дополнительное преимущество, что вы можете вычислить расстояние вектор - x - расстояние в восточном направлении, а y - расстояние в северном направлении. В противном случае, экспериментируйте с 3 и выберите то, что лучше всего работает в вашей ситуации.

Ответ 2

Итак, вы хотите:

сортировка записей по расстоянию от p0
выберите только записи, расстояние от которых p0 меньше r

Фокус в том, что вам не нужно просто вычислять большое расстояние круга для этого! Вы можете использовать любую функцию от пары точек до реального значения , которое строго растет с большим расстоянием между точками. Есть много таких функций, и некоторые из них намного быстрее вычисляются, чем различные формулы для точного большого расстояния круга. Одной из таких функций является евклидово расстояние в 3D. Преобразование широты и долготы в трехмерную точку на сфере не включает в себя обратные тригонометрические функции.

Как только у вас есть x, Y, Z, вы можете понять, что на самом деле вам не нужно расстояние от p0 до вашей точки, потому что вы также можете использовать расстояние от касательной плоскости к p0. Это расстояние также строго растет с большим расстоянием круга и вычисляется из X, Y, Z как линейная комбинация - даже квадратный корень не требуется. Вам просто нужно прекомпретировать коэффициенты и расстояние отсечки, которое соответствует желаемому расстоянию большого круга.