Odległości miejscowości Opcje

[TomASS]

Wtiam serdecznie

Szukam rozwiązania, algorytmu, propozycji wykonania w php + MySQL skrytpu do obliczania odległości (w linii prostej, bądź "drogowej") pomiędzy jakimiś miejscowościami w Polsce. Najwygodniejsze do użucia byłyby na pewno kody pocztowe - aby jednoznacznie określić o którą miejscowość nam chodzi, a dodatkowo określa nam nawet dzielnicę dużego miasta. I teraz. Prawdopodobnie zrobienie bazy typu

kod każdej miejscowości - kod każdej miejscowości i przypisanie do tego odległości nie wchodzi w grę (99 999 kodów * 99 998 = ok 1e10 możliwości).


Sprawa jeszcze bardziej komplikuje się, gdy mamy np. 3, 4, 5 nie mówiąc już o więcej miejscowościach "przelotowych".

Wpadłem na pomysł aby każdą miejscowość opisać szerokością i długością geograficzną i na tej podstawie obliczać odległości. Ciekawe czy jest to gdzieś dostępne? - wsp. geograficzne

A może lepiej zrobić sobie układ współrzędnych x,y ze środkiem np. w lewym dolnym "rogu" Polski. I mając do dyspozycji 99 999 odległości (oczywiście po kodach pocztowych) z 3 różnych miejscowości (co daje nam 299 997 kodów) możemy policzyć współrzędne każdej innej miejscowości

A wy co proponujecie?

Pozdrawiam Wszystkich - małych i dużych (IMG:http://forum.php.pl/style_emoticons/default/smile.gif)

[Aztech]

Co do algorytmu poszukiwania najkrótszj drogi z punktu A bo B jesli znamy wszystkie odleglosci pomiedzy poszczegolnymi miastami najlepszy/najprotszy w implementacji jest algorytm DIJKSTRY.
Baze musialbys zorganizowac tak aby miec podane:
pierwsza tabela np MIASTA
MID | NAZWA | WSP_GEOGR/KOD_POCZT
ws geogr/kod_poczt tylko w przypadkach gdy miasta o tych samych nazwach, zeby si nie pomylic
druga tabelka z polaczeniami np taka
TID | MID | MID2 | ODL
w Polaczeniach masz MID->MID2 i odleglosc miedzy nimi
(*) zapytaniem wyciagasz odleglosci
(*) tworzysz graf odleglosci miedzy miastmi zapisany w tabeli
(*) tworzysz pomocnicza tabele posluzaca ci do przeszukiwania najkrotszej drogi z miasta A do B
(*) liczysz algorytmem DIJKSTRY - banalny

Nie wiem jak to zadziala w php bo to problem przeniesiony czysto z programowania (przykladowa baza towrzona na kolanie), ale mysle ze dalo by sie to zrobic

Jesli nie, to mze chociaz na jakies rozwiazanie naprowadzi

P.S. (*) Algorytm ma taka zalete ze dokladnie pokaze trase przez jakie miejsowosci bo beda one zapisane w tabelce pomocniczej
(*) jesli dopiszemy dodatkowa wage reprezentujaca czas do polaczeń to bedziemy mogli dodatkowo dobierac droge pod katam optymalnego czasu, bo przeciez nie zawsze najkrósza odległość jest najlepsza