Wzory na wyliczanie tras GPS między miejscowościami z punktami pośrednimi

Mam pytanie, czy ktoś orientuje się, gdzie można szukać wzorów na wyliczanie dróg pomiędzy dwoma miejscowościami, podając jako parametry
długość i szerokość geograficzną, najlepiej jeszcze z wyznaczaniem pośrednich punktów.(dane na poziome GPS)
Za wszelkie informacje, oraz podana literaturę serdecznie dziekuję.

kaja1 napisał:

Mam pytanie, czy ktoś orientuje się, gdzie można szukać wzorów na wyliczanie dróg pomiędzy dwoma miejscowościami, podając jako parametry
długość i szerokość geograficzną, najlepiej jeszcze z wyznaczaniem pośrednich punktów.(dane na poziome GPS)
Za wszelkie informacje, oraz podana literaturę serdecznie dziekuję.

Ja bym to zrobil tak:

- Cala mape przedstawil bym za pomoca grafu
- Kazdy punkt w grafie mial by swoje wspolrzedne geograficzne
- Najkrotsza droge miedzy punkami w grafie wyznaczyl bym algorytmem Dijkstry o zloznosci obliczeniowej O(V log V + E); przy zalozeniu ze graf nie ma wag ujemnych co nie wystapi w mapie GPS;
(Ten wlasnie algorytm jest wykorzystywany w GPS i nawet w znajdowaniu najktotszej drogi miedzy routerami, przy polaczeniu internetowym, polecam Ci go)

Wiecej informacji na temat algorytmu Dijkstry:
http://pl.wikipedia.org/wiki/Algorytm_Dijkstry

Wiecej na temat Problemu najkrotszej sciezki w grafie:
http://pl.wikipedia.org/wiki/Problem_najkr%C3%B3tszej_%C5%9Bcie%C5%BCki

Dzięki za odpowiedz, wykorzystaliśmy ten własnie algorytm Dijk. , którego pełno implementacji w internecie oraz wzór na obliczanie odległości z danych GPS:D