Is there a way to identify and remove similar GPS tracks in PostGIS or ArcGIS?

Question

I have a large number of GPS tracks from a number of different users. I'd like to identify tracks that take the same route and remove those duplicates. For example, a user takes the same streets from the same origin/destination, but obviously with GPS accuracy issues, the lat/longs aren't exactly the same.

Any sort of intersect function simply provides a large set of intersecting sections, but doesn't compare a full track from start to finish.

Currently using PostGIS, but trialing in ArcGIS to visualize and test a procedure before applying it to the 1,000+ tracks and 8 million datapoints.

Answer 1

@relet seems to be going in the right direction but I think it would be better to create ST_Buffer around the lines and then use ST_AREA on the intersection of the two buffers and compare it to the area of the buffer of each track. Determining if the tracks go in the same direction would be more difficult though, comparing of segments suggested earlier seems to be the best.

Answer 2

The ST_Hausdorffdistance can be used to compare each line_geom against every other one with the same user_id. 500 feet is my boundary to check the two trips' origin points distance from each other to confirm the same route direction and the difference in trip lengths is determined before computing the Hausdorff distance. A Hausdorff distance that is less than 5% of the total trip length, for our project's purpose denotes two routes that take essentially the same path (that part is in a separate query).

SELECT a.user_id AS user_id_a, a.trip_id AS trip_id_a, b.trip_id as trip_id_b, 
ST_Length(a.line_geom) AS a_trip_length, 
(CASE   
WHEN abs(ST_Distance(a.orig, 
        b.orig)) < 500 AND abs(ST_Length(a.line_geom)-ST_Length(b.line_geom)) < 500 THEN    
        ST_HausdorffDistance(a.line_geom,b.line_geom) END) AS max_dist_diff 
FROM t_routes_lines a, t_routes_lines b
WHERE a.user_id = b.user_id 
ORDER BY a.user_id, a.trip_id asc, b.trip_id asc;

Answer 3

From the way you write it, the order of the points in the track is not important.

Assuming this, you can split each track into its individual points. Now, for every two tracks, calculate the sum of distances (or their squares) from each point in the one track, to any point in the other track. If the sum remains below your threshold, the tracks can be considered equal.

If that sum reaches a certain threshold, you can assume that the two tracks are distinct, and continue. In most of the cases, that threshold will be reached with the first point you consider, so the loop should complete reasonably fast. Depending on your threshold function and the differences you expect, you may want to divide by the total length of the track.

Answer 4

Depending on how accurately you must do the matching and how valuable it is to you, and assuming these tracks lie on streets (as you hint in your question), you could convert your tracks to routes on the street network. Once you've done the conversion, the routes are directly comparable. Of course, this raises the question of how to convert the tracks to routes on the street network (and requires that you have a database of all the streets.)

I would approach the conversion by taking the street network, buffering each street, then intersecting the track with the street buffers. If the track really is following streets, you should be able to find each segment on the street network from the beginning intersection to the ending one on each street. Not a trivial undertaking, but it would be very accurate for matching purposes.