Caminho mais curto usando pontos OSM interpolados

8

Eu tenho um conjunto de pontos de GPS que encaixei na rede OSM. Na captura de tela abaixo, os pontos de GPS são vermelhos, os pontos de snap são verdes. insira a descrição da imagem aqui

Quero calcular o caminho mais curto que inclui todos esses pontos de passagem verdes. Minha solução é calcular o caminho mais curto entre cada par de pontos e finalmente concatenar os resultados.

Meu problema é que dijkstra_sp não aceita pontos arbitrários na rede OSM. Meus pontos quebrados não estão necessariamente na tabela de formas porque foram calculados usando a seguinte lógica.

  1. Encontre o caminho mais próximo de um determinado ponto de GPS.
  2. Usando a interpolação, encontre o ponto mais próximo desse caminho até o ponto GPS.

Os pontos capturados não estão na tabela de formas porque foram derivados por interpolação.

Portanto, minha pergunta é: como calcular o caminho mais curto entre dois pontos na rede OSM que não estão necessariamente na tabela de formas?

interpolation pgrouting Fezter
fonte
Parece-me que você está tentando resolver o problema do vendedor ambulante . Nesse caso, o caminho mais eficiente a seguir seria usar um algoritmo TSP ...
ntg

Respostas:

3

Resolvemos o mesmo problema com arestas e vértices temporários. Ajustamos nossas cordas GPS a uma borda e da v1 à v2 e obtivemos um deslocamento entre 0 e 1:

segOffset := line_locate_point(geom(e), Point(coords);

Com isso, criamos um novo Point () e com isso um novo vértice v_tmp:

line_interpolate_point(geom(e), segOffset);

Em seguida, dividimos nossa borda e1 em duas novas bordas e_tmp1 da v1 para v_tmp e e_tmp2 de v_tmp para v2. (Você pode precisar dividi-lo em quatro extremidades temporárias ...)

Com nosso objetivo, fizemos o mesmo. Do que começamos a fazer o agrupamento com nossos novos vértices v_tmp_source, v_tmp_dest e é isso.

Axel Zingsem
fonte
2

Combinei com os nós mais próximos, usei o pgrouting para encontrar a rota entre esses nós. Eu estava atrás da distância total, então adicionei as duas distâncias dos nós dos pontos.

Eu tinha um limite superior de quão perto um nó precisava estar, para ser aceitável.

A matemática seria mais complicada / mais lenta, mas você poderia fazer o mesmo com arestas se estivesse usando um algoritmo de pgrouting que funcionasse em termos de arestas em vez de nós.

winwaed
fonte
(Desculpe, de alguma forma, não posso comentar sobre "winwaed", então tenho que fazer isso com outra resposta)> A matemática seria mais complicada / mais lenta, mas você poderia fazer o mesmo com arestas se estivesse usando um algoritmo de pgrouting que trabalhou em termos de arestas em vez de nós. O algoritmo Shooting Star usa arestas em vez de nós.
dkastl
Nem o nó mais próximo nem os procedimentos baseados em borda funcionarão, veja o exemplo abaixo. dl.dropbox.com/u/11502389/Screenshot2.png As linhas azuis são as maneiras que as cada pontos verdes estão no.
1

seu problema me lembra de um caso semelhante, que tivemos que resolver alguns anos atrás: alguém está desenhando um caminho (cadeia de linhas) no topo de um mapa raster e tivemos que correspondê-lo à rede de estradas subjacente.

Parece ser semelhante aos seus pontos GPS vermelhos. E mesmo que você tenha assumido que podemos procurar o caminho mais curto entre esses pontos.

Porque isso faz muito tempo, não me lembro mais de detalhes. Mas publicamos as funções em "matching.sql", que já faz parte do pgRouting. Porém, não há documentação. Desculpe por isso. Mas talvez a leitura da fonte SQL dê uma idéia de como ela funciona: https://github.com/pgRouting/pgrouting/blob/master/core/sql/matching.sql

dkastl
fonte
O uso de nós mais próximos não funciona, considere o exemplo abaixo.
Essa função de correspondência mencionada faz uma combinação de correspondência com nós e segmentos de estrada. Depende da proximidade do seu ponto GPS com um nó. Se você estiver muito perto de uma travessia, seu ponto de GPS pode estar mais próximo de uma borda, na qual não deve ser atribuído.
dkastl