Projektstandort auf einem (Großkreis-) Pfad

9

Ich habe diese SE-Site jetzt seit einigen Stunden durchsucht und habe immer noch Probleme, eine Lösung für meine Frage zu finden. Mein Ziel ist es, dass ich anhand eines Weges in OSM und meines Standorts (Lat / Lon-Koordinaten) den nächstgelegenen Standort (Lat / Lon-Koordinaten) auf diesem Weg finden möchte. Der Punkt kann sich überall auf dem Weg befinden, nicht nur auf die Punkte, die zum Definieren des Weges verwendet werden.

Ich denke also an folgenden Algorithmus:

  1. Separater Pfad in separate Kanten, wobei jede Kante nur zwei Punkte verbindet.
  2. Wählen Sie die nächste Kante.
  3. Projizieren Sie meinen Standort auf diesen Rand.

Nun gibt es viele Fragen zur Berechnung der Entfernung zwischen einem Ort und einem Pfad:

Auch eine sehr ähnliche Frage, bei der ich die Berechnungen nicht richtig oder verifiziert machen kann:

Es gibt auch einige Informationen von Dr. Math zu diesem Thema. Ich kann jedoch anscheinend keinen Algorithmus finden, um den Ort in Schritt 3 zu berechnen. Da ich die (Vektor-) Algebra seit einiger Zeit nicht mehr berührt habe, verstehe ich die Logik in diesen Antworten nicht ganz.

Kann jemand einen Algorithmus zeigen, um dies zu tun? Eine Lösung in einer vernünftigen Programmiersprache ist für mich in Ordnung.

Bouke
quelle
1
Da es für Ihre "Ablehnung" der anderen Fragen von entscheidender Bedeutung zu sein scheint, erläutern Sie bitte "Projizieren Sie meinen Standort auf diesen Rand". Die Projektion befindet sich möglicherweise nicht am Rand. Ich glaube , dass Problem wird in den anderen Fragen gerichtet. (Gut gemacht, für die Forschung, übrigens.)
Martin F
@MartinF diese Frage berechnet die Entfernung von einem Punkt zu einer Linie, aber nicht den nächsten Punkt auf der Linie selbst.
Bouke
Unter gis.stackexchange.com/a/23500/3195 gibt es eine Lösung , die jedoch möglicherweise schwer zu verstehen ist.
Martin F
Ah ja danke, ich habe ref nein aktualisiert. 3. Die "Lösung" in dieser speziellen Frage verweist auf eine allgemeine Erklärung des Problemfeldes. Während dies für fundierte Mathematiker ausreichend sein mag, verstehe ich die Mathematik in diesem Artikel nicht ganz.
Bouke

Antworten:

7

Die Verwendung eines sphärischen Erdmodells kann eine ausreichende Genauigkeit ergeben und zu einfachen, schnellen Berechnungen führen.

Konvertieren Sie alle Koordinaten in erdzentrierte (3D) kartesische Koordinaten. Zum Beispiel die Formel

(cos(lon)*cos(lat), sin(lon)*cos(lat), sin(lat))

Wird besorgt. (Es wird ein Abstandsmaß verwendet, bei dem der Erdradius eine Einheit beträgt, was praktisch ist.)

Schreiben von X0 = (x0, y0, z0) für den Startpunkt und X1 = (x1, y1, z1) für den Zielpunkt, die den Großkreis definieren (vorausgesetzt, X0 unterscheidet sich von X1 und die beiden sind nicht diametral entgegengesetzt). sei U das normalisierte Kreuzprodukt von X0 und X1. Dies wird in zwei Schritten berechnet:

V = (xv, yv, zv) = (y0*z1 - z0*y1, z0*x1 - x0*z1, x0*y1 - y0*x1)

Die Länge von V ist

|V| = sqrt(xv^2 + yv^2 + zv^2)

Die Normalisierung erstreckt sich von V auf die Längeneinheit:

U = (xu, yu, zu) = V / |V| = (xv/|V|, yv/|V|, zv/|V|).

Der orientierte 3D-Abstand zwischen einem beliebigen Punkt X = (x, y, z) und der Ebene dieses Großkreises ist nur das Punktprodukt von X mit Z, gegeben durch

d = X * U = x*xu + y*yu + z*zu

Der nächstgelegene Punkt in Bezug auf die Entfernung auf der Erdoberfläche ist derjenige, der der Ebene am nächsten liegt: Er hat also den kleinsten absoluten Wert von d .

Zahl

Diese Abbildung zeigt einen Großkreis (in Schwarz), der durch die beiden weißen Punkte und 2000 zufälligen Punkte auf der Kugel bestimmt wird, die entsprechend ihrem absoluten 3D-Abstand zur Ebene dieses Großkreises gefärbt und schattiert sind. das heißt, | d |.

Nachdem Sie einen nächstgelegenen Punkt gefunden haben, projizieren Sie ihn auf den Großkreis, indem Sie ihn zuerst auf die Ebene des Großkreises (in 3D) projizieren und diesen dann radial nach außen zur Erdoberfläche ausdehnen. Die Projektion subtrahiert lediglich d * U:

X' = (x', y', z') = X - d*U = (x - d*xu, y - d*yu, z - d*zu).

Die radiale Projektion normalisiert X 'einfach auf die gleiche Weise, wie V zu U renormiert wurde:

X'' = X' / |X'|.

(Dies ist problematisch, wenn | X '| = 0 ist, was passiert, wenn der nächste Punkt einer der Pole des Großkreises ist. Fügen Sie einen Test für diese Bedingung in den Code ein, falls dies passieren könnte, und behandeln Sie ihn separat. Verwenden Sie das Vorzeichen von d , um den Pol zu identifizieren.)

Falls gewünscht, konvertieren Sie die Koordinaten von X '' mit den üblichen Formeln zurück in (lat, lon) .

whuber
quelle
Eine Frage. Betrachten Sie den nicht allzu ungewöhnlichen Fall, in dem wir X1 und X0 (auf dem Großkreis) unter dem Gesichtspunkt der Genauigkeit auswählen können. Es ist besser, X1 und X0 nahe oder weit voneinander entfernt auszuwählen (vorausgesetzt, X0 unterscheidet sich von X1 und die beiden sind nicht diametral entgegengesetzt)?
user189035
1
@ user189035 Wähle sie in einem Abstand von 90 Grad. Wenn sie sehr nahe beieinander liegen, ist ihr Kreuzprodukt numerisch ungewiss: Die Subtraktionen werden häufig aufgehoben, was zum Verlust signifikanter Zahlen führt.
whuber