Формулы для расчета географической близости

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

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

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

http://i46.tinypic.com/30shbn6.png

Приведенный выше снимок экрана был взят из удивительного поиска 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
  • Формула 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 километров по сравнению с формулой Винсенти, поскольку она использует эллипсоидальное приближение Земли вместо сферического.

Источник

2 ответа

Решение

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

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

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

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

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

Vicenty.

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

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

Источник

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

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

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

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

Источник
Другие вопросы по тегам