Формулы для вычисления гео-близости
Я должен реализовать Гео-поиск с расстоянием в своем приложении, но я очень смущен относительно корректной формулы для использования. После некоторых поисков в сети и в StackOverflow я нашел, что решения:
- Используйте формулу Haversine
Используйте большую круговую формулу расстояния- Используйте пространственную поисковую систему в базе данных
Опция № 3 является действительно не опцией для меня ATM. Теперь я немного смущен так как я всегда, хотя это Большая Круговая Формула Расстояния и Формула Haversine было синонимично, но по-видимому я был неправ?
Вышеупомянутый снимок экрана был взят от потрясающего Гео-(близость) Поиск с бумагой 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
- Формула Haversine
- Сферический закон косинусов
Формула Vincenty мертва медленный, однако это довольно точно (вниз к 0,5 мм).
Формула Haversine является путем быстрее, чем Формула Vincenty, я смог выполнить 1 миллион вычислений приблизительно через 6 секунд, который в значительной степени приемлем для моих потребностей.
Сферический Закон Формулы Косинусов показал, чтобы быть почти дважды с такой скоростью, как Формула Haversine, и различием в точности является небрежность для большинства случаев использования.
Вот некоторые тестовые местоположения:
- 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 - оперный театр, Сидней:
- Формула Vincenty:
11 939 773.640 meters - Формула Haversine:
11 952 717.240 meters - Сферический закон косинусов:
11 952 717.240 meters
Поскольку Вы видите, что нет никакого заметного различия между Формулой Haversine и Сферическим Законом Косинусов, однако у обоих есть смещения расстояния целых 22 километра по сравнению с Формулой Vincenty, потому что это использует эллипсоидальное приближение земли вместо сферической.
1 ответ
Вы можете сохранить его Static, но используйте userdata для хранения это Указатель в дополнение к любую другие другие пользовательские задачи, которые вы хотите (например, упаковывая их в структуру), а затем вызовите обратный вызов, специфичный объект от статической версии, вызывая , This-> SomeCallback (где Это - указатель, хранящийся в userdata, конечно).
Закон о косинусах и формуле Гаверина даст идентичные результаты, предполагая машину с бесконечной точностью. Формула Haversine более устойчивая к ошибкам с плавающей точкой. Однако сегодняшние машины имеют двойную точность порядка 15 важных фигур, а закон косинусов может работать просто для вас. Оба эти формулы предполагают сферическую Землю, тогда как итеративный раствор в то время как (наиболее точный) предполагает эллипсоидальную землю (на самом деле земля не является даже эллипсоидом - это геоид). Некоторые ссылки: http://www.movable-type.co.uk/scripts/gis-faq-5.1.html
становится все лучше: обратите внимание на широту, которая будет использоваться в законе косинусов, а также в Haversine Геоцентричная широта, которая отличается от геодезической широты. Для сферы эти два одинаковы.
Какой из них является самым быстрым, чтобы вычислить?
В том порядке, из-за самого самого медленного: закон косинусов (5 триг. Звонки) -> Haversine (включает в себя SQRT) -> Victy (приходится решать это итеративно в цикле для цикла )
Какой из них наиболее точен?
ViCenty.
Какой из них лучше всего, когда скорость и точность рассматриваются?
Если ваш проблемный домен такой, что для расстояний, которые вы пытаетесь рассчитать, земля можно рассматривать как квартиру, тогда вы можете работать (я Не собираюсь дать подробности) формула формы x = kx * разница в долготе, y = ky * разница в широте. Затем расстояние = SQRT (DX DX + DY DY). Если ваш проблемный домен такой, что он может быть решен с квадратом расстояния, то вам не придется принимать SQRT, и эта формула будет так же быстрее, насколько это возможно. Он имеет дополнительное преимущество, которое вы можете рассчитать вектор Vector - x расстояние в восточном направлении, а Y - расстояние в северном направлении. В противном случае экспериментируйте с 3 и выберите, что лучше всего работает в вашей ситуации.