Mapa de roteamento, a la Google Maps?

votos
19

Sempre fui intrigado com Mapa de roteamento, mas eu nunca encontrei qualquer bom introdutória (ou mesmo avançado!) Nível de tutoriais sobre ele. Alguém tem qualquer ponteiros, sugestões, etc?

Update: eu estou olhando principalmente para os ponteiros de como um sistema de mapa é implementado (estruturas de dados, algoritmos, etc).

Publicado 05/08/2008 em 21:24
fonte usuário
Em outras línguas...                            


9 respostas

votos
14

Dê uma olhada no projeto de mapa de rua aberto para ver como esse tipo de coisa está sendo abordado em um projeto de software verdadeiramente livre usando apenas utilizador fornecido e licenciado dados e ter um wiki contendo material que você pode achar interessante .

Alguns anos atrás, os caras envolvidos, onde muito fácil ir e respondeu muitas perguntas que eu tinha então eu não vejo nenhuma razão por que eles ainda não são um grupo agradável.

Respondeu 05/08/2008 em 21:27
fonte usuário

votos
4

A * é na verdade muito mais perto de algoritmos de mapeamento de produção. Ele requer um pouco menos de exploração em relação ao algoritmo original de Dijikstra.

Respondeu 25/09/2008 em 00:19
fonte usuário

votos
4

Barry Brumitt, um dos engenheiros de recurso rota descoberta mapas do Google, escreveu um post sobre o tema que podem ser de interesse:

A estrada para melhor encontrar caminho 11/06/2007 03:47:00

Respondeu 17/09/2008 em 09:44
fonte usuário

votos
4

Por Mapa Routing, você quer dizer encontrar o caminho mais curto ao longo de uma rede de ruas?

Dijkstra algoritmo de caminho mais curto é o mais conhecido. Wikipedia não tem um mau introdução: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Há um applet Java aqui onde você pode vê-lo em ação: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html e Google você levá-lo para o código-fonte em praticamente qualquer língua.

Qualquer implementação real para gerar rotas de condução vai incluir um pouco de dados sobre a rede de ruas que descreve o custo associado com links que atravessam e hierarquia da rede gânglios-road, velocidade média, prioridade intersecção, ligando sinal de trânsito, voltas proibidas etc.

Respondeu 15/08/2008 em 05:31
fonte usuário

votos
2

De um ponto de vista conceitual, imagine deixar cair uma pedra em um lago e observando as ondulações. As rotas representaria a lagoa ea pedra a sua posição inicial.

É claro que o algoritmo teria que procurar alguma proporção de n ^ 2 caminhos como os n distância aumenta. Você iria levá-lo posição inicial e verificar todos os caminhos disponíveis a partir desse ponto. Em seguida, de forma recursiva chamar os pontos no final desses caminhos e assim por diante.

Você pode aumentar o desempenho, por não double-backing em um caminho, por não re-verificar as rotas em um ponto, se já tiver sido coberto e dando-se em caminhos que estão tomando muito tempo.

Uma forma alternativa é a de utilizar a abordagem de feromonas de formigas, formigas onde rastrear aleatoriamente a partir de um ponto de partida e deixar um rastro, que acumula os mais formigas atravessar um dado caminho. Se você enviar formigas (suficientes), tanto do ponto de partida e os pontos finais depois, eventualmente, o caminho com o cheiro mais forte será a mais curta. Isso ocorre porque o caminho mais curto terá sido visitado mais vezes em um determinado período de tempo, uma vez que as formigas andar em um ritmo uniforme.

EDIT @ Spikie

Como mais uma explicação de como implementar o algoritmo lagoa - estruturas de dados potenciais necessários são destacadas:

Você vai precisar de guardar o mapa como uma rede. Isto é simplesmente um conjunto de nodese edgesentre eles. Um conjunto de nodesconstituir uma route. Uma aresta junta-se dois nós (possivelmente ambos o mesmo nó), e tem uma associada costtal como distanceou timepara atravessar a borda. Uma aresta pode quer ser bidireccional ou unidireccional. Provavelmente mais simples apenas para ter os uni-direcionais e dobrar para viagens nos dois sentidos entre os nós (ou seja, uma margem de A para B e um diferente para B para A).

A título de exemplo, imagine três estações ferroviárias dispostos em um triângulo equilátero que aponta para cima. Há também mais três estações cada meio caminho entre eles. Arestas juntar todas as estações adjacentes em conjunto, o diagrama final terá um triângulo invertido sentado no interior do triângulo maior.

nodos do rótulo a partir da esquerda inferior, indo da esquerda para a direita e para cima, como A, B, C, D, E, F (F no topo).

Consideram-se os bordos pode ser atravessado em ambos os sentidos. Cada ponta tem um custo de 1 km.

Ok, então queremos rota a partir do canto inferior esquerdo A ao topo estação F. Há muitas rotas possíveis, incluindo aqueles que dobrar para trás em si, por exemplo ABCEBDEF.

Nós temos uma palavra a dizer rotina, NextNodeque aceita um nodee um coste chama-se para cada nó pode viajar.

Claramente se deixarmos esta corrida rotina que acabará por descobrir todas as rotas, incluindo aqueles que são potencialmente infinito de comprimento (por exemplo ABABABAB etc). Nós impedir que isso aconteça, verificando contra o cost. Sempre que visitar um nó que não foi visto antes, nós colocamos tanto o custo eo nó viemos contra esse nó. Se um nó foi visto antes que o check contra o custo existente e se estamos mais barato, então vamos atualizar o nó e continuar (recursão). Se formos mais caro, então vamos pular o nó. Se todos os nós são ignorados, então, sair da rotina.

Se nós batemos nosso nó de destino, em seguida, sair da rotina também.

Desta forma, todas as rotas viáveis ​​são verificados, mas crucialmente apenas aqueles com o menor custo. Até o final do processo de cada nó terá o menor custo para chegar a esse nó, incluindo o nosso nó de destino.

Para obter o caminho que trabalhar para trás do nosso nó de destino. Desde que nós armazenados no nó viemos junto com o custo, nós apenas hop para trás construção da rota. Para nosso exemplo, iria acabar com algo como:

Nó - (Total) Custo 0 - De nó Nenhum
nó B - Custo 1 - A partir de um nó
do nó C - Custo 2 - A partir do nó B
nó D - Custo 1 - A partir de um nó
do nó E - Custo 2 - A partir do nó D / Custo 2 - a partir do nó B (isto é uma excepção, como não é igual custo)
Nó F - custo 2 - a partir do nó D

Assim, o caminho mais curto é ADF.

Respondeu 26/09/2008 em 15:05
fonte usuário

votos
2

Eu ainda tenho que encontrar um bom tutorial sobre roteamento, mas há um monte de código para ler:

Existem aplicações de roteamento GPL que utilizam dados OpenStreetMap, por exemplo Gosmore que funciona no Windows (+ mobile) e Linux. Há uma série de interessantes [aplicações usando os mesmos dados, mas Gosmore tem algum legal usa exemplo de interface com os sites .

O maior problema com roteamento são dados ruins, e você nunca obter dados bons o suficiente. Então, se você quiser experimentá-lo manter o seu teste muito local para que possa controlar melhor os dados.

Respondeu 17/09/2008 em 09:34
fonte usuário

votos
2

Em vez de aprender APIs para cada prestador de serviço de mapas (como Gmaps, Ymaps api) É bom para aprender Mapstraction

"Mapstraction é uma biblioteca que oferece uma API comum para várias APIs de mapeamento javascript"

Sugiro que você vá para o URL e aprender uma API geral. Há uma boa quantidade de How-Tos também.

Respondeu 06/08/2008 em 14:35
fonte usuário

votos
1

Da minha experiência de trabalhar neste campo, A * faz o trabalho muito bem. É (como mencionado acima) mais rápido do que o algoritmo de Dijkstra, mas ainda é bastante simples para um programador normalmente competente para implementar e entender.

Construindo a rede de rotas é a parte mais difícil, mas que pode ser dividido em uma série de passos simples: obter todas as estradas; classificar os pontos em ordem; formar grupos de pontos idênticos em estradas diferentes em intersecções (nós); adicionar arcos em ambos os sentidos, onde nós conectam (ou somente em uma direção para uma estrada de sentido único).

O A * algoritmo em si é bem documentado na Wikipedia . O lugar chave para otimizar é a seleção dos melhores nó da lista aberta, para o qual você precisa de uma fila de prioridade de alto desempenho. Se você estiver usando C ++ você pode usar o adaptador STL priority_queue.

Personalizando o algoritmo de rota ao longo de diferentes partes da rede (por exemplo, pedestre, carro, transportes públicos, etc.) de velocidade favor, distância ou outros critérios é bastante fácil. Você faz isso por escrito filtros para controlar quais segmentos de rota estão disponíveis, ao construir a rede, e que o peso é atribuído a cada um.

Respondeu 15/07/2012 em 22:13
fonte usuário

votos
1

Outro pensamento ocorre-me sobre o custo de cada travessia, mas aumentaria o tempo e poder de processamento necessário para calcular.

Exemplo: Existem 3 maneiras que eu posso tomar (onde moro) para ir do ponto A ao B, de acordo com o GoogleMaps. Unidades Garmin oferecer cada uma destas 3 caminhos no Quickestcálculo da rota. Depois de atravessar cada uma dessas rotas muitas vezes e média (obviamente haverá erros, dependendo da hora do dia, quantidade de cafeína etc.), eu sinto os algoritmos poderia levar em conta o número de curvas na estrada para o alto nível de precisão , por exemplo estrada reta de uma milha será mais rápido do que uma estrada uma milha com curvas acentuadas nele . Não uma sugestão prática, mas certamente que eu uso para melhorar o conjunto de resultados do meu trajeto diário.

Respondeu 18/09/2011 em 22:34
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more