Berechnung der Entfernung zwischen einem Punkt und einer virtuellen Linie aus zwei Längen

14

Bitte beachten Sie das Beispiel und das entsprechende Bild.

Ich möchte Folgendes erreichen: Geben Sie zwei Standorte (lat / lng) an, die im Folgenden als A und B dargestellt sind . Daraus würde eine virtuelle Linie gezogen und dann der Abstand zwischen dieser Linie und C berechnet (bei jeder Messung).

Zeichnung

Ich habe dies derzeit in Google Maps API v3 erreicht, möchte dies aber auch hinter den Kulissen in der Sprache meiner Wahl durchführen können. Alle Tipps / Ideen wäre sehr dankbar!

Häftling
quelle
Ist AB eine Great Circle Linie?
Kirk Kuykendall
@ Kirk, Nein, AB ist nur eine gerade Linie
Prisoner
@ Michael, das ist ein interessanter Punkt. Ich muss mal reinschauen!
Gefangener
@Prisoner @Kirk Buchstäblich wird eine "gerade Linie" unter der Erdoberfläche verlaufen. Im Allgemeinen ist seine radiale Projektion zurück auf die Oberfläche tatsächlich ein Segment eines Großkreises (unter Verwendung eines sphärischen Erdmodells).
Whuber
1
@Prisoner Das ist eine äußerst nützliche Zusatzinformation! Ja du hast Recht. Sie müssen noch die Tatsache kompensieren, dass die Verwendung von (lat, lon) die Ost-West-Entfernungen im Vergleich zu Nord-Süd unterschiedlich verzerrt. Projizieren Sie die Koordinaten, wie von @Jose empfohlen. Dies kann so einfach sein, als ob Sie die Längengrade mit dem Kosinus des durchschnittlichen Breitengrades vormultiplizieren und dann so tun, als wären Sie auf einer euklidischen Ebene.
Whuber

Antworten:

6
def get_perp( X1, Y1, X2, Y2, X3, Y3):
    """************************************************************************************************ 
    Purpose - X1,Y1,X2,Y2 = Two points representing the ends of the line segment
              X3,Y3 = The offset point 
    'Returns - X4,Y4 = Returns the Point on the line perpendicular to the offset or None if no such
                        point exists
    '************************************************************************************************ """
    XX = X2 - X1 
    YY = Y2 - Y1 
    ShortestLength = ((XX * (X3 - X1)) + (YY * (Y3 - Y1))) / ((XX * XX) + (YY * YY)) 
    X4 = X1 + XX * ShortestLength 
    Y4 = Y1 + YY * ShortestLength
    if X4 < X2 and X4 > X1 and Y4 < Y2 and Y4 > Y1:
        return X4,Y4
    return None

Die kürzeste Länge ist die Entfernung, die Sie benötigen, es sei denn, ich irre mich?

Behaart
quelle
Ja, ich suche den kürzesten Abstand von C zum Streckenabschnitt. Berechnet diese Mathematik das?
Gefangener
1
Es hat in der Tat gut funktionieren, habe ich die drei Punkte (A, B, C) in dem folgenden: i.imgur.com/bK9oB.jpg und es kam mit dem lat / lng von X. Great work!
Gefangener
1
@Hairy, eine letzte Sache, wie würde ich vorgehen, um dies zu ändern, um zum nächsten Punkt (nicht nur zur Linie) zu gelangen? Wenn ich es also hinter den Punkt gesetzt hätte, an dem ich eine Linie füge, wie könnte ich es dazu bringen, die Entfernung zum zu überprüfen? Punkt?
Gefangener
1
@Hairy Guter Anfang, aber es scheint, dass dieser Code zu oft zurückgegeben wird, Nonewenn eine legitime Lösung vorhanden ist. Das Problem ist, dass die letzte Bedingung X1 <X2 und Y1 <Y2 annimmt, was nicht immer sichergestellt werden kann. Ein besserer Test der Übereinstimmung ist erforderlich.
whuber
1
@Hairy Es hört sich so an, als ob dieser Austausch zwischen Ihnen und @prisoner produktiv war. Ich möchte betonen, dass ich nichts damit zu tun hatte (oder auch keine Kontrolle darüber hatte), ob Abstimmungen oder Punkte geändert wurden, und dass mein Kommentar nur dazu gedacht war, Ihnen dabei zu helfen, Ihre Antwort zu verbessern.
Whuber
11

Vielleicht mache ich es zu kompliziert, aber was Sie wollen, ist die Entfernung von einem Punkt zu einer Linie. Dies ist der Abstand von einem Punkt entlang AB, der AB mit C mit einer zu AB orthogonalen Linie verbindet. Dieser Vektor senkrecht zu AB ist gegeben durch

v=[x2-x1, -(y2-y1)] # Point A is [x1,y1] Point B is [x2,y2]

(Ich habe die eckigen Klammern verwendet, um einen Vektor oder ein Array mit zwei Elementen zu definieren.) Der Abstand zwischen C [xp, yp] und Punkt A beträgt

u=[x1-xp, y1-xp]

Der Abstand zwischen der Linie und C ist nur die Projektion von u auf v. Wenn wir mod (v) = 1 annehmen (nur normalisieren), dann

distance = u*v = abs( (x2-x1)*(y1-yp) - (x1-xp)*(y2-y1) )

Die einzige Schwierigkeit besteht darin, dass Sie wahrscheinlich sicherstellen möchten, dass Ihre Koordinaten keine WGS84-Lat / Log-Paare sind, sondern projiziert (oder geodätische Koordinaten verwenden). Sie können hierfür OGR oder Proj4 verwenden .

Jose
quelle
3
+ Übrigens mehrere Millionen Pseudopunkte, weil sie keine trigonometrischen Funktionen verwenden. Allzu viele Leute ziehen ArcTan heraus, wenn sie sich das ansehen sollten: en.wikipedia.org/wiki/Dot_product
Herb
@Jose, danke für die Antwort! Ich verwende die Lat / Long-API von Google Maps. Der Mathe-Teil ist für mich ziemlich neu, also werde ich es versuchen und sehen, was ich mir einfallen lassen kann. Irgendwelche Tipps mit der Mathematik? ZB [x2-x1, - (y2-y1)], was bedeutet das?
Gefangener
Ich habe dafür eine kurze Bearbeitung hinzugefügt. Grundsätzlich ist es eine Array-Notation, aber wenn Sie Ihre Koordinaten in den Variablen x1, x2, y1, y2 und xp, yp speichern, müssen Sie nur die rechte Seite der letzten von mir bereitgestellten Gleichung schreiben. Dies ist so ziemlich der gültige Code für C, Java, JS, Python usw. :)
Jose
1
@Jose Sie berechnen die Entfernung von C zur Linie AB. Ausgehend von der Abbildung glaube ich, dass das OP den Abstand von C zum Liniensegment AB haben möchte . Dies erfordert zusätzliche Arbeit, um zu prüfen, ob die Projektion von C auf die Linie AB zwischen A und B liegt oder nicht. Verwenden Sie im letzteren Fall die kürzere der beiden Längen CA und CB.
Whuber
1
@Prisoner Der Hauptunterschied besteht darin, dass sich eine Linie für immer erstreckt (sie wird nur durch einen Richtungsvektor und einen Punkt oder durch zwei Punkte definiert), während ein Segment zwischen A und B das Bit der unendlichen Linie ist, die zwischen A und verläuft B (es hat eine endliche Länge)
Jose
4

Da ich all dieser Mathematik auch ein bisschen abgeneigt bin, würde ich es aus einem anderen Blickwinkel betrachten. Ich würde es zu einer "tatsächlichen" Linie und nicht zu einer virtuellen Linie machen und dann vorhandene Tools verwenden.

Wenn A und B ein Attribut gemeinsam haben, können Sie sie verbinden, indem Sie eine Linie zeichnen. Sobald Sie die Linien haben, gibt Ihnen eine Nahfunktion auf der C-Punkt-Ebene die Entfernung zur Linie an. Lassen Sie die Software die Mathematik für Sie erledigen!

Darren Cope
quelle
Vielen Dank für den Kommentar, aber Hairy hat in diesem Fall Trumpf gemacht!
Gefangener
1
(+1) Sie machen einen ausgezeichneten Punkt. Algorithmen für die rechnergestützte Geometrie sind in der Praxis notorisch schwierig umzusetzen (wie wir aus dem gesamten Code sehen können, der bisher angeboten wurde, der hilfreich und illustrativ ist, aber noch nicht vollständig funktioniert). Die Verwendung eines GIS-Verfahrens auf hoher Ebene ist oft eine gute Methode, um sicherzustellen, dass Sie die erwartete Antwort erhalten und dass sie richtig ist (vorausgesetzt, Sie vertrauen Ihrem GIS ;-).
whuber
1

Wenn Sie Java auf Android verwenden, ist es nur eine Zeile mit der Bibliotheksfunktion

import static com.google.maps.android.PolyUtil.distanceToLine;

distanceToLine:

public static double distanceToLine(LatLng p, LatLng start,LatLng end)

Berechnet den Abstand auf der Kugel zwischen dem Punkt p und dem Ende des Liniensegments.

Parameter: p - der zu messende Punkt

start - der Anfang des Liniensegments

Ende - das Ende des Liniensegments

Rückgabe: die Entfernung in Metern (unter der Annahme einer sphärischen Erde)

Fügen Sie einfach eine Bibliothek zu Ihrer hinzu

dependencies {
    compile 'com.google.maps.android:android-maps-utils:0.5+'
}
Indy
quelle