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

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

67 голосов
/ 19 января 2010

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

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

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

Haversine Formula

Приведенный выше снимок экрана был сделан с удивительной Geo (близости) поиска с бумагой MySQL и используетследующие функции: 

ASIN, SQRT, POWER, SIN, PI, COS

Я также видел варианты от той же формулы ( Сферический закон косинусов ) , как этоone: 

(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.Может ли кто-нибудь объяснить мне различия между формулами, которые я упомянул выше?

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

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

На основании theonlytheory ответа Я проверил следующие формулы расстояний большого круга:

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

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

Формула Haversine намного быстрее, чем Формула Винсенти, я смог выполнить 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 103.006 meters
  • Сферический закон косинусов: 49 103.006 meters

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

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

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

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

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

Ответы [ 2 ]

35 голосов
/ 20 января 2010

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

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

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

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

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

Vicenty.

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

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

11 голосов
/ 29 марта 2012

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

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

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

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

...