Warum ist das Kosinusgesetz bei der Berechnung der Entfernung zwischen zwei Längen- und Breitengradpunkten dem Haversinus vorzuziehen?

41

Als Sinnott die Haversin-Formel veröffentlichte, war die rechnerische Genauigkeit begrenzt. Heutzutage verwenden JavaScript (und die meisten modernen Computer und Sprachen) 64-Bit-Gleitkommazahlen nach IEEE 754, die 15 signifikante Präzisionszahlen liefern. Mit dieser Präzision liefert das einfache sphärische Gesetz der Kosinusformel ( cos c = cos a cos b + sin a sin b cos C) gut konditionierte Ergebnisse bis zu Entfernungen von nur etwa 1 Meter. In Anbetracht dessen lohnt es sich wahrscheinlich, in den meisten Situationen entweder das einfachere Kosinussatzgesetz oder die genauere ellipsoidale Vincenty-Formel anstelle von Haversin zu verwenden! (Beachten Sie die folgenden Hinweise zu den Genauigkeitsbeschränkungen des sphärischen Modells).
Quelle: http://www.movable-type.co.uk/scripts/latlong.html

Was ist der Grund, warum das Kosinusgesetz vorzuziehen ist?

Hinweis: Der zitierte Text wurde von seinem Autor wie unten erwähnt aktualisiert .

Afriza N. Arief
quelle
10
Wie ist das Cosinusgesetz "vorzuziehen"? Wir können dies auf zwei Arten beantworten: für den Computer und den Programmierer. Für den Computer verwendet die Haversine-Formel weniger Triggerfunktionen, benötigt jedoch zwei Quadratwurzeln. Für die Berechnungseffizienz ist es also ein Fehler. Für den Programmierer ist die Haversine-Formel etwas länger. Das Gesetz der Cosinusformel erfordert jedoch eine ACos-Implementierung, die etwas seltener auftritt als eine ATan-Implementierung. Um einen kugelsicheren Code zu schreiben, müssen Sie außerdem sicherstellen, dass der ACos nicht ausfällt. Allein aus diesem Grund sollten wir Haversin bevorzugen.
whuber
2
Ich habe gerade Haversine und Cosine in Python implementiert. Auf diesem Computer benötigt Haversine 3,3 μs und Cosinus 2,2 μs, was ziemlich wichtig ist, wenn Sie eine Menge von ihnen tun müssen
Gnibbler
1
Vielen Dank an alle für einige gute Beobachtungen und Informationen. Ich habe den in der Frage zitierten Text aktualisiert und hoffe, dass er objektiver und hilfreicher ist.
ChrisV
@ ChrisV, danke für das Update! Ich habe dies in einen Kommentar verschoben, da dies keine direkte Antwort auf die Frage ist. Vielen Dank für Ihre großartige Website.
scw

Antworten:

48

Das Problem wird durch das Wort "gut konditioniert" angezeigt. Es ist eine Frage der Computerarithmetik, nicht der Mathematik.

Hier sind die grundlegenden Fakten zu berücksichtigen:

  1. Ein Bogenmaß auf der Erde überspannt fast 10 ^ 7 Meter.

  2. Die Cosinusfunktion für Argumente x in der Nähe von 0 ist ungefähr gleich 1 - x ^ 2/2.

  3. Gleitkommazahlen mit doppelter Genauigkeit haben eine Genauigkeit von ca. 15 Dezimalstellen.

Die Punkte (2) und (3) implizieren, dass bei x um einen Meter oder 10 ^ -7 Radiant (Punkt 1) fast die gesamte Genauigkeit verloren geht: 1 - (10 ^ -7) ^ 2 = 1 - 10 ^ - 14 ist eine Berechnung, bei der die ersten 14 der 15 signifikanten Ziffern alle gelöscht werden und nur eine Ziffer übrig bleibt, um das Ergebnis darzustellen. Das Umkehren dieses Wertes (wie es der inverse Cosinus "acos" tut) bedeutet, dass die Berechnung von acos für Winkel, die Entfernungen in Metern Länge entsprechen, nicht mit einer sinnvollen Genauigkeit durchgeführt werden kann. (In bestimmten schlimmen Fällen ergibt der Genauigkeitsverlust einen Wert, bei dem acos nicht einmal definiert ist, sodass der Code zusammenbricht und keine Antwort, keine unsinnige Antwort oder keinen Absturz der Maschine liefert.) Ähnliche Überlegungen legen nahe, dass Sie die Verwendung des inversen Kosinus vermeiden sollten Bei Entfernungen von weniger als ein paar hundert Metern hängt es davon ab, wie viel Präzision Sie verlieren möchten.

Die Rolle, die acos in der naiven Kosinussatzformel spielt, besteht darin, einen Winkel in eine Entfernung umzuwandeln. Diese Rolle spielt atan2 in der Haversin-Formel. Die Tangente eines kleinen Winkels x ist ungefähr gleich x selbst. Folglich wird der inverse Tangens einer Zahl, der ungefähr dieser Zahl entspricht, im wesentlichen ohne Genauigkeitsverlust berechnet. Aus diesem Grund ist die Haversinformel, obwohl sie dem Gesetz der Cosinusformel mathematisch äquivalent ist, für kleine Entfernungen (in der Größenordnung von 1 Meter oder weniger) weit überlegen .

Hier ist ein Vergleich der beiden Formeln unter Verwendung von 100 zufälligen Punktpaaren auf dem Globus (unter Verwendung von Mathematics Berechnungen mit doppelter Genauigkeit).

Alt-Text

Sie können sehen, dass die beiden Formeln bei Entfernungen von weniger als 0,5 Metern voneinander abweichen. Oberhalb von 0,5 Metern stimmen sie eher überein. Um zu zeigen, wie eng sie übereinstimmen, werden im nächsten Diagramm die Verhältnisse des Kosinusgesetzes dargestellt: Haversinusergebnisse für weitere 100 zufällige Punktpaare, wobei sich ihre Breiten- und Längengrade zufällig um bis zu 5 Meter unterscheiden.

Alt-Text

Dies zeigt, dass das Gesetz der Kosinusformel bis zu 3-4 Dezimalstellen gilt, sobald der Abstand 5-10 Meter überschreitet. Die Anzahl der Dezimalstellen der Genauigkeit nimmt quadratisch zu; bei 50-100 Metern (eine Größenordnung) erhalten Sie also eine Genauigkeit von 5-6 dp (zwei Größenordnungen); Auf 500-1000 Metern erhalten Sie 7-8 dp usw.

whuber
quelle
Gibt es einen billigen Test - zB delta latitude > .1 || delta longitude > .1um dynamisch entweder Cosinus (für große) oder Haversinus (für kleine Entfernungen) zu wählen? Um die beste Leistung und gute Präzision zu erzielen.
Anony-Mousse
@ Anony-Mousse Beide Formeln können bei Entfernungen von einem Viertel um die Welt um einige Zehntel Prozent abweichen, sodass wir uns bis dahin nicht um Präzision kümmern müssen! Daher sollte jeder Test ausreichen, der enge Punkte (einige hundert Meter) von nahezu diametral gegenüberliegenden Punkten (etwa 20 Millionen Meter) von allem dazwischen unterscheiden kann.
whuber
Bietet atan2numerische Vorteile gegenüber asin? Ich habe Benchmarks gesehen, atan2die 2-3x langsamer waren als asin, und wir brauchen auch eine Sekunde sqrt.
Erich Schubert
@Erich Ich habe den Unterschied nicht untersucht, aber beachte, dass dies asinim Wesentlichen dasselbe ist acosund daher für bestimmte Werte den gleichen Genauigkeitsverlust aufweist - in diesem Fall für Argumente in der Nähe von 1 und -1. Im Prinzip hat atan2das kein Problem.
Whuber
Das wäre bei sehr großen Entfernungen? Das mit dem Vorschlag von @ Anony-Mousse zu kombinieren, scheint dann interessant zu sein.
Erich Schubert
6

Eine historische Fußnote:

Der Haversinus war eine Möglichkeit, große Rundungsfehler bei Berechnungen wie zu vermeiden

1 - cos(x)

wenn x klein ist. In Bezug auf die Haversine haben wir

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

und 2 * sin (x / 2) ^ 2 kann genau berechnet werden, selbst wenn x klein ist.

In früheren Zeiten hatte die Haversin-Formel den zusätzlichen Vorteil, dass eine Addition vermieden wurde (was eine Antilog-Suche, eine Addition und eine Protokollsuche nach sich zog). Eine trigonometische Formel, die nur Multiplikationen enthielt, soll in "logarithmischer Form" vorliegen.

Heutzutage ist die Verwendung der Haversinformeln leicht anachronistisch. Es kann sein, dass der Winkel x in Termen sin(x)und ausgedrückt wird cos(x)(und x möglicherweise nicht explizit bekannt ist). In diesem Fall beinhaltet die Berechnung 1 - cos(x)über die Haversinusformel einen Arkustangens (um den Winkel x zu erhalten x/2), eine Halbierung (um zu erhalten ), einen Sinus (um zu erhalten sin(x/2)), ein Quadrat (um zu erhalten sin(x/2)^2) und eine endgültige Verdopplung. Mit dem Auswerten sind Sie weit besser dran

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

was keine Bewertungen der trigonometrischen Funktionen mit sich bringt. (Verwenden Sie die rechte Seite nur, wenn cos(x) > 0dies der Fall ist 1 - cos(x). Andernfalls können Sie sie direkt verwenden.)

cffk
quelle
1

Die Kosinusformel kann in einer Zeile implementiert werden:

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

Die Haversine-Formel besteht aus mehreren Zeilen:

  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))

Mathematisch gibt es identische, so dass der einzige Unterschied in der Praktikabilität besteht.

Tom W
quelle
Während das ursprüngliche Haversine die computer-bezogene atan2Formel nicht verwendet , gibt es nichts, das einen davon abhält, die 4 obigen Zeilen in eine einzige Formel umzuschreiben.
Arjan
@Arjan, stimmt, aber es wäre ineffizient , weil Sie berechnen müssen eine zweimal. Es ist wichtig, dass die Formel sowohl Sqrt (a) als auch Sqrt (1-a) umfasst, denn obwohl eine davon für sehr kleine oder sehr große Entfernungen numerisch instabil ist, funktioniert die andere nicht: Deshalb funktioniert dieser Ansatz.
whuber
Stimmt, @whuber, aber ich bezweifle immer noch, dass die Anzahl der Zeilen mich jemals dazu bringen würde, eine über die andere zu wählen. (Und wie Sie bereits in Ihrer Antwort erklärt haben, gibt es viel wichtigere Gründe, einen zu bevorzugen.)
Arjan
3
@Arjan Ich stimme zu. Die erste Priorität sollte die Angemessenheit des Codes für die Programmieraufgabe sein. Danach würde ich Klarheit schaffen: das heißt Lesbarkeit, Wartbarkeit und gute Dokumentation. Ohne einen solchen Kontext ist es bedeutungslos, die Anzahl der Codezeilen zu zählen.
Whuber
1
atan2(sqrt(a), sqrt(1-a))ist dasselbe wieasin(sqrt(a))
user102008