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

8

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.

Abhi Beckert
quelle
Ich schlage vor, diese Frage auf der OSM- Entwickler -Mailingliste ( lists.openstreetmap.org/listinfo/dev ) zu stellen. Sie ist etwas zu spezifisch für ein allgemeines GIS-Forum.
Igor Brejc
1
Sicherlich ist die Mathematik zum Finden eines Punktes auf halbem Weg zwischen zwei anderen Punkten nicht sehr spezifisch?
Abhi Beckert
Es ist nicht so, aber vielleicht gibt es andere Möglichkeiten, mit diesem Problem umzugehen, das formatspezifisch ist.
Igor Brejc
Es gibt keine alternativen Methoden, um damit umzugehen. Eine 16-Bit-Ganzzahl ist das einzige Format, das in gewisser Weise für Punkte zulässig ist, und (mit einer Genauigkeit von 6 Dezimalstellen) eine 16-Bit-Ganzzahl kann nur eine Differenz von etwa 3,5 km zwischen zwei Punkten darstellen. Die einzige Alternative besteht darin, dieses Format nicht zu verwenden (was meine Zwischenlösung ist). Aber ich möchte wenn möglich etwas Standardisches verwenden.
Abhi Beckert
1
Ich denke, Sie könnten um eine Größenordnung abweichen: Die längsten Entfernungen, die Sie auf der Erde finden können, betragen ungefähr 20.000 km. Mit 16 Bit entspricht dies einer Genauigkeit von 300 m.
whuber

Antworten:

13

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:

Relative Fehler

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.

Relative Fehler 2

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.

Relative Fehler 3

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.

whuber
quelle
1
Wow, danke! Das sind einige wirklich gute Informationen. Ich brauche keine perfekte Präzision, es ist nur eine iPhone-App für den persönlichen GPS-Gebrauch, die sich hauptsächlich auf Straßen konzentriert. Da eine Autobahn über Hunderte von Kilometern nicht perfekt gerade ist, ist auch die lineare Präzision "gut genug". Aber die politischen Grenzen sind oft gerade und lang (die rechte Seite von Westaustralien ist 1.800 km lang). Die Kugelformel sollte dafür perfekt sein. Ich wünschte, ich könnte dir ein Kopfgeld für deine Antwort geben, du hast es verdient.
Abhi Beckert
8

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

Geben Sie hier die Bildbeschreibung ein

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.

Igor Brejc
quelle
Vielen Dank! Genau das suche ich. Mike Gavaghans Code lässt sich leicht auf C portieren (ich verwende übrigens tatsächlich Objective-C). Ich war mir ziemlich sicher, dass meine lineare Mathematik ein Ausweg sein würde, aber ich musste etwas haben.
Abhi Beckert
-1

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

Beispiel einer langen geraden Linie zwischen Punkten

Abhi Beckert
quelle