<div dir="ltr"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span style="font-family:arial,sans-serif;font-size:13px">Pra esse algoritmo só importa a velocidade atribuída a cada trecho das<br>
</span><span style="font-family:arial,sans-serif;font-size:13px">vias (e a atribuição pode não ter relação direta com aquilo que foi<br></span><span style="font-family:arial,sans-serif;font-size:13px">mapeado, só indireta). </span></blockquote>
<div><br></div><div>Não é bem assim.  Na graduação se ensina o Djkstra que leva a maioria das pessoas focar apenas no custo de percurso.  Mas uma aplicação real é mais complexa. O tamanho do grafo é um fator de extrema relevância. </div>
<div><br></div><div>Acho que tu não leste o artigo sobre Hierarchy Contraction.  Existe uma otimização que é feita nos dispositivos móveis.  Enfim, vou resumir: para rotas de longa distância, em que analisar o grafo todo seria muito custoso tanto em termos de desempenho quanto de memória, é feito um descarte de vias de baixa hierarquia.  As vias de menor hierarquia só passam a ser computadas nas proximidades dos pontos de origem e de destino.  Por causa desse descarte, o cálculo de rotas longas pode falhar em smartphones, tablets e GPSs para mapas mal desenhados.</div>
<div><br></div><div><br></div><div><br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">Em 19 de julho de 2014 11:56, Fernando Trebien <span dir="ltr"><<a href="mailto:fernando.trebien@gmail.com" target="_blank">fernando.trebien@gmail.com</a>></span> escreveu:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Só acrescentando uns detalhes. Um resumo da ópera: em alguns sistemas,<br>
a classificação pode ter um efeito no roteamento, mas fundamentalmente<br>
o mais importante é mapear as características da via (velocidade<br>
máxima, superfície, etc.).<br>
<br>
Pra esse algoritmo só importa a velocidade atribuída a cada trecho das<br>
vias (e a atribuição pode não ter relação direta com aquilo que foi<br>
mapeado, só indireta). Se não for mapeada a velocidade máxima das<br>
vias, então a maioria dos roteadores tenta "adivinhar" a velocidade a<br>
partir da classificação. Como exemplo, eis aqui [1] como o OSRM faz<br>
essa adivinhação (lembrando que é um serviço mais voltado às<br>
características do trânsito na Europa).<br>
<br>
Então, sim, a classificação é importante para o roteamento caso não<br>
seja mapeada a velocidade máxima. Mas, fundamentalmente, o mais<br>
importante para o roteamento é a velocidade atribuída à via. Existem<br>
casos em que uma primária urbana tem velocidade reduzida num trecho<br>
curto e isso faz diferença pro roteamento decidir mandar o usuário por<br>
ali ou não. Só seria mapear para a aplicação se alguém mudasse a<br>
classificação naquele trecho por causa da velocidade, para forçar um<br>
roteador a evitar o trecho. (Um problema é que muita gente faz isso.)<br>
<br>
Especificamente para o Garmin/mkgmap, parece que ainda existe o<br>
conceito de "classe de velocidade", que não é nem a classificação da<br>
via (que se reflete no desenho), nem a velocidade máxima (que produz<br>
os alertas de velocidade). Essa é uma velocidade estimada de trânsito<br>
que no mkgmap [2] pode ter regras até bem complexas de derivação (nos<br>
exemplos que eu vi por aí o pessoal estava derivando esse campo a<br>
partir de uma combinação da classe da via e da velocidade máxima). Até<br>
daria pra mapear no OSM uma velocidade "esperada" pra via (que então<br>
se traduziria diretamente nessa velocidade do Garmin), mas isso é<br>
complicado de padronizar e por isso pode gerar divergências (e guerras<br>
de edição) e até pode acabar não sendo usado. [3] Algumas abordagens<br>
melhores são coletar a velocidade média [4] e monitorar o tráfego [5].<br>
Com essas duas abordagens, a classificação se torna irrelevante pro<br>
roteamento (por exemplo, no caso de uma primária estar sempre<br>
congestionada e uma secundária paralela estar sempre livre).<br>
<br>
[1] <a href="https://github.com/DennisOSRM/Project-OSRM/blob/master/profiles/car.lua" target="_blank">https://github.com/DennisOSRM/Project-OSRM/blob/master/profiles/car.lua</a><br>
[2] <a href="http://www.mkgmap.org.uk/doc/pdf/style-manual.pdf" target="_blank">http://www.mkgmap.org.uk/doc/pdf/style-manual.pdf</a> seção 4.6.5<br>
[3] <a href="http://wiki.openstreetmap.org/wiki/Talk:Proposed_features/traffic_speed#Practicality_of_Using_Info_in_Router" target="_blank">http://wiki.openstreetmap.org/wiki/Talk:Proposed_features/traffic_speed#Practicality_of_Using_Info_in_Router</a><br>

[4] <a href="http://wiki.openstreetmap.org/wiki/Average_speed_per_way" target="_blank">http://wiki.openstreetmap.org/wiki/Average_speed_per_way</a><br>
[5] <a href="https://lists.openstreetmap.org/pipermail/talk/2012-August/063985.html" target="_blank">https://lists.openstreetmap.org/pipermail/talk/2012-August/063985.html</a><br>
<br>
2014-07-15 8:30 GMT-03:00 Paulo Carvalho <<a href="mailto:paulo.r.m.carvalho@gmail.com">paulo.r.m.carvalho@gmail.com</a>>:<br>
<div><div class="h5">> Amigos,<br>
><br>
>     Para compreender a razão de não quebrar a hierarquia de vias nos<br>
> pequenos trechos que rodovias passam por cidades, recomendo esta leitura:<br>
><br>
> <a href="http://en.wikipedia.org/wiki/Contraction_hierarchies" target="_blank">http://en.wikipedia.org/wiki/Contraction_hierarchies</a><br>
><br>
>    Aos que já estão com o argumento "isso é mapear para aplicação" na ponta<br>
> da língua rogo um momento para parar e pensar:<br>
><br>
> "For routing software to work well, the underlying map data must be of good<br>
> quality. Essentially this means that ways that should be connected are in<br>
> fact connected, one-way roads are tagged, turn restrictions are mapped, and<br>
> so on. You should be familiar with the Map Features used, in particular see<br>
> OSM tags for routing to understand the tags specific to routing." (grifo<br>
> meu)<br>
><br>
> Palavras da própria comunidade OSM.<br>
><br>
> Fonte:  <a href="http://wiki.openstreetmap.org/wiki/Routing" target="_blank">http://wiki.openstreetmap.org/wiki/Routing</a><br>
><br>
> [ ]s<br>
><br>
> Paulo<br>
><br>
</div></div>> _______________________________________________<br>
> Talk-br mailing list<br>
> <a href="mailto:Talk-br@openstreetmap.org">Talk-br@openstreetmap.org</a><br>
> <a href="https://lists.openstreetmap.org/listinfo/talk-br" target="_blank">https://lists.openstreetmap.org/listinfo/talk-br</a><br>
><br>
<span class="HOEnZb"><font color="#888888"><br>
<br>
<br>
--<br>
Fernando Trebien<br>
<a href="tel:%2B55%20%2851%29%209962-5409" value="+555199625409">+55 (51) 9962-5409</a><br>
<br>
"Nullius in verba."<br>
<br>
_______________________________________________<br>
Talk-br mailing list<br>
<a href="mailto:Talk-br@openstreetmap.org">Talk-br@openstreetmap.org</a><br>
<a href="https://lists.openstreetmap.org/listinfo/talk-br" target="_blank">https://lists.openstreetmap.org/listinfo/talk-br</a><br>
</font></span></blockquote></div><br></div>