[Talk-cz] MTB mapa vyhledava trasy

Martin Tesar osmmtb na gmail.com
Úterý Červen 18 14:02:56 UTC 2013


Ahojte,

určitě je potřeba doplnit nějaký popis toho, jak algoritmus funguje a jak
se zadané váhy projeví na výsledku.

Typický případ užití je asi takový, že si nastavím šablonu (vy tomu říkáte
speciální profil), která je mi nejbližší, např. MTB easy. Samo o sobě to
hledá poměrně dobře, to snad nikoho neodradí. Když mám pocit, že to pořád
hledá trasy které nechci, doladím konkrétní parametr. To jsou ty "advanced
settings". Třeba mtb:scale=0 nechám na "Ideální", ale mtb:scale=1 snížím na
"Vhodný". Pak to automaticky upraví všem odpovídajícím cestám váhu.

Jakmile je uživatel se svým profilem spokojený, může si ho uložit a kdykoli
znova nahrát a použít, aby nemusel všechno dokola klikat.

Nějaký model který by nastavování zjednodušil by se určitě hodil. Hlavním
cílem mojí práce ale bylo právě to, aby si mohl každý nastavit všechno jak
chce, to si myslím, že jinde chybí.

Jak by se ta působivost počítala z dostupných dat si moc neumím představit,
obtížnost by asi šla.

Snad jsem aspoň trochu vysvětlil některé nejasnosti. Díky za nápady,
Martin


Dne 13. června 2013 23:51 Jan Kouba <kouba.honza na gmail.com> napsal(a):

> **
>
> Ahoj,
>
>
>
> a) Já jsem předpokládal, že jedna cesta má jen jednu přiřazenou působivost
> a namáhavost, takže by se daly ty dva ůseky brát každý jako zvláštní cesta
> a mělo by to fungovat. Kvůli efektivitě, je ale asi takové kombinování
> úseků do jedné cesty potřeba. Kdyby se váha cesty počítala jak píšu, tedy:
>
>
>
> <váha cesty> = <délka cesty>*(<namáhavost> - <obtížnost>*<působivost>)
>
>
>
> zkráceně:
>
> v = d*(n - o*p)
>
>
>
> pak tedy:
>
> v = v_1 + v_2
>
> = d_1*(n_1 - o*p_1) + d_2*(n_2 - o*p_2) =
>
> = (d_1*n_1 + d_2*n_2 - o*(d_1*p_1 + d_2*p_2))*(d_1+d_2)/(d_1 + d_2)
>
> = (d_1+d_2) * ((d_1*n_1+d_2*n_2)/(d_1+d_2)
>
> - o*(d_1*p_1 + d_2*p_2)/(d_1 + d_2))
>
> = d*(n - o*p)
>
>
>
> tak mi vychází, že
>
>
>
> n = (d_1*n_1+d_2*n_2)/(d_1+d_2)
>
> p = (d_1*p_1 + d_2*p_2)/(d_1 + d_2)
>
>
>
> tedy že n a p jsou vážené průměr podle délky cesty.
>
>
>
>
>
> b) Ano, speciální profily pro pěší, horská, sliniční kola, auta, ... jsou
> určitě třeba. Já jsem se snažil navrhnout něco, co by fungovalo pro horská
> kola. O tom, jestli by to šlo použít i na jiné dopravní prostředky jsem
> zatím moc nepřemýšlel, ale příjde mi, že u působivosti by se dala použít
> stejná hodnota pro všechny dopravní prostředky, avšak namáhavost je pro
> každý dopravní prostředek jiná.
>
>
>
> c) Mít možnost nastavovat více parametrů by jistě šlo, ale hodně by
> záleželo, jak by ty parametry byly vysvětleny, aby to lidé opravdu
> používali a nenechávali všechno v "default" nastavení.
>
>
>
> Navíc s každým přidaným parametrem se znásobí počet různých ohodnocení
> grafu cest počtem hodnot parametru. Takže když budeš mít 5 parametrů každý
> s možností výběru 4 hodnot, tak se musí počítat 4^5 = 1024 různých
> ohodnocení hran. To teď není problém, protože podle toho, co psal Martin
> Tesař, se teď ohodnocení stejně počítá znova při kažném dotazu, ale časem
> by to možná chtěl zrychlit nějakou předgenerovanou vyhledávací strukturou.
> V tom se sice moc neorientuju, ale vím, že například algoritmus, který se
> používá na http://project-osrm.org/, potřebuje pro každé ohodnocení
> grafu, podle kterého se vyhledává, prostor úměrný velikosti grafu. A je
> dost možné, že ostatní vyhledávací struktury na tom budou dost podobně. A
> tady už je dost velký rozdíl, jestli máš 1024 různých ohodnocení, nebo jen
> 5.
>
>
>
> A k těm tebou navrhovaným parametrům. Silnice vyšší třídy by měly
> namáhavost stejnou jako jakákoliv jiná cesta (třeba i lesní) s asfaltovým
> povrchem, ale působivost by měla jednu z nejmenších, takže ten navržený
> algoritmus by se té cestě stejně snažil vyhnout. A když by se jí nevyhnul,
> tak uživatel může do trasy přidat pár bodů navíc, které zajistí, že to po
> té silnici nepovede.
>
>
>
> Pokud chce někdo jezdit pouze po kvalitních cestách tak nevím proč by měl
> používat profil pro MTB. Ať použije profil pro trekingové kolo, kde budou
> nejspíš všechny lesní cestičky zakázané.
>
>
>
> A že by někdo chtěl preferovat pouze rovinatý terén se mi taky moc nezdá.
> Například jízda po rovině po cestě s mtb:scale=4 je určitě víc namáhavá než
> jet do kopce s 12% stoupáním, ale po asfaltu. Myslím si, že uživatel může
> spíš preferovat cesty, které nejsou moc namáhavé. To ale zařídí tak, že si
> obtížnost nastaví na minimum.
>
>
>
>
>
> Honza
>
>
>
>
>
>
>
> Dne Čt 13. června 2013 02:59:35, Jan Bilak napsal(a):
>
> a) Jaké vlastnosti mají namáhavost a působivost? Tedy mám dva úseky cesty
> s namáhavostí n_1 a n_2 a působivostí p_1 a p_2, jaká bude namáhavost n a
> působivost p složené cesty z těchto dvou úseků? Součet, maximum, vážený
> průměr s váhou délky úseku, ...?
>
>
> b) Nějaké pojmenované profily mi dávají smysl, protože řekněme jízda na
> horském kole a na silničním (pokud pominu, že jde o MTB mapu) je z principu
> jiná a nelze dost dobře vyjádřit zmíněným vzorečkem.
>
>
> c) Mě dává smysl mít možnost nastavit i další parametry (jako nějaké
> "advanced settings"). Např. za žádných okolností nechci jezdit po silnici
> vyšší třídy. Nebo naopak třeba chci jezdit pouze po kvalitních cestách
> (asfalt apod.) a rozhodně nechci jezdit po nějaké lesní cestičce. Nebo
> maximálně preferuji rovinatý terén a kvalita povrchu je pro mě druhořadá.
> Jen bude vhodné nastavení předělat tak, aby bylo lépe pochopitelné pro
> běžné uživatele. Naopak pro pokročilé uživatele podrobněji vysvětlit, jaký
> to má vlastně dopad na algoritmus hledající cestu.
>
>
> Honza
>
>
>
> Dne 13. června 2013 2:24 Jan Kouba <kouba.honza na gmail.com> napsal(a):
>
> Ahoj,
>
>
>
> nevadí, já jsem jen tak doufal, že když už umíte počítat výškový profil
> trasy, tak třeba už máte pro každou cestu její profil spočítaný a uložený.
>
>
>
>
>
>
>
> Mám ještě připomínku k těm parametrům vyhledávání. Teď je to strašně
> komplikované. Pokud jsem dobře počítal, tak je tam kolem 50 různých
> nastavení, což musí spolehlivě odradit každého.
>
>
>
> Navíc není vůbec zřejmé, jak se ta nastavení parametrů projevují v
> ohodnocení grafu cest. Jde třeba nějak nastavit, aby highway=path s
> mtb:scale=0 byla víc vhodná než highway=path s mtb:scale=1? Nejak se mi to
> nepodařilo.
>
>
>
> Pro vyhledávání trasy pro horské kolo by mi přišlo ideální, kdyby uživatel
> měl jen jedno nastavení a to "obtížnost". Tím by říkal, o kolik obtížnější
> může trasa být v porovnání s nejméně obtížnou trasou, která vůbec nebere v
> potaz vhodnost cest.
>
>
>
> Ohodnocení cest by se pak počítalo takto: Pro každou cestu a směr by se
> braly v úvahu dvě veličiny, "namáhavost" a "působivost", a ty by se pak
> spolu s nastavenou obtížností použily k vypočítání celkové váhy cesty.
>
>
>
> Namáhavost by říkala, kolik sil stojí projet cestu v daném směru.
> Například asfaltová cesta, která vede po rovině, patří k nejméně namáhavým,
> zato pěšina s mtb:scale:uphill=5 ve směru do kopce nebo schody ve směru do
> kopce, kde se musí tlačit, patří k těm nejvíce namáhavým. Podobně cesta do
> kopce je více namáhavá, než stejná cesta po rovině a ta je více namáhavá
> než stejná cesta s kopce.
>
>
>
> Působivost by pak popisovala něco jako radost z projetí cesty. Radost může
> být buď ze samotné jízdy, nebo z okolí. Například radost z jízdy po silnici
> první třídy je většinou velmi malá, zato radost z jízdy po pěšině s
> mtb:scale=0 je většinou velmi velká. Podobně cesta která vede v rovině v
> poli s kukuřicí má asi méně působivé okolí než cesta, která vede v národním
> parku, národní přírodní rezervaci, CHKO, rezervaci UNESCO a tak podobně
> (tohle dostat z OSM dat by asi byl problém).
>
>
>
> Z namáhavosti a působivosti by se pak počítala výsledná váha cesty. To jak
> se tyto dvě veličiny zkombinují by pak záleželo na nastavení obtížnosti. Na
> nejlehčí obtížnost by algoritmus vybíral co možná nejméně namáhavé cesty s
> minimem objížděk (malá váha na působivosti). Čím těžší obtížnost, tím
> raději by algoritmus vybíral namáhavější, ale působivější cesty. Počítat by
> se to dalo asi takto:
>
> <váha cesty> = <délka cesty>*(<namáhavost> - <obtížnost>*<působivost>).
>
> Algoritmus pro hledání by pak hledal trasu s nejmenší vahou.
>
>
>
> Různých hodnot pro obtížnost by asi měl být nějaký malý počet (tak 5).
> Obdobným způsobem by se asi dala udělat i pěší navigace.
>
>
>
> Dává to smysl? Vím že tu neřeším žádné detaily, ale snad je z toho mého
> popisu zřetelny princip fungování. Co vy na to?
>
>
>
>
>
> Honza Kouba
>
>
>
>
>
>
>
>
>
> Dne Út 11. června 2013 09:25:31, Martin Tesar napsal(a):
>
> Ahoj,
>
> ze dne na den to není možné, ale dodělat by to časem určitě šlo.
>
> Výškový profil trochu (nekdy i trochu dost) přehání, musím se na to
> podívat.
>
> Diky za podněty,
>
> Martin
>
>
>
> Dne 10. června 2013 19:19 Jan Kouba <kouba.honza na gmail.com> napsal(a):
>
> Ahoj,
>
>
>
> nešlo by do toho ohodnocení cest nějak zahrnout taky nastoupané metry?
> Takhle mě to pořád žene někde po kopcích, přesto že se dá jet po pěkné
> cestě (mtb:scale=0, highway=track, tracktype=grade4) i mnohem víc po
> rovině.
>
>
>
> A taky mi přijde, že ten výškový profil ukazuje více nastoupaných metrů,
> než je to ve skutečnosti.
>
>
>
> Honza Kouba
>
>
>
>
>
> Dne Po 10. června 2013 12:12:29, Martin Tesar napsal(a):
>
> Ahoj,
>
> není to nic tajného. Nahraji data do PostGISu pomocí aplikace osm2po a
> "trochu" je upravím. Přímo v databázi pak vyhledává knihovna pgRouting,
> která má jako parametr SQL dotaz, v němž specifikuju výběr cest a jejich
> ohodnocení podle veškerých parametrů a omezení. Díky tomuto dynamickému
> ohodnocování každé cesty (hrany) je to celkem pomalé, oproti ostatním
> vyhledávačům.
>
>
> Martin
>
>
>
> Dne 10. června 2013 10:28 Václav Řehák <rehakv01 na gmail.com> napsal(a):
>
> Ahoj,
>
>
> zajímavý počin, hlavně možností parametrizace. Mohl bys prozradit něco víc
> o technickém řešení, pokud to není tajné :) Použil jsi nějaký hotový engine
> nebo udělal kompletně svůj?
>
>
> V.
>
>
>
> Dne 7. června 2013 18:14 Martin Tesar <osmmtb na gmail.com> napsal(a):
>
> Ahojte,
>
> spustil jsem první verzi vyhledávače tras na mtbmap.cz, který je určený
> pro cyklisty a turisty. Zatím je pokryto území ČR.
>
> Dá se různě parametrizovat, jak má výsledná trasa vypadat. Kvůli tomu je
> to docela pomalé, ale výsledek snad stojí za to. Vyzkoušejte, sdílejte a
> těším se na ohlasy.
>
>
> Martin
>
> --
> Martin Tesar
> http://mtbmap.cz/ <http://tchor.fi.muni.cz:8080/>
>
>
> _______________________________________________
> Talk-cz mailing list
> Talk-cz na openstreetmap.org
> http://lists.openstreetmap.org/listinfo/talk-cz
>
>
>
> _______________________________________________
> Talk-cz mailing list
> Talk-cz na openstreetmap.org
> http://lists.openstreetmap.org/listinfo/talk-cz
>
>
>
>
> --
> Martin Tesar
> http://mtbmap.cz/ <http://tchor.fi.muni.cz:8080/>
>
>
>
>
> _______________________________________________
> Talk-cz mailing list
> Talk-cz na openstreetmap.org
> http://lists.openstreetmap.org/listinfo/talk-cz
>
>
>
>
> --
> Martin Tesar
> http://mtbmap.cz/ <http://tchor.fi.muni.cz:8080/>
>
>
>
>
> _______________________________________________
> Talk-cz mailing list
> Talk-cz na openstreetmap.org
> http://lists.openstreetmap.org/listinfo/talk-cz
>
>
>
>
>
> _______________________________________________
> Talk-cz mailing list
> Talk-cz na openstreetmap.org
> http://lists.openstreetmap.org/listinfo/talk-cz
>
>


-- 
Martin Tesar
http://mtbmap.cz/ <http://tchor.fi.muni.cz:8080/>
------------- další část ---------------
HTML příloha byla odstraněna...
URL: <https://lists.openstreetmap.org/pipermail/talk-cz/attachments/20130618/73ec8d3a/attachment.html>


Další informace o konferenci talk-cz