Ähnlichkeit zwischen zwei oder mehr Trajektorien

11

Ich habe die Daten von Lastwagen ( http://www.chorochronos.org/ ).

Diese Daten sind GPS-Koordinaten mehrerer Flugbahnen von Lastwagen in Athen.

Ich muss die Ähnlichkeit zwischen den Trajetorien berechnen, um diejenigen zu löschen, die sehr ähnlich sind!

Problem:

Rot und Grün sind ähnlich, aber Blau, Schwarz und (Rot oder Grün) sind unterschiedliche Flugbahnen. Ich möchte eines der Ähnlichkeiten löschen, rot oder grün.

Die Daten sind in Punkten (Geometrie, Lat und Long, X und Y) (Koordinaten GPS) angegeben. Das Bild ist ein Beispiel für Trajektorien

user2883056
quelle
1
Was passiert, wenn Rot und Grün ähnlich sind und Grün und Schwarz ähnlich sind, Rot und Schwarz jedoch nicht ähnlich sind? Wie definieren Sie "ähnlich" - ist es ein Anteil der Linie, der in einen Abstand von der anderen Linie fällt, oder eine andere Metrik?
Phloem
Ich möchte nur bei Flugbahnen bleiben, die sich von den anderen unterscheiden. Die Trajetories sind GPS-Koordinaten, keine Linien ...
user2883056
1
Sie haben Tags für postgis und postgresql , erwähnen diese aber auch nicht in Ihrem Fragenkörper . Wenn Sie diese Produkte verwenden, ist das Markieren zwar wichtig, ich empfehle jedoch dringend, sie im Hauptteil Ihrer Frage festzuhalten, da dies nach einem Blick auf den Titel der Abschnitt Ihrer Frage ist, der die ganze Aufmerksamkeit auf sich zieht.
PolyGeo
2
Ich stimme @phloem zu - die Schlüsselfrage lautet "Wie definieren Sie Ähnliches?" Alle Routen verlaufen von AB, daher sind sie in diesem Sinne „ähnlich“. Sie müssen weitere Informationen darüber bereitstellen, wie Sie ein erfolgreiches Ergebnis bewerten
Stephen Lead

Antworten:

10

Eine wirklich einfache, aber nicht fantastische Maßnahme besteht darin, den Hausdorff-Abstand zwischen jeder Kombination zu ermitteln, was mit der Funktion ST_HausdorffDistance erfolgt . Unter Verwendung der ungefähren LineStrings aus Ihrer Figur werden diese alle in Blau angezeigt, und der Hausdorff-Abstand wird für eines der Linienpaare in Rot angezeigt:

Hausdorff Entfernung

Und die Abfrage zum Sortieren der 6 Kombinationen in absteigender Reihenfolge:

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)

In diesem Beispiel funktioniert es also gut, aber es ist keine großartige oder robuste Technik zum Clustering von Linien, da die einzige Metrik der einzelne Punkt mit der größten Entfernung ist, anstatt die Unterschiede vollständiger Linien zu vergleichen. Es gibt viel bessere Methoden, aber sie werden komplizierter sein.

Mike T.
quelle
Gute Antwort. Ich hätte wahrscheinlich so etwas wie ST_Interpolate point verwendet und dann die durchschnittlichen Abstände für jeden Satz verwandter Punkte als naiven Ansatz berechnet. Was hatten Sie mit viel besseren Methoden vor?
John Powell
1
@ JohnBarça bessere Methoden wären, räumliche Statistiken der Abdeckung jeder Linie zu vergleichen. Eine Methode würde jede Zeile rasteren, eine Gaußsche Unschärfe mit dem Raster durchführen und dann die Korrelation von übereinstimmenden Rasterwerten aus jeder Kombination bestimmen. Eine auf den Werkzeugen ST_Segmentize und ST_Interpolate basierende Methode würde ebenfalls funktionieren.
Mike T
4

Ich habe keinen Zugriff auf PostGres / PostGIS, aber hier ist, wie ich in ArcGIS (oder anderen) vorgehen würde.

  1. Berechnen Sie die Länge der ursprünglichen Zeilen in einer statischen Spalte
  2. Puffern Sie Ihre Zeilen entsprechend Ihrer Definition von "ähnlich". Puffer nicht auflösen. Die resultierenden Puffer haben eine FID, die der ursprünglichen Zeile entspricht.
  3. Puffer und ursprüngliche Linien schneiden. Die resultierende Ebene identifiziert FIDs, die an dieser bestimmten Kreuzung teilnehmen (z. B. "FID_lines" und "FID_buff").
  4. Lösen Sie die Schicht von # 3 durch die beiden ursprünglichen FID-Spalten und die ursprüngliche Längenspalte auf
  5. Ignorieren Sie resultierende Zeilen, die denselben Wert für die beiden ursprünglichen FID-Spalten haben, mithilfe einer Definitionsabfrage oder auf andere Weise (natürlich überlappt sich eine gepufferte und mit ihrem eigenen Puffer geschnittene Zeile vollständig).
  6. Fügen Sie eine numerische Spalte hinzu und füllen Sie sie mit der neuen Länge
  7. Teilen Sie die neue Länge durch die ursprüngliche Länge (in eine neue Spalte), um ein Verhältnis der ursprünglichen Zeile zu erhalten, die in den Puffer jeder nahe gelegenen Zeile fällt.
  8. Überprüfen Sie die Werte für das Verhältnis. Behalten Sie die, die Sie als "ähnlich genug" definiert haben. Zum Beispiel ist eine Linie, die für 75% ihrer Länge in den Puffer einer anderen Linie fällt, ähnlich genug, vielleicht liegt Ihr Cutoff bei 50% Übereinstimmung usw.
Phloem
quelle