Temos um exemplo de um mapa Garmin que não está calculando uma rota entre o extremo sul do Brasil e um ponto no Ceará. A rota é calculada normalmente no Mapsource (computador) mas não no GPS (dipositivo móvel). O problema é justamente localizar onde está a interrupção ou alternância de classificação de vias nos mais de 3000km da rota.
Em 20 de julho de 2014 12:05, Fernando Trebien <fernando.treb...@gmail.com> escreveu: > Contraction hierarquies permite usar Dijkstra bidirecional + alguma > heurística otimista em ambientes com restrições de memória e > capacidade computacional sem remover qualquer via do cálculo. Isso tá > lá nos papers referenciados no final daquele artigo da Wikipédia que > você apontou. Era a isso que eu me referia ao julgar a inteligência do > algoritmo, e por ser um fato (o algoritmo foi publicado e nada > "impede" que seja implementado), não tem como ser arrogante. É uma > escolha simples (bem, não tão simples) que o desenvolvedor da > aplicação tem que fazer. E é uma escolha que é independente do mapa > (que, novamente, serve a vários propósitos, não só ao roteamento, não > só ao roteamento em ambientes com capacidades limitadas). > > "Mas interromper uma motorway com um trecho de residential vai quebrar > o roteamento em muitas aplicações." Pode dar um exemplo de aplicação e > local? > > Apesar de solicitar esse exemplo, não conheço nenhum caso em que uma > motorway/trunk precisaria ter um trecho classificado como > "residencial". Na pior das hipóteses, teria um trecho classificado > como terciária por estar não-pavimentada - mas acho que nem no Brasil > essa situação ocorre. Recentemente eu achei um exemplo em que uma > trunk se intercala com uma primária [1], mas isso também não deve > afetar esses sistemas que descartam vias a que você se refere. > > E claro, no caso particular, raro, e bizarro de uma classificação fiel > produzir uma situação assim, podemos pensar em discutir com a > comunidade sobre o que fazer. A idéia de não alternar demais a > classificação da via poderia ser aplicada ser for só um trecho curto > com características diferentes, e o motivo não seria só o roteamento. > > [1] http://www.openstreetmap.org/#map=12/-29.5385/-51.8998 > > 2014-07-20 10:47 GMT-03:00 Paulo Carvalho <paulo.r.m.carva...@gmail.com>: > > > > > > > > Em 19 de julho de 2014 22:29, Fernando Trebien < > fernando.treb...@gmail.com> > > escreveu: > > > >> Sabendo que há trabalhos cientificos publicados descrevendo bons > >> algoritmos para esses ambientes e que não descartam quaisquer vias > >> (mesmo as de classe bem inferior), acho que não devemos fazer > >> adaptações no mapa em favor de algoritmos menos inteligentes. (Isso > >> seria mapear para a aplicação.) > > > > > > 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. > > > > 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. > > > >> > >> > >> Mas, ao mesmo tempo, acho que são muito raros os casos em que > >> adaptações seriam necessárias para evitar problemas com esses > >> algoritmos que descartam vias. A menos que eles estejam descartando > >> até as vias primárias (arteriais urbanas), daí não tem como resolver > >> mesmo. > > > > > > 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): > > a) Encontrar um lugar (geocoding); > > b) Navegar até um lugar (roteamento); > > c) Quase sempre em trânsito, com dispositivos móveis. > > > > 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. > > > > 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. > > > > []s > > > > Paulo > > > >> > >> > >> 2014-07-19 17:56 GMT-03:00 Paulo Carvalho <paulo.r.m.carva...@gmail.com > >: > >> > E qual sua opinião sobre o descarte de vias de baixa prioridade nos > >> > roteamentos de longa distância em ambientes com baixa memória e > >> > processamento mais lento? > >> > > >> > > >> > Em 19 de julho de 2014 12:58, Fernando Trebien > >> > <fernando.treb...@gmail.com> > >> > escreveu: > >> > > >> >> Li sim, há bastante tempo. Mas acho que estás confundindo as > >> >> hierarquias do OSM com a hierarquia de atalhos emergente que o > >> >> algoritmo de "contraction hierarchies" produz (que inclusive pode ter > >> >> muito mais níveis do que os poucos que existem no OSM). Os atalhos > >> >> servem apenas para acelerar outro algoritmo de roteamento qualquer > >> >> (geralmente se adota uma variação do Dijkstra, e nesse caso as > >> >> heurísticas acabam preferindo usar os atalhos). E a hierarquia do OSM > >> >> não se converte em atalhos automaticamente. A sequẽncia das coisas é > >> >> assim: > >> >> - cada arco original representa a ligação de duas interseções no mapa > >> >> - o peso dos arcos originais é atribuído por velocidade X distância, > >> >> onde velocidade é uma estimativa feita de forma diferente por cada > >> >> aplicação (algumas usam a classificação da via, outras não) > >> >> - (contraction hierarchies) os arcos de atalho são gerados eliminando > >> >> sequências de arcos cujo peso total é muito alto > >> >> - (contraction hierarchies) um grafo é formado combinando os arcos > >> >> originais com os atalhos > >> >> - um algoritmo de busca em grafos é aplicado sobre o grafo resultante > >> >> (< ou seja, esse algoritmo vai usar tanto atalhos quanto arcos > >> >> originais, possivelmente se intercalando entre os dois) > >> >> > >> >> Por exemplo, se você tiver dois caminhos de A a B com quase a mesma > >> >> distância total, um deles é uma primária com velocidade de 10km/h, e > >> >> outro é uma terciária intercalada com trechos de living_street que, > na > >> >> média, fica em torno de 80km/h, vai ser a primária que vai ser > >> >> removida na geração dos atalhos e o segundo caminho (mais rápido, > >> >> embora envolva vias de classificação inferior) que vai virar um > >> >> atalho. O fato de ser primária, secundária, living street, não faz > >> >> diferença alguma a princípio - a menos que exista um programa antes > >> >> (como o mkgmap) que associa a classificação ao peso do arco (mais > >> >> especificamente à velocidade, já que a distância é exata sempre). O > >> >> OSRM, por exemplo, não associa quando a velocidade máxima é definida > >> >> (ou seja, o segundo caso pode acontecer). > >> >> > >> >> Enfim, isso é um detalhe, a classificação tem que estar bem feita por > >> >> diversos motivos, mas (se formos pensar genericamente, para vários > >> >> sistemas) não se pode ignorar o mapeamento da velocidade máxima das > >> >> vias. > >> >> > >> >> 2014-07-19 12:10 GMT-03:00 Paulo Carvalho > >> >> <paulo.r.m.carva...@gmail.com>: > >> >> >> 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.treb...@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.carva...@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@openstreetmap.org > >> >> >> > https://lists.openstreetmap.org/listinfo/talk-br > >> >> >> > > >> >> >> > >> >> >> > >> >> >> > >> >> >> -- > >> >> >> Fernando Trebien > >> >> >> +55 (51) 9962-5409 > >> >> >> > >> >> >> "Nullius in verba." > >> >> >> > >> >> >> _______________________________________________ > >> >> >> Talk-br mailing list > >> >> >> Talk-br@openstreetmap.org > >> >> >> https://lists.openstreetmap.org/listinfo/talk-br > >> >> > > >> >> > > >> >> > > >> >> > _______________________________________________ > >> >> > Talk-br mailing list > >> >> > Talk-br@openstreetmap.org > >> >> > https://lists.openstreetmap.org/listinfo/talk-br > >> >> > > >> >> > >> >> > >> >> > >> >> -- > >> >> Fernando Trebien > >> >> +55 (51) 9962-5409 > >> >> > >> >> "Nullius in verba." > >> >> > >> >> _______________________________________________ > >> >> Talk-br mailing list > >> >> Talk-br@openstreetmap.org > >> >> https://lists.openstreetmap.org/listinfo/talk-br > >> > > >> > > >> > > >> > _______________________________________________ > >> > Talk-br mailing list > >> > Talk-br@openstreetmap.org > >> > https://lists.openstreetmap.org/listinfo/talk-br > >> > > >> > >> > >> > >> -- > >> Fernando Trebien > >> +55 (51) 9962-5409 > >> > >> "Nullius in verba." > >> > >> _______________________________________________ > >> Talk-br mailing list > >> Talk-br@openstreetmap.org > >> https://lists.openstreetmap.org/listinfo/talk-br > > > > > > > > _______________________________________________ > > Talk-br mailing list > > Talk-br@openstreetmap.org > > https://lists.openstreetmap.org/listinfo/talk-br > > > > > > -- > Fernando Trebien > +55 (51) 9962-5409 > > "Nullius in verba." > > _______________________________________________ > Talk-br mailing list > Talk-br@openstreetmap.org > https://lists.openstreetmap.org/listinfo/talk-br >
_______________________________________________ Talk-br mailing list Talk-br@openstreetmap.org https://lists.openstreetmap.org/listinfo/talk-br
