Мне нужно реализовать геометрический поиск геометрии в моем приложении, но я очень смущен относительно правильной формулы для использования. После некоторых поисков в Интернете и в StackOverflow я обнаружил, что решения:
Вариант № 3 действительно не вариант для меня ATM. Теперь я немного смущен, так как всегда, хотя Формула расстояний на большие расстояния и Формула Хаверсина были синонимами, но, видимо, я был неправ?
Формула Хаверсина http://img.ruphp.com/php/30shbn6.png
Вышеупомянутый снимок экрана был взят из удивительного документа Geo (proximity) Search with 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. Может ли кто-нибудь объяснить мне различия между приведенными выше формулами?
Я ценю ваше понимание этих вопросов.
Основываясь на theonlytheory ответа, я протестировал следующие Формулы расстояния по Большому кругу:
Формула Винченти мертва медленно, однако она довольно точна (до 0,5 мм) .
Формула Хаверсина намного быстрее, чем Формула Vincenty , я смог запустить 1 миллион расчетов за 6 секунд, что в значительной степени приемлемо для моих нужд.
Сферический закон Формулы Косинеса показал, что он почти в два раза быстрее, чем Формула Хаверсина, а разница точности – это пренебрежительность для большинства случаев использования.
Вот несколько тестовых мест:
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 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 – Оперный театр, Сидней:
11 939 773.640 meters 11 952 717.240 meters 11 952 717.240 meters Как вы видите, нет заметной разницы между Формулой Хаверсина и Сферическим законом Косинеса, однако оба имеют смещение расстояния до 22 километров по сравнению с Формулой Винценти, потому что оно использует эллипсоидальное приближение Земли вместо сферического.
Закон Косинеса и Формула Хаверсина дадут одинаковые результаты, предполагая машину с бесконечной точностью. Формула Хаверсина более устойчива к ошибкам с плавающей запятой. Тем не менее, сегодняшние машины имеют двойную точность порядка 15 значащих цифр, и закон косинусов может работать для вас отлично. Обе эти формулы предполагают сферическую землю, тогда как итеративное решение Висенти (наиболее точное) предполагает эллипсоидальную Землю (на самом деле земля не является даже эллипсоидом – это геоид). Некоторые ссылки: http://www.movable-type.co.uk/scripts/gis-faq-5.1.html
Это становится лучше: обратите внимание на широту, которая будет использоваться в законе косинусов, а также Хаверсине – геоцентрическая широта, которая отличается от геодезической широты. Для сферы эти два одинаковы.
Какой из них наиболее быстрый для вычисления?
В порядке от самых быстрых до самых медленных: закон косинусов (5 триггерных вызовов) -> haversine (включает sqrt) -> Vicenty (нужно решить эту итеративно в цикле for)
Какой из них наиболее точным?
Vicenty.
Какой из них лучше, если учитывать скорость и точность?
Если ваш проблемный домен таков, что для расстояний, которые вы пытаетесь вычислить, земля может считаться плоской, тогда вы можете разработать (я не буду приводить подробностей) формулу формы x = kx * разницу в долготе , y = ky * разность широт. Тогда расстояние = sqrt (dx dx + dy dy). Если ваш проблемный домен таков, что его можно решить с помощью квадрата расстояния, вам не придется брать sqrt, и эта формула будет такой же быстрой, как вы, возможно, получите. У этого есть дополнительное преимущество, что вы можете рассчитать векторное расстояние – x – расстояние в восточном направлении, а y – расстояние в северном направлении. В противном случае, экспериментируйте с 3 и выберите то, что лучше всего работает в вашей ситуации.
Итак, вы хотите:
Хитрость в том, что вам не нужно точно вычислять большое расстояние круга! Вы можете делать с любой функцией от пары точек до реального значения, которое строго растет с большим расстоянием между точками . Есть много таких функций, и некоторые из них намного быстрее вычисляются, чем различные формулы для точного большого расстояния круга. Одной из таких функций является евклидово расстояние в 3D. Преобразование широты и долготы в трехмерную точку на сфере не включает в себя обратные тригонометрические функции.
Когда у вас есть x, Y, Z, вы можете понять, что вам действительно не нужно расстояние от p0 до вашей точки, потому что вы также можете использовать расстояние от касательной плоскости к p0. Это расстояние также строго растет с большим расстоянием круга и вычисляется из X, Y, Z как линейная комбинация – даже квадратный корень не требуется. Вам просто нужно предварительно рассчитать коэффициенты и расстояние отсечки, соответствующее желаемому большому расстоянию круга.