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

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

• Punkt WGS wskazuje odległość odcinka linii WGS (wielkie koło)
• Obliczanie odległości między punktem a wirtualną linią dwóch lat / lngs
• Jak przybliżać odległość między punktami na kuli?

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

• Znajdź najbliższy punkt na linii

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.

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 .

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 .