[Talk-br] A importância de não quebrar a hierarquia das vias dentro de cidades.

Paulo Carvalho paulo.r.m.carvalho em gmail.com
Sábado Julho 19 15:10:59 UTC 2014


>
> Pra esse algoritmo só importa a velocidade atribuída a cada trecho das
> vias (e a atribuição pode não ter relação direta com aquilo que foi
> mapeado, só indireta).


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.

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.





Em 19 de julho de 2014 11:56, Fernando Trebien <fernando.trebien em gmail.com>
escreveu:

> Só acrescentando uns detalhes. Um resumo da ópera: em alguns sistemas,
> a classificação pode ter um efeito no roteamento, mas fundamentalmente
> o mais importante é mapear as características da via (velocidade
> máxima, superfície, etc.).
>
> Pra esse algoritmo só importa a velocidade atribuída a cada trecho das
> vias (e a atribuição pode não ter relação direta com aquilo que foi
> mapeado, só indireta). Se não for mapeada a velocidade máxima das
> vias, então a maioria dos roteadores tenta "adivinhar" a velocidade a
> partir da classificação. Como exemplo, eis aqui [1] como o OSRM faz
> essa adivinhação (lembrando que é um serviço mais voltado às
> características do trânsito na Europa).
>
> Então, sim, a classificação é importante para o roteamento caso não
> seja mapeada a velocidade máxima. Mas, fundamentalmente, o mais
> importante para o roteamento é a velocidade atribuída à via. Existem
> casos em que uma primária urbana tem velocidade reduzida num trecho
> curto e isso faz diferença pro roteamento decidir mandar o usuário por
> ali ou não. Só seria mapear para a aplicação se alguém mudasse a
> classificação naquele trecho por causa da velocidade, para forçar um
> roteador a evitar o trecho. (Um problema é que muita gente faz isso.)
>
> Especificamente para o Garmin/mkgmap, parece que ainda existe o
> conceito de "classe de velocidade", que não é nem a classificação da
> via (que se reflete no desenho), nem a velocidade máxima (que produz
> os alertas de velocidade). Essa é uma velocidade estimada de trânsito
> que no mkgmap [2] pode ter regras até bem complexas de derivação (nos
> exemplos que eu vi por aí o pessoal estava derivando esse campo a
> partir de uma combinação da classe da via e da velocidade máxima). Até
> daria pra mapear no OSM uma velocidade "esperada" pra via (que então
> se traduziria diretamente nessa velocidade do Garmin), mas isso é
> complicado de padronizar e por isso pode gerar divergências (e guerras
> de edição) e até pode acabar não sendo usado. [3] Algumas abordagens
> melhores são coletar a velocidade média [4] e monitorar o tráfego [5].
> Com essas duas abordagens, a classificação se torna irrelevante pro
> roteamento (por exemplo, no caso de uma primária estar sempre
> congestionada e uma secundária paralela estar sempre livre).
>
> [1]
> https://github.com/DennisOSRM/Project-OSRM/blob/master/profiles/car.lua
> [2] http://www.mkgmap.org.uk/doc/pdf/style-manual.pdf seção 4.6.5
> [3]
> http://wiki.openstreetmap.org/wiki/Talk:Proposed_features/traffic_speed#Practicality_of_Using_Info_in_Router
> [4] http://wiki.openstreetmap.org/wiki/Average_speed_per_way
> [5] https://lists.openstreetmap.org/pipermail/talk/2012-August/063985.html
>
> 2014-07-15 8:30 GMT-03:00 Paulo Carvalho <paulo.r.m.carvalho em gmail.com>:
> > Amigos,
> >
> >     Para compreender a razão de não quebrar a hierarquia de vias nos
> > pequenos trechos que rodovias passam por cidades, recomendo esta leitura:
> >
> > http://en.wikipedia.org/wiki/Contraction_hierarchies
> >
> >    Aos que já estão com o argumento "isso é mapear para aplicação" na
> ponta
> > da língua rogo um momento para parar e pensar:
> >
> > "For routing software to work well, the underlying map data must be of
> good
> > quality. Essentially this means that ways that should be connected are in
> > fact connected, one-way roads are tagged, turn restrictions are mapped,
> and
> > so on. You should be familiar with the Map Features used, in particular
> see
> > OSM tags for routing to understand the tags specific to routing." (grifo
> > meu)
> >
> > Palavras da própria comunidade OSM.
> >
> > Fonte:  http://wiki.openstreetmap.org/wiki/Routing
> >
> > [ ]s
> >
> > Paulo
> >
> > _______________________________________________
> > Talk-br mailing list
> > Talk-br em openstreetmap.org
> > https://lists.openstreetmap.org/listinfo/talk-br
> >
>
>
>
> --
> Fernando Trebien
> +55 (51) 9962-5409
>
> "Nullius in verba."
>
> _______________________________________________
> Talk-br mailing list
> Talk-br em openstreetmap.org
> https://lists.openstreetmap.org/listinfo/talk-br
>
-------------- Próxima Parte ----------
Um anexo em HTML foi limpo...
URL: <http://lists.openstreetmap.org/pipermail/talk-br/attachments/20140719/df111dd7/attachment-0001.html>


Mais detalhes sobre a lista de discussão Talk-br