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 [99]

This is an old revision of RoutingProposal made by JozefVince on 2008-03-20 22:17:12.

 

Takze moje nic-nerobenie vo forme rozmýšľania vyústilo do týchto záverov... no a samozrejme potrebuje aspoň okomentovať
Stránka má ACL READ (dodi, lubos, deni,jarino) - nechcem ju ešte dávať verejnú, aj keď 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 veľa neviem, len toľko, že sa podobá 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.
- podmienkou je aby heuristika podcenovala cestu z aktu8lneho bodu do cieľa

Yo... celková 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