Pozor! wiki.freemap.sk je archivovaná a už do nej nie je možné prispievať. Užitočné stránky budú premigrované na oficiálne wiki stránky slovenskej OpenStreetMap komunity.

Revision [94]

This is an old revision of RoutingProposal made by JozefVince on 2008-03-20 00:35:43.

 

Takze moje nic-nerobenie vo forme rozmýšľania vyústilo do týchto záverov... no a samozrejme potrebuje aspon okomentovat
Stránka ma ACL READ (dodi, lubos) - nechcem ju este davat verejnú, aj ked je to iba wiki

Routing Proposal


Úložisko routing dát

pre rýchly štart som si vybral SQLite, perl na predspracovanie a prípravu dát... ak uvidim, že to vedie k nejakému výsledku, možno sa zamyslím nad nejakým binárnym storage formátom.

Spracovanie OSM dát

  1. načítať slovakia.osm do osm.db (SQLite databazy)
  2. zrušiť všetky neroutovatelné data (lesy, voda, landuse...) - tu pripomínam sám sebe, že landuse može byť potrebné pre spočítanie maxspeed pre cesty vramci landuse, zatiaľ však ignorujme túto "drobnosť"
  3. nájsť všetky RoutingNodes. to sú tie, ktoré sú na začiatku a na konci každej cesty, a body, v ktorých sa spájajú dve alebo viac ciest
  4. rozbiť všetky cesty na RoutingSegments - to sú také úseky ciest, ktoré medzi jednotlivými RoutingNodes
  5. pre každý RoutingSegment spočítať PenaltyVector / RoutingFeatureWeightVector [w1,w2,...wN] - vyjadruje, že pre RoutingSegment(rsX) tvorený RoutingNode(rnA) a RoutingNode(rnB) sú vybrané RoutingFeatures [rf1,rf2,...rfN] zastúpené príslušnou váhou - dobre zvolené RoutingFeatures a dobre zvolené výpočty RoutingFeatureWeightVector su predpokladom dobrého vyhľadávania cesty podľa zvolených RoutingProfile -ov
  6. treba poriešiť jednosmenky - t.j. bude si povieme, že RoutingSegment(rsX1) [ RoutingNode(rnA) , RoutingNode(rnB) ] je iný ako RoutingSegment(rsX2) [ RoutingNode(rnB) , RoutingNode(rnA) ], pritom RoutingSegment(rsX1) a RoutingSegment(rsX2) môžu mať rozdielne váhy pre RoutingFeatureWeightVector (napriklad kvoli tomu, že jeden smer je z kopca a druhý do kopca - súhlasím, že zachádzam do extrému, ale ja to rád)
  7. musím ešte spomenúť RoutingProfile [ c1,c2,...cN ] - vyjadrujúci ktorý faktor z RoutingFeatureWeightVector -a má aký vplyv na výber trasy
Kolo druhé
Ak uvažujem o možnosti plánovať cestu "easy", a neskôr samozrejme TurnRestrictions (až bude OSM rozhodnute, ako si želá modelovať zákazy odbočenia), je potrebné brať do úvahy aj vzájomné vzťahy medzi RoutingSegments, ktoré majú spoločný RoutingNode. Napr. je viac easy odbočiť z hlavnej cesty na vedlajšiu ako naopak, zabočiť doprava je jednoduchšie ako zabočiť doľava.

Routing Algorithm

o Algoritme A* teda vela neviem, len toľko, že sa podoba na Dijkstra, len používa nejakú heuristiku na odhad z aktuálnej pozície do cieľa. Nesnaži sa generovať všetky možné trasy naraz, ale vylešpuje vždy tú, ktorá dáva najmenší súčet prejdenej cesty + heuristika do ciela.

O heuristike - najjednoduchšia a naj naivnejšia je euklidova vzdialenosť do cieľa, len nemám zatiaľ premyslené, ako do tej heuristiky pretaviť hodnoty RoutingFeatureWeightVector.

Yo... celkov8 prejdená trasa je SUMA ( RoutingProfile [ c1,c2,...cN ] x RoutingFeatureWeightVector(RoutingSegment, [w1,w2,...wN]) ) + Heuristika - a táto sa minimalizuje

Valid XHTML :: Valid CSS: :: Powered by WikkaWiki