Similitude entre deux ou plusieurs trajectoires

11

J'ai les données des camions ( http://www.chorochronos.org/ ).

Ces données sont les coordonnées GPS de plusieurs trajectoires de camions à Athènes.

Je dois calculer la similitude entre les trajectoires, afin de supprimer celles qui sont très similaires!

Problème:

Le rouge et le vert sont similaires, mais le bleu, le noir et (rouge ou vert) sont des trajectoires différentes. Je souhaite supprimer l'un des éléments similaires, rouge ou vert.

Les données sont en points (géométrie, lat et long, x et y) (coordonnées gps), l'image sont des exemples de trajectoires

postgis postgresql similarity user2883056
la source
1
Que se passe-t-il si le rouge et le vert sont similaires et que le vert et le noir sont similaires, mais que le rouge et le noir ne sont pas similaires? De plus, comment définissez-vous «similaire» - est-ce une proportion de la ligne se trouvant à une distance de l'autre ligne, ou une autre métrique?
phloème du
Je veux juste rester avec des trajectoires différentes des autres. Les trajectoires sont des coordonnées GPS, pas des lignes ...
user2883056
1
Vous avez des balises pour postgis et postgresql mais ne les mentionnez pas non plus dans votre corps de question. Bien que le marquage soit important, si vous utilisez ces produits, je recommande fortement de les enregistrer dans le corps de votre question car, après avoir jeté un coup d'œil au titre, ce sera la section de votre question qui retiendra toute l'attention.
PolyGeo
2
Je suis d'accord avec @phloem - la question clé est "comment définissez-vous similaire"? Tous les itinéraires partent de l'AB, ils sont donc «similaires» dans ce sens. Vous devez fournir plus d'informations sur la façon dont vous évaluerez un résultat positif
Stephen Lead

Réponses:

10

Une mesure vraiment facile, mais pas fantastique, est d'obtenir la distance de Hausdorff entre chaque combinaison, ce qui est fait avec la fonction ST_HausdorffDistance . En utilisant les chaînes de lignes approximatives de votre figure, elles sont toutes affichées en bleu et la distance de Hausdorff est indiquée pour l'une des paires de lignes en rouge:

Distance Hausdorff

Et la requête pour trier les 6 combinaisons par ordre décroissant:

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)

Donc, cela fonctionne bien pour cet exemple, mais ce n'est pas une technique excellente ou robuste pour regrouper des lignes, car la seule métrique est le point unique avec la plus grande distance, plutôt que de comparer les différences de lignes complètes. Il existe de bien meilleures méthodes, mais elles seront plus compliquées.

Mike T
la source
Bonne réponse. J'aurais probablement utilisé quelque chose comme ST_Interpolate point, puis calculé les distances moyennes pour chaque ensemble de points liés comme une approche naïve. À quoi pensiez-vous par de bien meilleures méthodes?
John Powell,
1
@ JohnBarça de meilleures méthodes seraient de comparer les statistiques spatiales de la couverture de chaque ligne. Une méthode consiste à pixelliser chaque ligne, à effectuer un flou gaussien avec le raster, puis à déterminer la corrélation des valeurs de raster coïncidentes à partir de chaque combinaison. Une méthode basée sur les outils ST_Segmentize et ST_Interpolate fonctionnerait également.
Mike T
4

Je n'ai pas accès à PostGres / PostGIS, mais voici comment j'y arriverais dans ArcGIS (ou autre).

  1. Calculez la longueur des lignes d'origine dans une colonne statique
  2. Mettez vos lignes en mémoire tampon en fonction de la façon dont vous définissez "similaire". Ne dissolvez pas les tampons. Les tampons résultants auront un FID égal à la ligne d'origine.
  3. Tampons d'intersection et lignes originales. La couche résultante identifiera les FID participant à cette intersection particulière (par exemple, "FID_lines" et "FID_buff").
  4. Dissoudre le calque n ° 3 par les deux colonnes FID d'origine et la colonne de longueur d'origine
  5. Ignorez les lignes résultantes qui ont la même valeur pour les deux colonnes FID d'origine en utilisant une requête de définition ou d'autres moyens (bien sûr, une ligne mise en mémoire tampon et coupée avec sa propre mémoire tampon se chevauchera complètement).
  6. Ajoutez une colonne numérique et remplissez-la avec la nouvelle longueur
  7. Divisez la nouvelle longueur par la longueur d'origine (dans une nouvelle colonne) pour obtenir un rapport de la ligne d'origine qui tombe dans le tampon de chaque ligne voisine.
  8. Inspectez les valeurs du rapport. Conservez ceux que vous avez définis comme "assez similaires". Par exemple, peut-être qu'une ligne se trouvant dans le tampon d'une autre ligne pour 75% de sa longueur est suffisamment similaire, peut-être que votre seuil est d'accord à 50%, etc.
phloème
la source