Lokalizacja projektu na ścieżce (wielkiego koła)

9

Przeszukuję tę stronę SE już od kilku godzin i wciąż mam trudności z znalezieniem rozwiązania mojego pytania. Moim celem jest to, że biorąc pod uwagę sposób w OSM i moją lokalizację (współrzędne lat / lon), chcę znaleźć najbliższą lokalizację (współrzędne lat / lon) na tej drodze. Punkt może znajdować się w dowolnym miejscu po drodze, nie ograniczając się do punktów użytych do zdefiniowania drogi.

Mam na myśli następujący algorytm:

  1. Rozdziel ścieżkę na osobne krawędzie, przy czym każda krawędź łączy tylko dwa punkty.
  2. Wybierz najbliższą krawędź.
  3. Wyświetl moją lokalizację na tej krawędzi.

Teraz jest wiele pytań dotyczących obliczania odległości między lokalizacją a ścieżką:

Również bardzo podobne pytanie, którego nie mogę poprawnie wyliczyć lub zweryfikować:

Jest też kilka informacji od dr Matha na ten temat. Jednak nie mogę znaleźć algorytmu do obliczenia lokalizacji w kroku 3. Ponieważ od dłuższego czasu nie dotknąłem algebry (wektorowej), nie do końca rozumiem logikę tych odpowiedzi.

Czy ktoś może pokazać algorytm, aby to zrobić? Rozwiązanie w dowolnym rozsądnym języku programowania jest dla mnie w porządku.

Bouke
źródło
1
Ponieważ wydaje się to mieć krytyczne znaczenie dla „odrzucenia” pozostałych pytań, prosimy o rozwinięcie „rzutowania mojej lokalizacji na tę krawędź”. Projekcja może nie znajdować się na krawędzi. Uważam, że problem ten został omówiony w innych pytaniach. (Dobra robota, do badań, BTW.)
Martin F
@MartinF to pytanie oblicza odległość od punktu do linii, ale nie najbliższy punkt na samej linii.
Bouke
Nie jest to rozwiązanie na gis.stackexchange.com/a/23500/3195 choć to może trudne do zrozumienia.
Martin F,
Ach tak, dziękuję, zaktualizowałem nr ref. 3. „Rozwiązanie” w tym konkretnym pytaniu prowadzi do ogólnego wyjaśnienia dziedziny problemu. Chociaż może to być wystarczające dla dobrze ugruntowanych matematyków, nie do końca rozumiem matematykę w tym artykule.
Bouke

Odpowiedzi:

7

Zastosowanie sferycznego modelu Ziemi może zapewnić odpowiednią dokładność i prowadzić do prostych szybkich obliczeń.

Konwertuj wszystkie współrzędne na współrzędne kartezjańskie ześrodkowane na ziemi (3D). Na przykład formuła

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

zrobi. (Wykorzystuje miarę odległości, w której promień ziemi wynosi jedną jednostkę, co jest wygodne.)

Zapis X0 = (x0, y0, z0) dla punktu początkowego i X1 = (x1, y1, z1) dla punktu docelowego, które definiują wielki okrąg (pod warunkiem, że X0 różni się od X1 i oba nie są diametralnie przeciwne), niech U będzie znormalizowanym iloczynem krzyżowym X0 i X1. Oblicza się to w dwóch krokach:

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

Długość V wynosi

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

Normalizacja rozciąga V na jednostkę długości:

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

Zorientowana odległość 3D między dowolnym punktem X = (x, y, z) a płaszczyzną tego wielkiego koła jest iloczynem iloczynu X z Z, podanym przez

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

Najbliższym punktem pod względem odległości na powierzchni ziemi jest ten, który jest najbliżej płaszczyzny: ma zatem najmniejszą wartość bezwzględną d .

Postać

Ta figura pokazuje wielki okrąg (w kolorze czarnym) wyznaczony przez dwa białe punkty i 2000 losowych punktów na kuli pokolorowanych i zacieniowanych zgodnie z ich absolutną odległością 3D od płaszczyzny tego wielkiego koła; to znaczy, | d |.

Po znalezieniu najbliższego punktu, rzutuj go na wielki okrąg, najpierw rzutując go na płaszczyznę wielkiego koła (w 3D), a następnie rozciągając go promieniowo na zewnątrz do powierzchni ziemi. Projekcja po prostu odejmuje d * U:

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

Rzut promieniowy po prostu renormalizuje X 'w ten sam sposób, w jaki V został renormalizowany na U:

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

(Będzie to problematyczne, jeśli | X '| = 0, co dzieje się, gdy najbliższy punkt jest jednym z biegunów wielkiego koła. Jeśli to możliwe, dołącz do kodu test tego warunku i załatw go osobno, używając znaku d, aby zidentyfikować, który biegun.)

W razie potrzeby przekonwertuj współrzędne X '' z powrotem na (lat, lon), używając zwykłych wzorów .

Whuber
źródło
Jedno pytanie. Rozważ niezbyt niezwykły przypadek, w którym możemy wybrać dowolny X1 i X0 (na wielkim kole), z punktu widzenia dokładności, czy lepiej jest wybrać X1 i X0 blisko lub daleko od siebie (ponownie pod warunkiem, że X0 różni się od X1 i te dwa nie są diametralnie przeciwne)?
user189035
1
@ user189035 Wybierz je w odległości 90 stopni. Gdy są bardzo blisko siebie, ich iloczyn krzyżowy jest niepewny numerycznie: odejmuje się wiele anulowań, co prowadzi do utraty znaczących liczb.
whuber