Dlaczego prawo cosinusów jest korzystniejsze niż haversine przy obliczaniu odległości między dwoma punktami szerokość-długość geograficzna?

41

W rzeczywistości, kiedy Sinnott opublikował formułę haverine, precyzja obliczeniowa była ograniczona. Obecnie JavaScript (i większość współczesnych komputerów i języków) używa 64-bitowych liczb zmiennoprzecinkowych IEEE 754, które zapewniają 15 znaczących liczb precyzji. Z tą precyzją proste sferyczne prawo cosinusów ( cos c = cos a cos b + sin a sin b cos C) daje dobrze uwarunkowane wyniki aż do odległości tak małych, jak około 1 metra. W związku z tym w większości przypadków prawdopodobnie warto zastosować prostsze prawo cosinusów lub dokładniejszą elipsoidalną formułę Vincenty'ego zamiast haverine! (mając na uwadze poniższe uwagi dotyczące ograniczeń dokładności modelu sferycznego).
Źródło: http://www.movable-type.co.uk/scripts/latlong.html

Jaki jest powód, dla którego prawo cosinusów jest bardziej preferowane?

Uwaga: cytowany tekst został zaktualizowany przez autora, jak wspomniano poniżej .

Afriza N. Arief
źródło
10
W jaki sposób prawo cosinusów jest „lepsze”? Możemy odpowiedzieć na to na dwa sposoby: dla komputera i programisty. W przypadku komputera formuła haverine wykorzystuje mniej funkcji wyzwalania, ale wymaga dwóch pierwiastków kwadratowych. Zatem dla wydajności obliczeniowej jest to losowanie. Dla programisty formuła haverine jest nieco dłuższa. Jednak formuła prawa cosinusów wymaga implementacji ACos, co jest postrzegane nieco rzadziej niż implementacja ATan. Ponadto, aby napisać kod kuloodporny , musisz sprawdzić, czy ACos nie zawiedzie. Tylko z tego powodu powinniśmy preferować haverine.
whuber
2
Właśnie zaimplementowałem haversine i cosinus w Pythonie. Na tym komputerze haversine pobiera 3,3 μs, a cosinus - 2,2 μs, co jest dość znaczące, jeśli musisz zrobić wiele z nich
gnibbler
1
Dziękujemy wszystkim za dobre obserwacje i informacje. Mam nadzieję, że tekst cytowany w pytaniu jest bardziej obiektywny i pomocny.
ChrisV
@ChrisV, dzięki za aktualizację! Przeniosłem to na komentarz, ponieważ nie jest to bezpośrednia odpowiedź na pytanie, dziękuję za wspaniałą stronę.
scw

Odpowiedzi:

48

Problem wskazuje słowo „dobrze uwarunkowane”. To kwestia arytmetyki komputerowej, a nie matematyki.

Oto podstawowe fakty do rozważenia:

  1. Jeden radian na ziemi ma prawie 10 ^ 7 metrów.

  2. Funkcja cosinus dla argumentów x w pobliżu 0 jest w przybliżeniu równa 1 - x ^ 2/2.

  3. Zmienna zmiennoprzecinkowa podwójnej precyzji ma około 15 cyfr dziesiętnych precyzji.

Punkty (2) i (3) oznaczają, że gdy x wynosi około jednego metra lub 10 ^ -7 radianów (punkt 1), prawie cała precyzja jest tracona: 1 - (10 ^ -7) ^ 2 = 1 - 10 ^ - 14 jest obliczeniem, w którym pierwsze 14 z 15 cyfr znaczących wszystkie są anulowane, pozostawiając tylko jedną cyfrę reprezentującą wynik. Odwracanie tego (co robi odwrotny cosinus „acos”) oznacza, że obliczanie acos dla kątów odpowiadających odległościom metra nie może być wykonane z żadną znaczącą dokładnością. (W niektórych złych przypadkach utrata precyzji daje wartość, w której acos nie jest nawet zdefiniowany, więc kod się zepsuje i nie da odpowiedzi, bezsensownej odpowiedzi lub zawiesi maszynę.) Podobne uwagi sugerują, że należy unikać używania odwrotnego cosinusa jeśli występują odległości mniejsze niż kilkaset metrów, w zależności od tego, ile precyzji jesteś gotów stracić.

Rolą acos w naiwnej formule prawa cosinusów jest konwersja kąta na odległość. Tę rolę odgrywa atan2 w formule haverine. Styczna małego kąta x jest w przybliżeniu równa samemu x . W konsekwencji odwrotna styczna liczby, która jest w przybliżeniu tą liczbą, jest obliczana zasadniczo bez utraty precyzji. Właśnie dlatego formuła haversine, choć matematycznie równoważna zasadzie formuły cosinus, jest znacznie lepsza dla małych odległości (rzędu 1 metra lub mniejszej).

Oto porównanie dwóch formuł wykorzystujących 100 losowych par punktowych na kuli ziemskiej (przy użyciu obliczeń podwójnej precyzji Mathematica).

alternatywny tekst

Widać, że dla odległości mniejszych niż około 0,5 metra obie formuły się różnią. Powyżej 0,5 metra zwykle się zgadzają. Aby pokazać, jak ściśle się ze sobą zgadzają, następny wykres pokazuje stosunki prawa cosinusów: wyniki haverine dla kolejnych 100 losowych par punktowych, przy czym ich szerokości i długości geograficzne różnią się losowo o maksymalnie 5 metrów.

alternatywny tekst

To pokazuje, że prawo formuły cosinus jest dobre do 3-4 miejsc po przecinku, gdy odległość przekroczy 5-10 metrów. Liczba miejsc dziesiętnych dokładności rośnie kwadratowo; tak więc przy 50-100 metrach (jeden rząd wielkości) otrzymujesz dokładność 5-6 dp (dwa rzędy wielkości); na 500-1000 metrów dostajesz 7-8 dp itp.

Whuber
źródło
Czy jest jakiś tani test - np. delta latitude > .1 || delta longitude > .1Aby dynamicznie wybrać cosinus (dla dużych) lub haversine (dla małych odległości)? Aby uzyskać najlepszą wydajność i dobrą precyzję.
Anony-Mousse,
@ Anony-Mousse Obie formuły mogą być wyłączone o kilka dziesiątych jednego procenta dla odległości jednej czwartej na całym świecie, więc do tego czasu nie będziemy się martwić o precyzję! Dlatego każdy test, który może odróżnić punkty bliskie (kilkaset metrów) od prawie przeciwległych punktów (około 20 milionów metrów) od wszystkiego pomiędzy nimi, powinien wystarczyć.
whuber
Czy atan2oferuje przewagę liczbową asin? Widziałem testy porównawcze, gdzie atan2były 2-3 razy wolniejsze niż asini potrzebujemy też drugiego sqrt.
Erich Schubert,
@Erich Nie zbadałem różnicy, ale zauważ, że asinjest to w zasadzie to samo acosi dlatego cierpi z powodu tej samej utraty precyzji dla niektórych wartości - w tym przypadku dla argumentów w pobliżu 1 i -1. Zasadniczo atan2nie ma tego problemu.
whuber
To byłoby na bardzo dużych odległościach? Ciekawe wydaje się połączenie powyższej sugestii @ Anony-Mousse.
Erich Schubert,
6

Historyczny przypis:

Hversine był sposobem na uniknięcie dużych błędów zaokrągleń w obliczeniach takich jak

1 - cos(x)

gdy x jest małe. Jeśli chodzi o haverine mamy

1 - cos(x) = 2*sin(x/2)^2
           = 2*haversin(x)

i 2 * sin (x / 2) ^ 2 można dokładnie obliczyć, nawet gdy x jest małe.

W dawnych czasach formuła haverine miała dodatkową zaletę polegającą na unikaniu dodawania (co wiązało się z wyszukiwaniem antylogicznym, dodawaniem i przeglądaniem logów). Mówi się, że wzór trygonometryczny, który obejmował tylko mnożenia, ma „postać logarytmiczną”.

W dzisiejszych czasach stosowanie formuł haverine jest nieco anachroniczne. Możliwe, że kąt x jest wyrażony w kategoriach sin(x)i cos(x)(i x może nie być wyraźnie znany). W takim przypadku obliczanie 1 - cos(x)za pomocą formuły haversine wymaga arcus tangens (aby uzyskać kąt x), zmniejszenie o połowę (aby uzyskać x/2), sinus (aby uzyskać sin(x/2)), kwadrat (aby uzyskać sin(x/2)^2) i ostateczne podwojenie. O wiele lepiej jest używać oceniania

1 - cos(x) = sin(x)^2/(1 + cos(x))

co nie wymaga oceny funkcji trygonometrycznych. (Oczywiście używaj prawej strony tylko wtedy cos(x) > 0, gdy ; w przeciwnym razie możesz używać 1 - cos(x)bezpośrednio.)

cffk
źródło
1

Formułę cosinus można zaimplementować w jednym wierszu:

  Distance = acos(SIN(lat1)*SIN(lat2)+COS(lat1)*COS(lat2)*COS(lon2-lon1))*6371

Formuła haverine ma wiele linii:

  dLat = (lat2-lat1)
  dLon = (lon2-lon1)
  a = sin(dLat/2) * sin(dLat/2) + cos(lat1) * cos(lat2) * sin(dLon/2) * sin(dLon/2)
  distance = 6371 * 2 * atan2(sqrt(a), sqrt(1-a))

Matematycznie są identyczne, więc jedyną różnicą jest praktyczność.

Tom W.
źródło
Podczas gdy oryginalna Haversine nie używa atan2formuły związanej z komputerem , nic nie stoi na przeszkodzie , aby przepisać 4 linie powyżej w jedną formułę.
Arjan
@Arjan, to prawda, ale to byłoby nieefektywne, ponieważ trzeba by obliczyć dwukrotnie. Istotne jest, aby formuła obejmowała zarówno Sqrt (a), jak i Sqrt (1-a), ponieważ chociaż jeden z nich będzie liczbowo niestabilny na bardzo małych lub bardzo dużych odległościach, drugi nie będzie: to sprawia, że ​​to podejście działa.
whuber
To prawda, @whuber, ale wciąż wątpię, czy liczba linii sprawiłaby, że wybrałem jedną z nich. (I jak już wyjaśniłeś w swojej odpowiedzi, istnieją o wiele ważniejsze powody, aby je faworyzować.)
Arjan
3
@Arjan Zgadzam się. Pierwszym priorytetem powinna być adekwatność kodu do zadania programistycznego. Następnie umieściłbym jasność: to znaczy czytelność, łatwość konserwacji i pisanie dokumentacji. W przypadku braku takiego kontekstu liczenie wierszy kodu jest bez znaczenia.
whuber
1
atan2(sqrt(a), sqrt(1-a))jest taki sam, jakasin(sqrt(a))
user102008,