Podobieństwo dwóch lub więcej trajektorii

11

Mam dane ciężarówek ( http://www.chorochronos.org/ ).

Te dane są współrzędnymi GPS wielu trajektorii ciężarówek w Atenach.

Muszę obliczyć podobieństwo między trajetoriami, aby usunąć te, które są bardzo podobne!

Problem:

Czerwony i zielony są podobne, ale niebieski, czarny i (czerwony lub zielony) to różne trajektorie. Chcę usunąć jeden z podobnych, czerwony lub zielony.

Dane są w punktach (geometria, szerokość i długość, x i y) (współrzędne gps), obraz to przykłady trajektorii

postgis postgresql similarity użytkownik 2883056
źródło
1
Co się stanie, jeśli czerwony i zielony są podobne, a zielony i czarny są podobne, ale czerwony i czarny nie są podobne? W jaki sposób definiujesz „podobny” - czy jest to część linii mieszcząca się w odległości od drugiej linii, czy jakaś inna metryka?
łyk
Chcę pozostać z trajektoriami, które różnią się od innych. Trajetories to współrzędne GPS, a nie linie ...
user2883056
1
Masz tagi dla postgis i postgresql, ale nie wymieniaj żadnego z nich w treści pytania. Podczas gdy tagowanie jest ważne, jeśli używasz tych produktów, zdecydowanie zalecam zapisanie ich w treści pytania, ponieważ po spojrzeniu na tytuł będzie to sekcja pytania, która przyciągnie całą uwagę.
PolyGeo
2
Zgadzam się z @phloem - kluczowe pytanie brzmi: „jak definiujesz podobne”? Wszystkie trasy biegną od AB, więc są w tym sensie „podobne”. Musisz podać więcej informacji o tym, jak ocenisz udany wynik
Stephen Lead

Odpowiedzi:

10

Naprawdę łatwym, ale nie fantastycznym miernikiem jest uzyskanie odległości Hausdorffa między każdą kombinacją, co odbywa się za pomocą funkcji ST_HausdorffDistance . Używając przybliżonych ciągów liniowych z twojej figury, wszystkie są pokazane na niebiesko, a odległość Hausdorffa pokazana jest dla jednej z par linii na czerwono:

Odległość Hausdorffa

I zapytanie o sortowanie 6 kombinacji w kolejności malejącej:

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)

Tak więc działa dobrze w tym przykładzie, ale nie jest to świetna ani solidna technika dla grupowania linii, ponieważ jedyną miarą jest pojedynczy punkt o największej odległości, zamiast porównywania różnic pełnych linii. Istnieją znacznie lepsze metody, ale będą bardziej skomplikowane.

Mike T.
źródło
Niezła odpowiedź. Prawdopodobnie użyłbym czegoś w rodzaju punktu ST_Interpolate, a następnie obliczyłem średnie odległości dla każdego zestawu powiązanych punktów jako podejście naiwne. Co miałeś na myśli o wiele lepszych metodach?
John Powell,
1
@ JohnBarça lepszymi metodami byłoby porównanie statystyk przestrzennych pokrycia każdej linii. Jedna metoda zrasteryzowałaby każdą linię, wykonała rozmycie gaussowskie z rastrem, a następnie określiła korelację zbieżnych wartości rastrowych z każdej kombinacji. Działa również metoda oparta na narzędziach ST_Segmentize i ST_Interpolate.
Mike T
4

Nie mam dostępu do PostGres / PostGIS, ale oto, jak bym to zrobił w ArcGIS (lub innym).

  1. Oblicz długość oryginalnych linii w kolumnie statycznej
  2. Buforuj swoje linie zgodnie ze sposobem, w jaki definiujesz „podobne”. Nie rozpuszczaj buforów. Bufory wynikowe będą miały FID równy oryginalnej linii.
  3. Przecinaj bufory i oryginalne linie. Powstała warstwa identyfikuje identyfikatory FID uczestniczące w danym skrzyżowaniu (na przykład „FID_lines” i „FID_buff”).
  4. Rozpuść warstwę z nr 3 przez dwie oryginalne kolumny FID i kolumnę o oryginalnej długości
  5. Zignoruj ​​wynikowe wiersze, które mają tę samą wartość dla dwóch oryginalnych kolumn FID przy użyciu zapytania definicji lub w inny sposób (oczywiście linia buforowana i przecięta z własnym buforem całkowicie się pokryje).
  6. Dodaj kolumnę numeryczną i wypełnij ją nową długością
  7. Podziel nową długość z oryginalną długością (na nową kolumnę), aby uzyskać stosunek oryginalnej linii, która wpada do bufora każdej pobliskiej linii.
  8. Sprawdź wartości współczynnika. Zachowaj te, które określiłeś jako „wystarczająco podobne”. Na przykład, być może linia mieszcząca się w buforze innej linii dla 75% jej długości jest wystarczająco podobna, być może twoja granica wynosi 50% zgodności itp.
łyko
źródło