Obliczanie odległości między punktem a wirtualną linią dwóch lat / lngs

14

Proszę odnieść się do przykładu i odpowiedniego obrazu.

Ja zamierzamy uzyskać następujące: dostarczenie dwóch miejscach (łac / ng), które są pokazane poniżej jako A i B . Na tej podstawie zostanie narysowana linia wirtualna, a następnie obliczona zostanie odległość między tą linią a C (w dowolnym pomiarze).

rysunek

Osiągnąłem to obecnie w Google Maps API v3, ale chciałbym również móc to zrobić za kulisami w moim wybranym języku. Wszelkie wskazówki / pomysły będą mile widziane!

Więzień
źródło
Czy AB to linia Great Circle ?
Kirk Kuykendall
@Kirk, Nie, AB jest po prostu linią prostą
więzień
@Michael, to interesujący punkt. Będę musiał to zobaczyć!
Więzień
@ Więzień @Kirk Dosłownie „linia prosta” przejdzie pod powierzchnią ziemi. Zasadniczo jego rzut promieniowy z powrotem na powierzchnię będzie rzeczywiście fragmentem wielkiego koła (przy użyciu kulistego modelu ziemi).
whuber
1
@ Więzień To bardzo przydatna dodatkowa informacja! Tak, masz rację. Nadal musisz zrekompensować fakt, że użycie (lat, lon) różnicowo zniekształca odległości wschód-zachód w porównaniu do północ-południe. Zgodnie z zaleceniem @Jose, wyświetl współrzędne. Może to być tak proste, jak wstępne pomnożenie długości przez cosinus średniej szerokości geograficznej, a następnie udawanie, że jesteś na płaszczyźnie euklidesowej.
whuber

Odpowiedzi:

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

Najkrótsza długość to wymagany dystans, chyba że się mylę?

Włochaty
źródło
Tak, szukam najkrótszej odległości od C do odcinka linii. Czy to właśnie oblicza matematyka?
Więzień
1
Rzeczywiście działało dobrze, przeszedłem trzy punkty (A, B, C) w następujący sposób: i.imgur.com/bK9oB.jpg i wróciłem z lat / lng X. Świetna robota!
Więzień
1
@ Mleczarstwo, ostatnia rzecz, jak bym to zmienił, aby przejść do najbliższego punktu (nie tylko linii), więc jeśli przełożyłem go poza punkt dołączenia do linii, jak mogę sprawić, by sprawdził odległość do punkt?
Więzień
1
@Hairy Dobry początek, ale wydaje się, że zbyt często ten kod powraca, Nonegdy istnieje uzasadnione rozwiązanie. Problem polega na tym, że ostatni warunek zakłada X1 <X2 i Y1 <Y2, czego nie zawsze można zapewnić. Potrzebny jest lepszy test wzajemności.
whuber
1
@Hairy Wygląda na to, że ta wymiana między tobą a @prisoner była owocna. Chciałbym podkreślić, że nie miałem nic wspólnego (ani nawet kontroli) nad wszelkimi zmianami w głosowaniu lub punktami, które mogły wystąpić, i że mój komentarz miał na celu jedynie pomóc w poprawieniu odpowiedzi.
whuber
11

Może robię to zbyt skomplikowane, ale to, czego chcesz, to odległość od punktu do linii. Jest to odległość od punktu wzdłuż AB, który łączy AB z C linią prostopadłą do AB. Ten wektor prostopadły do ​​AB podano przez

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

(Użyłem nawiasów kwadratowych do zdefiniowania wektora lub tablicy dwuelementowej). Odległość między C [xp, yp] a punktem A wynosi

u=[x1-xp, y1-xp]

Odległość między linią a C jest tylko rzutem u na v. Jeśli założymy mod (v) = 1 (po prostu normalizujemy), to

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

Jedyną komplikacją jest to, że prawdopodobnie chcesz się upewnić, że twoje współrzędne nie są parami lat / log WGS84, ale są rzutowane (lub używasz współrzędnych geodezyjnych). Możesz do tego użyć OGR lub Proj4 .

Jose
źródło
3
+ nawiasem mówiąc, kilka milionów pseudo-punktów za nieużywanie funkcji trygonometrycznych. Zbyt wielu ludzi wyciąga ArcTan, kiedy powinni na to patrzeć: en.wikipedia.org/wiki/Dot_product
Herb
@Jose, dzięki za odpowiedź! Używam lat / long z interfejsu API Google Maps. Część matematyczna jest dla mnie całkiem nowa, więc spróbuję i zobaczę, co mogę wymyślić. Jakieś wskazówki dotyczące matematyki? Np. [X2-x1, - (y2-y1)], co to oznacza?
Więzień
Dodałem do tego krótką edycję. Zasadniczo jest to notacja tablicowa, ale jeśli przechowujesz swoje współrzędne w zmiennych x1, x2, y1, y2 i xp, yp, musisz tylko napisać prawą stronę ostatniego równania, które podałem. To jest właściwie poprawny kod C, Java, JS, Python itp. :)
Jose
1
@Jose Obliczasz odległość od C do linii AB. Na podstawie tej liczby uważam, że OP chce odległości od C do odcinka linii AB. Wymaga to dodatkowej pracy, aby sprawdzić, czy rzut C na linię AB leży między A i B, czy nie. W tym drugim przypadku użyj krótszej z dwóch długości CA i CB.
whuber
1
@ Więzień Główna różnica polega na tym, że linia rozciąga się na zawsze (jest definiowana tylko przez wektor kierunku i punkt lub dwa punkty), podczas gdy odcinek między A i B jest bitem nieskończonej linii, która biegnie między A i B (ma skończoną długość)
Jose
4

Będąc trochę niechętnym całej tej matematyce, podchodziłbym do tego z innej perspektywy. Uczyniłbym to „rzeczywistą” linią, a nie linią wirtualną, a następnie używałbym istniejących narzędzi.

Jeśli A i B mają wspólny atrybut, możesz połączyć je poprzez narysowanie linii (Kosmo GIS ma narzędzie, które utworzy linie z punktów, i sądzę, że jest do tego również wtyczka QGIS). Po uzyskaniu linii funkcja „near” na warstwie punktowej „C” da ci odległość do linii. Niech oprogramowanie zajmie się matematyką!

Darren Cope
źródło
Dzięki za komentarz, ale Hairy wpadł na atuty tego!
Więzień
1
(+1) Robisz doskonały punkt. Algorytmy obliczeniowej geometrii są bardzo trudne do osiągnięcia w praktyce (jak widać z całego dotychczas oferowanego kodu, który jest pomocny i ilustracyjny, ale jeszcze nie w pełni działa). Korzystanie z procedury GIS na wysokim poziomie często jest dobrym sposobem na upewnienie się, że otrzymujesz oczekiwaną odpowiedź i że jest poprawna (pod warunkiem, że ufasz swojemu GIS ;-).
whuber
1

Jeśli korzystasz z java na Androidzie, jest to tylko jedna linia z funkcją biblioteki

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

distanceToLine:

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

Oblicza odległość na kuli między punktem p a segmentem linii zaczynającym się kończyć.

Parametry: p - punkt, który należy zmierzyć

start - początek odcinka linii

end - koniec segmentu linii

Zwraca: odległość w metrach (przy założeniu kulistej ziemi)

Po prostu dodaj bibliotekę do swojego

dependencies {
    compile 'com.google.maps.android:android-maps-utils:0.5+'
}
indy
źródło