[Talk-cz] MTB mapa vyhledava trasy

Jan Kouba kouba.honza na gmail.com
Úterý Červen 18 22:07:44 UTC 2013


Ahoj, 

popis jak se nastavení advanced parametrů projeví ve vyhledávání je určitě 
potřeba. Teď je to dost takové tápání ve tmě (zajímalo by mě, kolik procent 
lidí, co to vyhledávání použili, tak použili i nějaké advanced settings). Teď 
se to prostě nedá nastavit tak, jak člověk chce, protože chybí ten popis.

Působivost (asi jsem tomu měl raději říkat atraktivnost) má vyjadřovat jak je 
cesta atraktivní pro toho, kdo se po ní pohybuje, bez ohledu na to, jak je 
obtížné po ní projet/projít. Z dostupných dat by se myslím dalo poměrně snadno 
porovnávat atraktivitu například následovně:

highway: 
path >= track >= service >= unclasified >= tertiary >= secondary ...

tracktype
grade5 >= grade4 >= ...

surface
grass, ground, fine_gravel >= asphalt, concrete, concrete:plates

motor_vehicle
no > yes

když na uzlu cesty (nebo poblíž cesty) je tourism=yes/attraction/viewpoint, 
tak to zvedá atraktivitu.


Z dostupných dat by se taky dalo zjisti, ale nejspíš už ne tak snadno, 
například následující: 

když cesta vede přes nějaké chráněné území (NP, NPR, PR, ...) tak to zvedá 
atraktivitu. 

Když cesta vede ve svahu, tak to zvedá atraktivitu.


Ideální by bylo, kdyby v OSM existoval nejaký tag, který by popisoval právě tu 
atraktivitu cesty, a kdyby ho také mapeři používali. O žádném takovém ale 
nevím.


Honza Kouba



Dne Út 18. června 2013 16:02:56, Martin Tesar napsal(a):

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/



_______________________________________________
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/





_______________________________________________
Talk-cz mailing list
Talk-cz na openstreetmap.org
http://lists.openstreetmap.org/listinfo/talk-cz





-- 
Martin Tesar
http://mtbmap.cz/





_______________________________________________
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/



------------- další část ---------------
HTML příloha byla odstraněna...
URL: <https://lists.openstreetmap.org/pipermail/talk-cz/attachments/20130619/0720c80c/attachment.html>


Další informace o konferenci talk-cz