Semelhança entre duas ou mais trajetórias

11

Eu tenho os dados de caminhões ( http://www.chorochronos.org/ ).

Esses dados são coordenadas GPS de várias trajetórias de caminhões em Atenas.

Eu tenho que calcular a semelhança entre as trajetórias, para excluir aquelas que são muito semelhantes!

Problema:

Vermelho e verde são semelhantes, mas azul, preto e (vermelho ou verde) são trajetórias diferentes. Quero excluir um dos semelhantes, vermelho ou verde.

Os dados estão em pontos (geometria, lat e long, x e y) (coordenadas gps), a imagem é exemplos de trajetórias

postgis postgresql similarity user2883056
fonte
1
O que acontece se vermelho e verde são semelhantes e verde e preto são semelhantes, mas vermelho e preto não são semelhantes? Além disso, como você define "semelhante" - é uma proporção da linha que fica a uma distância da outra linha ou de alguma outra métrica?
Phloem
Eu só quero ficar com trajetórias diferentes das outras. Os trajetories são coordenadas de GPS, não linhas ...
user2883056
1
Você tem tags para postgis e postgresql, mas não menciona isso no corpo da sua pergunta. Embora a marcação seja importante, se você estiver usando esses produtos, recomendo gravá-los no corpo da sua pergunta, porque, depois de olhar o título, essa será a seção da sua pergunta que receberá toda a atenção.
PolyGeo
2
Concordo com @phloem - a questão principal é "como você define similar"? Todas as rotas partem de AB, portanto são "semelhantes" nesse sentido. Você precisa fornecer mais informações sobre como avaliar um resultado bem-sucedido
Stephen Lead

Respostas:

10

Uma medida realmente fácil, mas não fantástica, é obter a distância de Hausdorff entre cada combinação, o que é feito com a função ST_HausdorffDistance . Usando LineStrings aproximadas da sua figura, todas são mostradas em azul e a distância de Hausdorff é mostrada para um dos pares de linhas em vermelho:

Distância Hausdorff

E a consulta para classificar as 6 combinações em ordem decrescente:

WITH data AS (
  SELECT 'blue' AS name, 'LINESTRING (60 200, 110 290, 200 320, 330 320, 430 240, 450 200)'::geometry AS geom
  UNION SELECT 'black', 'LINESTRING (60 200, 120 270, 235 297, 295 207, 450 200)'::geometry
  UNION SELECT 'green', 'LINESTRING (60 200, 280 190, 450 200)'::geometry
  UNION SELECT 'red', 'LINESTRING (60 200, 150 210, 257 195, 360 210, 430 190, 450 200)'::geometry)
SELECT a.name || ' <-> ' || b.name AS compare, ST_HausdorffDistance(a.geom, b.geom)
FROM data a, data b WHERE a.name < b.name
ORDER BY ST_HausdorffDistance(a.geom, b.geom) DESC;

     compare     | st_hausdorffdistance
-----------------+----------------------
 blue <-> green  |                  130
 blue <-> red    |                  125
 black <-> blue  |     110.102502131467
 black <-> green |     104.846289061163
 black <-> red   |     97.9580173908678
 green <-> red   |     15.2677257073823
(6 rows)

Portanto, funciona bem neste exemplo, mas não é uma técnica excelente ou robusta para agrupar linhas, pois a única métrica é o ponto único com a maior distância, em vez de comparar as diferenças de linhas completas. Existem métodos muito melhores, mas serão mais complicados.

Mike T
fonte
Boa resposta. Provavelmente eu teria usado algo como o ponto ST_Interpolate e depois calculado as distâncias médias para cada conjunto de pontos relacionados como uma abordagem ingênua. O que você tinha em mente por métodos muito melhores?
John Powell
1
@ JohnBarça métodos melhores seriam comparar estatísticas espaciais da cobertura de cada linha. Um método rasterizaria cada linha, faria um desfoque gaussiano com a varredura e determinaria a correlação dos valores de varredura coincidentes de cada combinação. Um método baseado nas ferramentas ST_Segmentize e ST_Interpolate também funcionaria.
Mike T
4

Eu não tenho acesso ao PostGres / PostGIS, mas aqui está como eu faria isso no ArcGIS (ou outro).

  1. Calcular o comprimento das linhas originais em uma coluna estática
  2. Coloque suas linhas em buffer de acordo com a definição de "similar". Não dissolva os tampões. Os buffers resultantes terão o FID igual à linha original.
  3. Interseção de buffers e linhas originais. A camada resultante identificará os FIDs participantes dessa interseção específica (por exemplo, "FID_lines" e "FID_buff").
  4. Dissolver a camada do nº 3 pelas duas colunas originais do FID e pela coluna de comprimento original
  5. Ignore as linhas resultantes que têm o mesmo valor para as duas colunas originais do FID usando uma consulta de definição ou outros meios (é claro que uma linha armazenada em buffer e cruzada com seu próprio buffer se sobreporá totalmente).
  6. Adicione uma coluna numérica e preencha-a com o novo comprimento
  7. Divida o novo comprimento pelo comprimento original (em uma nova coluna) para obter uma proporção da linha original que cai no buffer de cada linha próxima.
  8. Inspecione os valores para a proporção. Mantenha aqueles que você definiu como "suficientemente parecidos". Por exemplo, talvez uma linha que caia no buffer de outra linha por 75% de seu comprimento seja semelhante o suficiente, talvez seu ponto de corte seja de 50% de concordância etc.
floema
fonte