Forum PHP.pl

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

A Google to wyłączyli?
http://www.google.com/search?hl=pl&q=wsp%C...olskich&spell=1
a wynika z tego
http://www.gugik.gov.pl/komisja/wydawnictwa.htm
Szczególnie 7 publikacja na liście.

To podobnie jak opisywałem

1. Skąd wziąść taką bazę danych
2. A co w przypadku kilku miescowości, skąd wiadomo, które trzeba po kolei wziąść? Np. ze Szczecina przez Warszawe do Krakowa, a nie że ze Szczecina do Warszawy przez Kraków?
3. Szukałem google i szukałem też w archiwum grupy

Pozdrawiam i dzięki

popatrz sobie na strone http://www.pilot.pl i zobacz jak oni to rozwiazali ;]

Ten post edytował Ive 18.10.2004, 22:06:02

Czy szukanie jest takie trudne hmm - no - podejrzewam ze trzeba by zapisac odleglosci pomiedzy sasiednimi miastami w bazie a potem rekurencja ....

witam ...

widze 2 rozwiazania ... oba moga sprawic trudnosci w implementacji ...
1. wpisac kazde wieksze miasto do bazy i w kolumnach N S W E wpisac najblizsze miasto obok ... do wyznaczania drogi musialby byc napisany algorytm sprawdzajacy miasto po miescie ... nie mam pojecia jak bedzie z wydajnoscia takiego systemu ...

2. wpisac do bazy miasta wraz ze wsp. geograficznymi i sprawdzac "pasami" ... czyli z miasta A + n stopni w lewo i w prawo z gory nadol wszystkie miasta ktore sie mieszcza w tych granicach ...

jest jeszcze dodatek do mysql do zabaw z geometria [mozna obliczyc dlugosc odcinka przechodzacego przez dane typu piont - miasta] link:http://dev.mysql.com/doc/mysql/en/Geometry..._functions.html
tez moze zadzialac ...

pozdrawiam

Nie radzę się wzorować. Tak naprawdę obliczanie odległości działa tylko w linii prostej a i to niedokładnie (wiem bo sam to pisałem).
Ale faktycznie najlepszym sposobem jest stworzenie bazy współrzędnych geograficznych wszystkich miast, przeliczenie tego na "płaski" układ współrzędnych (wzory są dość skomplikowane) i następnie przeliczenie różnicy położeń na odległość.
Te płaskie współrzędne też warto trzymać w bazie.

1. Zapisujesz w bazie punkty (miasta) wraz z ich wpólrzędnymi geograficznymi.
2. Zapisujesz odcinki drogi łączące sąsiednie miejscowości
3. Odległośc w linii prostej obliczasz tak jak podał lunter w pierwszym poście.
4. Odległość "prawie drogową" obliczasz szukając najkrótszej drogi w grafie. Szukać materiałów możesz nt. w tych wynikach Googli:
http://www.google.com/search?q=algorytm+po...-a&start=0&sa=N

Obliczasz sume dróg prowadzących do celu. Jełsi masz zaznaczone miasto przelotowe, liczysz : ( A -> przelot1 ) + ( przelot2 -> przelot2 ) + ... + (przelotN -> = Xszukane
Nie ma ograniczeń w ilości przelotowych miast.

Tylko skąd wziąść bazę danych z położeniami geograficznymi miejscowości??

Cześć,

zainteresował mnie ten problem bo miałem zapytanie od klienta, więc podpowiadam, że firma emapa sprzedaje bazy z położeniem geograficznym. Dodatkowo mogę pomóc definicję wzoru do określania odległości...

Powodzenia!!

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

zobacz
http://pusiek.org/download.php

http://www.transport.e-delta.com.pl/wspolrzedne.php
http://www.transport.e-delta.com.pl/baza_m...fabetycznie.php

Sorki ale niemialem czasu czytac calego forum chodzi Ci o obliczenie odległości dorgowej czy odległosci po prostej.

1. Bo jeśli drogowej to nieobejdzie się bez znajomości odległości od wszystkich miejscowości.
2. Jeśli po drodze prostej to no problem

Warto wiedzieć również o tym, że


Pozwala to na przechowywanie informaji o lokalizacjach geograficznych, oraz na obliczanie np. najkrótszej drogi, wszystkich możliwych tras itp.
Będzie to też o wiele wydajniejsze, niż przeliczanie takich informacji w php (w końcu jest to algorytm n-złożony) a MySQL potrafi to chyba całkiem sprytnie indeksować.

Algorytm (tak na prawde zwór) można sciągnąć za darmo ze strony www.bazamiejscowosci.pl (prawa strona, dział: Wzór obliczania odległości).
Dostępny jest kod w php, javie i arkusz Excel'owy.

Sama baza jest już płatna ale posiada wszystkie miejscowości w Polsce wraz ze współrzędnymi geograficznymi.

Ten post edytował lenrok258 5.11.2012, 22:44:41

Chwali się, że relatywnie nowi użytkownicy czytają forum. Ale że odpowiadają na tak stare posty - to już mnie lekko zadziwia...

Skoro już archeolodzy dotarli na forum

Temat był niedawno poruszany na forum. Kody pocztowe można wyciągnąć ze strony Poczty Polskiej, na ich podstawie wyciągnąć współrzędne z Google Maps i stworzyć sobie taką bazę.