Localizando Caminhos de Mapa Semelhantes

Estou procurando um algoritmo que, quando determinada rota em um mapa com atributos como inclinação / distância / forma / etc, pode encontrar uma rota semelhante (em termos de atributos), mas que começa em um ponto diferente ou em uma região diferente do globo.

Obviamente, em quase todos os casos, será impossível encontrar um ajuste perfeito, mas estou procurando um tipo de sistema de "melhor correspondência" com um método de medir a similaridade também idealmente.

Eu tentei procurar, mas a maioria das minhas consultas apresenta problemas de correspondência de mapa ou semelhança de rota para pontos de GPS no mesmo caminho. Talvez eu não saiba a terminologia correta! Existe um nome para este problema? Qual algoritmo posso usar para resolver isso?

A correspondência de mapa é diferente do que você está procurando. Mapmatching é a maneira correta de associar uma observação de GPS sem irregularidades à rede de ruas linear. Sua pergunta também não tem nada a ver com pontos de GPS. Porque você deseja comparar o padrão das rotas estáticas (não temporais) e encontrar as semelhantes. O que você está procurando é característica linear (no sentido de GIS não ie aprendizagem de máquina) correspondente . A literatura relacionada à faixa GPS é a correspondência espaço-temporal de padrões que se enquadra na rubrica da "Mineração de padrões de trajetória (temporal espacial)".

Para mais informações, consulte o capítulo (Trajectory Pattern Mining) do livro " computando com trajetória espacial ". Você terá muitas idéias sobre como comparar e contrastar (por exemplo, azimute, comprimento dos segmentos, sinuosidade, linha reta etc.) várias rotas ou trajetórias.

Sua pergunta é baseada em dados vetoriais. No entanto, acho que você está melhor servido com a conversão da pergunta em uma análise raster. Ao fazer isso, você também generalizará sua pergunta.

Um algoritmo para resolver sua pergunta seria o seguinte:

1. Rasterize a rota original e faça com que cada célula carregue parâmetros de acordo com suas especificações (inclinação / distância / forma / etc). O fato de uma estrada estar presente também é um parâmetro. Isso se torna uma lista unidimensional com n objetos -> routelist (n)

2. Encontre uma área de teste onde saiba que há pelo menos uma réplica da sua rota original. Rasterize esta área com os mesmos parâmetros da sua rota original. Isso é raster a.

3. Comece com a célula 1,1 na varredura a e percorra toda a varredura de maneira ordenada.
4. Para cada célula, uma função é chamada. Esta função verifica se a célula corresponde à lista de roteamento (0); nesse caso, a mesma verificação é feita nas células circundantes. Com sucesso, a função continua a verificar a célula quanto à lista de roteamento (1) e assim por diante. Se for bem-sucedida até a lista de rotas (n), as coordenadas são armazenadas como uma rota alternativa na lista de rotas (n)
5. Repita até chegar ao último pixel da varredura.

Acima, você verá três opções para rotas de acordo com os parâmetros na lista de rotas.

Além disso:

• As amostras de amostras acima são medidas de acordo com apenas um parâmetro. No seu desafio do mundo real, um pixel será uma combinação de vários parâmetros.
• Se eu tivesse essa tarefa, tentaria escrever a função mencionada acima de forma recursiva. Isso seria mais eficiente e resolveria o problema de "trilhas divergentes" - onde você tem várias trilhas alternativas com o mesmo ponto de partida.
• As curvas do seu percurso não são consideradas um problema. Isso significa que as respostas são uma lista de pixels conectados na mesma ordem que a sua rota original. Reviravoltas não são um problema. Talvez você precise escrever o algoritmo para que as rotas com interseção automática não façam parte da solução.
• Projete o algoritmo para que você possa definir diferentes níveis de tolerância para os critérios em jogo. Isso lhe dará mais flexibilidade.
• Em um ambiente operacional, todo o processo pode ser mais eficiente, rastreando a área quanto à ocorrência de pixels, de acordo com suas especificações. Se eles não estiverem lá, a área de pesquisa é negativa; portanto, não há razão para usar o tempo para analisar a área.