Wie finde ich einen Punkt auf halbem Weg zwischen zwei anderen Punkten?

Ich arbeite an der Implementierung des OSM Mobile Binary-Formats für Kartendaten. Da für jeden Punkt auf einem Weg ein 16-Bit-Delta verwendet wird, kann es keinen Weg darstellen, wenn zwischen zwei Punkten ein großer Abstand besteht.

Die dokumentierte Lösung besteht darin, neue Punkte in den Weg einzufügen, um die Lücke kleiner zu halten.

Hier ist der relevante Abschnitt meines Codes:

// calculate the distance between this point and the previous point,
// multiplied by 1,000,000 so it can be represented as an integer.
int32_t realNodeLatDelta = ((point.latitude - lastPoint.latitude) * 1000000);
int32_t realNodeLonDelta = ((point.longitude - lastPoint.longitude) * 1000000);

// cast as a 16 bit int (reduces filesize by about half)
int16_t nodeLatDelta = realNodeLatDiff;
int16_t nodeLonDelta = realNodeLonDiff;

// check if the cast caused corruption
if (realNodeLatDelta != nodeLatDelta || realNodeLatDelta != nodeLatDelta) {
  // if this point is reached, we need to add new points in the way,
  // which can be represented in a 16 bit delta
}

Ich bin mir nicht sicher, wie ich die Position neuer Punkte auf dem Weg berechnen soll. Ich nehme an, es muss ein großer Kreis sein?

Punkte, die weit genug voneinander entfernt sind, um dieses Problem zu verursachen, sind selten, aber wenn sie auftreten, handelt es sich normalerweise um eine politische Grenze oder ähnliches, die in der Regel recht lang ist und genau dargestellt werden muss.

Die beste Genauigkeit wird mit Ellipsoidmodellen erzielt. Der Einfachheit halber möchten Sie diese vermeiden, wenn Sie Entfernungen selbst codieren müssen. Wir zahlen einen Preis: Da die Abflachung der Erde etwa 1/300 beträgt, kann die Verwendung eines rein sphärischen Modells bei sehr langen Strecken möglicherweise einen relativen Abstandsfehler von bis zu 1/300 verursachen: etwa 3000 ppm. Dies ist eine Erkundung wert.

Zuerst die Kugelformel : Konvertieren Sie einfach (lat, lon) in kartesische Koordinaten, mitteln Sie die beiden kartesischen Punkte und konvertieren Sie dann den Durchschnitt zurück in sphärische Koordinaten. Hier ist Pseudocode:

function cartesian(f,l) { // f = latitude, l = longitude
    return (cos(f)*cos(l), cos(f)*sin(l), sin(f))
}
function spherical(x,y,z) {
    r = sqrt(x^2 + y^2)
    if (r == 0) {
        if (z > 0) return (90, 0) 
        elseif (z < 0) return (-90, 0)
        else return Undefined // (x,y,z) == (0,0,0)
    } else {
        return (atan2(r, z), atan2(x, y)) // atan2 must return *degrees*
    }
}
function midpoint(f0,l0, f1,l1) { 
    return spherical((cartesian(f0,l0) + cartesian(f1,l1))/2)
}

(Die Arithmetik für midpointbeinhaltet eine Vektorsumme und eine skalare Division dieser Summe, sodass wirklich drei Summen und drei Divisionen verborgen sind.)

Das ist der Mittelpunkt der sphärischen Geometrie. Die Berechnung erfordert zwei Cosinus, zwei Sinus, eine Quadratwurzel, zwei Arkustangens und eine gewisse Multiplikation und Addition: relativ schnell und einfach. In der Nähe der Pole oder beim Überqueren des + -180-Meridians treten keine Probleme auf. Das Ergebnis ist undefiniert, wenn die beiden Punkte diametral gegenüberliegen.

Eine Möglichkeit, den Fehler zu messen, besteht darin, die über den Mittelpunkt zurückgelegte größere Entfernung im Vergleich zur Entfernung zwischen den ursprünglichen Punkten zu berechnen. Wenn der Anstieg im Vergleich zur ursprünglichen Entfernung winzig ist, haben wir wenig zu beanstanden. Ich habe diese Fehler unter Verwendung des genauen Ellipsoidabstands für das WGS84-Ellipsoid berechnet. Als typisches Beispiel für die Ergebnisse ist hier eine grafische Darstellung der relativen Fehler, wenn einer der Endpunkte auf (lat, lon) = (45, 0) festgelegt ist:

Die Konturen liegen auf einer logarithmischen Skala (Basis 10): Die -6-Konturen zeigen Punkte, an denen der relative Fehler 10 ^ (- 6) beträgt; das heißt, ein Teil pro Million (ppm). Die -5 Konturen (kaum sichtbar in der Nähe von (-45, 180), dem diametral entgegengesetzten Punkt) betragen 10 ppm. Die -7, -8 usw. sind Bruchteile von ppm: hochgenau.

Offensichtlich werden wir es gut machen, solange wir nicht versuchen, Mittelpunkte von zwei Punkten zu berechnen, die sich fast diametral gegenüberliegen. (Denken Sie daran, dass die Berechnung für die Kugel vollkommen korrekt ist. Diese Fehler sind auf die Abflachung der Kugel zurückzuführen.)

Angesichts einer 16-Bit-Genauigkeit von etwa 16 ppm (ein Basis-10-Log-Wert von -4,8) ist es in Ordnung, die Kugelformel für die Mittelpunktsuche zu verwenden, vorausgesetzt, die beiden Punkte sind mehr als einen Grad vom diametralen Gegenteil entfernt.

Was ist mit der einfacheren linearen Formel? Um dies zu untersuchen, vergleichen wir den Abstand zwischen dem linearen Mittelpunkt (erhalten durch Mitteln der beiden Breiten- und zwei Längengrade) und dem sphärischen Mittelpunkt relativ zum Abstand zwischen den beiden Endpunkten. Die nächste Abbildung legt einen Endpunkt bei (45, 180) fest und untersucht einen relativ kleinen Bereich um ihn herum.

Die meisten dieser Konturen (wieder Basis-10-Logarithmen) liegen nahe -2: Das ist ein Teil pro hundert (1%) Fehler. Für Nord-Süd-Richtungen gibt es keinen Fehler, aber für alle anderen Richtungen ist der Fehler für viele Anwendungen nicht akzeptabel .

Um zu sehen, ob die lineare Approximation jemals in Ordnung wird, vergrößern wir die vorherige Karte um den Faktor 10. Jetzt ist sie einen Grad breit (50 Meilen bei diesem Breitengrad) und einen halben Grad breit (35 Meilen): Wir suchen im Maßstab einer Großstadt oder einer Kleinstadt und ihrer Vororte.

Jetzt liegen die Konturen bei -3 bis -4: das sind 100 bis 1000 Teile pro Million (0,01% bis 0,1%). Ziemlich grob und auf einem hochauflösenden Computerbildschirm kaum wahrnehmbar, wenn man genau hinschaut.

Rückblickend ist ersichtlich, dass die etwas kompliziertere - aber dennoch leicht umsetzbare - Kugelformel weltweit eine größere Genauigkeit erzielt als die einfache lineare Formel selbst an nahe gelegenen Orten. (Ich fummle ein wenig herum, weil ich zwei verschiedene Methoden zum Messen von Fehlern verwendet habe, sodass sie nicht direkt vergleichbar sind.)

Das Fazit:

- Die lineare Formel positioniert den Mittelpunkt um einen relativen Fehler von 0,01% bis 0,1% auf einer Stadtskala falsch. In größeren Gebieten kann die Fehlpositionierung grob falsch sein (1% bei bis zu Hunderten von%).

- Die Kugelformel ist für ein Kugelerdmodell absolut korrekt. Im Vergleich zur genaueren Ellipsoidformel sollte es bis auf Punkte, die fast diametral entgegengesetzt sind, immer noch gut funktionieren.

Ihre Lösung funktioniert für kleine Entfernungen, für größere jedoch nicht. Der einfachste Weg, um zu sehen, warum, ist die folgende Karte (von hier aus gesehen ):

Es ist eine Weltkarte in gleichwinkliger Projektion - Längen- und Breitengrade werden einfach linear in X- und Y-Achsen projiziert. Ihre Mathematik kann durch das blaue Rechteck dargestellt werden . Die blaue Diagonale repräsentiert jedoch nicht die kürzeste "Linie" zwischen zwei Punkten auf der Erdoberfläche. Was Sie brauchen, ist ein großer Kreis (dargestellt durch eine schwarze Kurve).

Obwohl Sie C ++ verwenden, empfehle ich einen Blick auf die C # Geodesy Library von Mike Gavaghan , die Open Source ist und von hoher Qualität ist. Sie sollten in der Lage sein, herauszufinden, wie die Berechnung entlang des großen Kreises durchgeführt wird. Sie können sich auch Vincentys Formeln ansehen , wenn Sie sich für Mathematik hinter der Berechnung interessieren.

Einfache lineare Mathematik scheint gut zu funktionieren:

double newLat = lastCoord.latitude + ((coord.latitude - lastCoord.latitude) / 2);
double newLon = lastCoord.longitude + ((coord.longitude - lastCoord.longitude) / 2);

Ich füge rekursiv halb neue Punkte in jeden Abschnitt des Weges ein, der zu groß ist, bis sie alle klein genug sind.

Ich bin mir nicht sicher, ob für größere Entfernungen komplexere Berechnungen erforderlich sind (kann dies jemand für mich bestätigen?), Aber es funktioniert gut über diese (ca. 5 km):