Chcę napisać program do wyznaczania optymalnej trasy przejazdu (w mieście, nie pomiędzy miastami). Potrzebuję do tego grafu, który będzie odwzorowywał mapę (krawędź to ulica, wierzchołek to skrzyżowanie, konkretny adres itp.). Mapa rzecz jasna musi być prawdziwa. Jak taki graf stworzyć?
Kolejny problem - mając już graf, jak znaleźć na nim konkretne adresy? Bo jeśli założyć, że wierzchołek symbolizuje jakiś tam adres, to ... nawet nie chcę sobie wyobrażać jak ten graf musiałby wyglądać. Rozwiązanie jakie przychodzi mi do głowy to użytkownik wprowadza interesujące go adresy, i dopiero wtedy tworzony jest graf z tymi adresami. Jest to rozwiązanie wystarczające na potrzeby mojego programu, ale jeśli problem nie jest bardzo złożony, to dlaczego ograniczać się do iluś adresów.
- Open Street Map udostępnia graf ulic w postaci XMLa i z powodzeniem można to wykorzystać do nawigacji.
- Jw, Open Street Map udostępnia nie tylko grafy GPSowe ale także informacje o adresach dla tych punktów.
Chcę przekształcić graf z tego pliku XML, do postaci reprezentującej graf skierowany w pamięci komputera (najlepszą opcją będzie chyba macierz sąsiedztwa).
Pierwszy problem, który dostrzegłem jest następujący - konkretne adresy budynków są zdefiniowane jako drogi, w których pierwszy wierzchołek jest jednocześnie ostatnim (są to po prostu obwody budynków). Wierzchołki nie są podłączone do drogi, inaczej mówiąc z grafu - budynku nie ma wyjścia na drogę. Zatem jak wpiszemy jakiś adres jako punkt startowy, to nigdzie nie dojedziemy. Jak ten problem rozwiązać?
Kolejny problem to niektóre drogi nie zawierają informacji o dopuszczalnej maksymalnej prędkości, zatem jak obliczyć czas przejazdu danej trasy?
Wyczytałem gdzieś, że do wyznaczania tras samochodowych nie są mi potrzebne relacje oraz drogi takie jak chodniki, ścieki rowerowe itp i żeby to w pierwszej kolejności wywalić z pliku. To z drogami jest raczej logiczne, ale z tymi relacjami to prawda?
- No zauważ że generalnie tak jest zwykle że budynek nie leży na drodze. Możesz na przykład znaleźć sobie najbliższy punkt GPS leżący na prawdziwej drodze obok budynku i uznać go jako punkt startowy/docelowy.
- Niektóre drogi z tego co pamiętam miały zdefiniowany "typ" więc możesz po prostu ustalić sobie odgórnie limit prędkości dla dróg danego typu jeśli nie jest określony.
- No relacje raczej nie będą ci potrzebne, chyba że chcesz robić cuda w stylu wyszukiwanie linii autobusowej na danej trasie. Bo właśnie takie rzeczy są określane relacjami (że jakiśtam zbiór punktów jest trasą autobusu).
panDawid napisał(a):
Chcę przekształcić graf z tego pliku XML, do postaci reprezentującej graf skierowany w pamięci komputera (najlepszą opcją będzie chyba macierz sąsiedztwa).
Pierwszy problem, który dostrzegłem jest następujący - konkretne adresy budynków są zdefiniowane jako drogi, w których pierwszy wierzchołek jest jednocześnie ostatnim (są to po prostu obwody budynków). Wierzchołki nie są podłączone do drogi, inaczej mówiąc z grafu - budynku nie ma wyjścia na drogę. Zatem jak wpiszemy jakiś adres jako punkt startowy, to nigdzie nie dojedziemy. Jak ten problem rozwiązać?
Jeśli do krawędzi grafu dodasz info o nazwie ulicy to łatwo zawęzić krąg poszukiwań najbliższego wierzchołka dla danego budynku ( budynki w miastach zazwyczaj mają tagi addr:housenumber i addr:street ).
Warto też wziąć pod uwagę, że często-gęsto prosty odcinek drogi jest pocięty na mniejsze( bo prędkość, bo mostek, bo zmiana ilości pasów, etc.) i co za tym idzie takie wierzchołki nie dają możliwości zmiany kierunku jazdy i tworzą "pusty przebieg" przy pathfindingu. IMHO warto pomyśleć nad czymś w rodzaju "krawędzi skrótu" omijającej takie wierzchołki i łączącej bezpośrednio wierzchołki do których odwołuje się >2 odcinki.
panDawid napisał(a):
Kolejny problem to niektóre drogi nie zawierają informacji o dopuszczalnej maksymalnej prędkości, zatem jak obliczyć czas przejazdu danej trasy?
W terenie zabudowanym to proste: 05:00-23:00 => 50km/h, 23:00-05:00 => 60km/h. a jeśli jest inaczej to przeważnie jest to uwzględnione w OSM.
Pozostałe drogi też nie są problemem.
Drogi mają kategorie:
- autostrada
- droga ekspresowa
- droga krajowa
- droga wojewódzka
- droga powiatowa
- droga gminna
- droga wewnętrzna
Na podstawie kategorii można określić mniej więcej jakiej klasy jest droga. A poszczególne klasy mają z góry określone jaka jest maksymalna prędkość projektowa.
klasa A => 100-120
klasa S => 80-120 (teren zabudowany: 60-80)
klasa GP (kategoria: DK, ew. DW ) => 60-100
klasa G (kategorie: DK,DW,DP) => 50-70
klasa Z ( kategorie: DW,DP,DG) => 40-60
klasa L ( kategorie: DG, ew. DP ) => 30-50
klasa D ( kategorie: DG ) => 30-40
panDawid napisał(a):
Wyczytałem gdzieś, że do wyznaczania tras samochodowych nie są mi potrzebne relacje oraz drogi takie jak chodniki, ścieki rowerowe itp i żeby to w pierwszej kolejności wywalić z pliku. To z drogami jest raczej logiczne, ale z tymi relacjami to prawda?
Niby tak, ale z relacji możesz się dowiedzieć do jakiej kategorii( i zarazem jaka jest Vmax) należy droga albo określić teren zabudowany.
tajny_agent napisał(a):
Warto też wziąć pod uwagę, że często-gęsto prosty odcinek drogi jest pocięty na mniejsze( bo prędkość, bo mostek, bo zmiana ilości pasów, etc.) i co za tym idzie takie wierzchołki nie dają możliwości zmiany kierunku jazdy i tworzą "pusty przebieg" przy pathfindingu. IMHO warto pomyśleć nad czymś w rodzaju "krawędzi skrótu" omijającej takie wierzchołki i łączącej bezpośrednio wierzchołki do których odwołuje się >2 odcinki.
Jak dokładnie można rozwiązać ten problem z omijaniem wierzchołków? Myślałem nad stworzeniem drugiego grafu, w którym nie byłoby tych niepotrzebnych wierzchołków, ale wtedy będę tylko wiedział jaka jest długość najktórszej drogi i będę znał tę drogę tylko dla drugiego grafu, a porzebuję jeszcze tę drogę "narysować" na mapie.
@panDawid kiedy pisaliśmy nawigacje opartą o OSM to robiliśmy taką "kompresje ścieżek": jeśli masz 2 wierzchołki pomiędzy którymi jest trzeci połączony tylko z tymi dwoma to można taką ścieżkę kompresować pomijając ten wierzchołek. Jako że wyświetlalismy trasę na podstawie wyznaczonej ścieżki, to nie kompresowaliśmy takiej trójki jeśli punkty nie były bliskie współliniowym. Tzn jeśli była 3 którą można kompresować i kąt ABC był bliski180 stopni to znaczy że spokojnie można kompresować i wywalic wierzchołek B tworząc bezpośrednią krawędź AC. W ten sposób unikaliśmy "ścinania" zakrętów na wizualizacji ;)
Dzięki temu wierzchołków jest wyraźnie mniej i liczenie Dijkstry jest szybsze, a jednocześnie wizualizacja na tym specjalnie nie cierpi.