<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">Em 19 de julho de 2014 22:29, 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:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">Sabendo que há trabalhos cientificos publicados descrevendo bons<br>

algoritmos para esses ambientes e que não descartam quaisquer vias<br>
(mesmo as de classe bem inferior), acho que não devemos fazer<br>
adaptações no mapa em favor de algoritmos menos inteligentes. (Isso<br>
seria mapear para a aplicação.)<br></blockquote><div><br></div><div>Menos inteligentes????   Desculpa, Fernando, esse seu comentário foi um tanto arrogante.  Quando você tem restrição de recursos de hardware em dispositivos móveis você TEM que fazer otimização. Isso para mim é sinal de extrema inteligência.</div>
<div><br></div><div>E só uma palavra sobre artigos científicos: poucas vezes tratam-se de ideias praticáveis. O algoritmo Dijkstra é um exemplo.  Ninguém usa a forma tal como publicada pelo Dijkstra originalmente.  A indústria sempre faz várias melhorias para o mundo real.  Sei disso porque trabalho nos dois mundos e também porque estou escrevendo um artigo e não estou pensando em problemas de ordem prática.  A teoria já dá trabalho suficiente.  Isso não é pecado, é como o progresso funciona: cada especialista em sua área.  </div>
<div> </div><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">
<br>
Mas, ao mesmo tempo, acho que são muito raros os casos em que<br>
adaptações seriam necessárias para evitar problemas com esses<br>
algoritmos que descartam vias. A menos que eles estejam descartando<br>
até as vias primárias (arteriais urbanas), daí não tem como resolver<br>
mesmo.<br></blockquote><div><br></div><div>Não são raros não.  Você tem que pensar em para que a maioria dos usuários precisa de um mapa de ruas (Street Map):</div><div>a) Encontrar um lugar (geocoding);</div><div>b) Navegar até um lugar (roteamento);</div>
<div>c) Quase sempre em trânsito, com dispositivos móveis.</div><div><br></div><div>Se essas coisas não estão funcionando bem, elas procurarão alternativas e aí seu mapa será o mais puro do mundo mas vazio de propósito.  Se queres que o mapa se torne popular, TEM que pensar nas questões de ordem prática.</div>
<div><br></div><div>Acho que dá para conciliar os princípios do OSM com as questões práticas.  Mas interromper uma motorway com um trecho de residential vai quebrar o roteamento em muitas aplicações.  Não digo colocar tudo igual, mas não deixar as classes tão contrastantes conforme já exemplificado.</div>
<div><br></div><div>[]s</div><div><br></div><div>Paulo</div><div> </div><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">

<br>
2014-07-19 17:56 GMT-03:00 Paulo Carvalho <<a href="mailto:paulo.r.m.carvalho@gmail.com">paulo.r.m.carvalho@gmail.com</a>>:<br>
> E qual sua opinião sobre o descarte de vias de baixa prioridade nos<br>
> roteamentos de longa distância em ambientes com baixa memória e<br>
> processamento mais lento?<br>
><br>
><br>
> Em 19 de julho de 2014 12:58, Fernando Trebien <<a href="mailto:fernando.trebien@gmail.com">fernando.trebien@gmail.com</a>><br>
> escreveu:<br>
><br>
>> Li sim, há bastante tempo. Mas acho que estás confundindo as<br>
>> hierarquias do OSM com a hierarquia de atalhos emergente que o<br>
>> algoritmo de "contraction hierarchies" produz (que inclusive pode ter<br>
>> muito mais níveis do que os poucos que existem no OSM). Os atalhos<br>
>> servem apenas para acelerar outro algoritmo de roteamento qualquer<br>
>> (geralmente se adota uma variação do Dijkstra, e nesse caso as<br>
>> heurísticas acabam preferindo usar os atalhos). E a hierarquia do OSM<br>
>> não se converte em atalhos automaticamente. A sequẽncia das coisas é<br>
>> assim:<br>
>> - cada arco original representa a ligação de duas interseções no mapa<br>
>> - o peso dos arcos originais é atribuído por velocidade X distância,<br>
>> onde velocidade é uma estimativa feita de forma diferente por cada<br>
>> aplicação (algumas usam a classificação da via, outras não)<br>
>> - (contraction hierarchies) os arcos de atalho são gerados eliminando<br>
>> sequências de arcos cujo peso total é muito alto<br>
>> - (contraction hierarchies) um grafo é formado combinando os arcos<br>
>> originais com os atalhos<br>
>> - um algoritmo de busca em grafos é aplicado sobre o grafo resultante<br>
>> (< ou seja, esse algoritmo vai usar tanto atalhos quanto arcos<br>
>> originais, possivelmente se intercalando entre os dois)<br>
>><br>
>> Por exemplo, se você tiver dois caminhos de A a B com quase a mesma<br>
>> distância total, um deles é uma primária com velocidade de 10km/h, e<br>
>> outro é uma terciária intercalada com trechos de living_street que, na<br>
>> média, fica em torno de 80km/h, vai ser a primária que vai ser<br>
>> removida na geração dos atalhos e o segundo caminho (mais rápido,<br>
>> embora envolva vias de classificação inferior) que vai virar um<br>
>> atalho. O fato de ser primária, secundária, living street, não faz<br>
>> diferença alguma a princípio - a menos que exista um programa antes<br>
>> (como o mkgmap) que associa a classificação ao peso do arco (mais<br>
>> especificamente à velocidade, já que a distância é exata sempre). O<br>
>> OSRM, por exemplo, não associa quando a velocidade máxima é definida<br>
>> (ou seja, o segundo caso pode acontecer).<br>
>><br>
>> Enfim, isso é um detalhe, a classificação tem que estar bem feita por<br>
>> diversos motivos, mas (se formos pensar genericamente, para vários<br>
>> sistemas) não se pode ignorar o mapeamento da velocidade máxima das<br>
>> vias.<br>
>><br>
>> 2014-07-19 12:10 GMT-03:00 Paulo Carvalho <<a href="mailto:paulo.r.m.carvalho@gmail.com">paulo.r.m.carvalho@gmail.com</a>>:<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).<br>
>> ><br>
>> ><br>
>> > Não é bem assim.  Na graduação se ensina o Djkstra que leva a maioria<br>
>> > das<br>
>> > pessoas focar apenas no custo de percurso.  Mas uma aplicação real é<br>
>> > mais<br>
>> > complexa. O tamanho do grafo é um fator de extrema relevância.<br>
>> ><br>
>> > Acho que tu não leste o artigo sobre Hierarchy Contraction.  Existe uma<br>
>> > otimização que é feita nos dispositivos móveis.  Enfim, vou resumir:<br>
>> > para<br>
>> > rotas de longa distância, em que analisar o grafo todo seria muito<br>
>> > custoso<br>
>> > tanto em termos de desempenho quanto de memória, é feito um descarte de<br>
>> > vias<br>
>> > de baixa hierarquia.  As vias de menor hierarquia só passam a ser<br>
>> > computadas<br>
>> > nas proximidades dos pontos de origem e de destino.  Por causa desse<br>
>> > descarte, o cálculo de rotas longas pode falhar em smartphones, tablets<br>
>> > e<br>
>> > GPSs para mapas mal desenhados.<br>
>> ><br>
>> ><br>
>> ><br>
>> ><br>
>> ><br>
>> > Em 19 de julho de 2014 11:56, Fernando Trebien<br>
>> > <<a href="mailto:fernando.trebien@gmail.com">fernando.trebien@gmail.com</a>><br>
>> > escreveu:<br>
>> ><br>
>> >> 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]<br>
>> >> <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]<br>
>> >><br>
>> >> <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]<br>
>> >> <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<br>
>> >> <<a href="mailto:paulo.r.m.carvalho@gmail.com">paulo.r.m.carvalho@gmail.com</a>>:<br>
>> >> > 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<br>
>> >> > 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<br>
>> >> > 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<br>
>> >> > of<br>
>> >> > good<br>
>> >> > quality. Essentially this means that ways that should be connected<br>
>> >> > are<br>
>> >> > in<br>
>> >> > fact connected, one-way roads are tagged, turn restrictions are<br>
>> >> > mapped,<br>
>> >> > and<br>
>> >> > so on. You should be familiar with the Map Features used, in<br>
>> >> > particular<br>
>> >> > see<br>
>> >> > OSM tags for routing to understand the tags specific to routing."<br>
>> >> > (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>
>> >> > _______________________________________________<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>
>> >><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>
>> ><br>
>> ><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>
>> ><br>
>><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>
><br>
><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>
><br>
<span class=""><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></div>