Identifying common route segments from GPS tracks

Question

Say I've got a bunch of recorded GPS tracks. Some are from repeated trips over the same route, some are from completely unique routes, and some are distinct routes yet have some segments in common.

Given all this data, I want to:

1. identify the repeated trips over the same route
2. identify segments which are shared by multiple routes

I suppose 1 is really a special case of 2.

To give a concrete example: suppose you had daily GPS tracks of a large number of bicycle commuters. It would be interesting to extract from this data the most popular bicycle commuting corridors based on actual riding rather than from the cycling maps that are produced by local governments.

Are there published algorithms for doing this? How do they work? Pointers to papers and/or code greatly appreciated.

Answer 1

You can use 3D histogram find the most visited points on the map. Using that you can derive the most used paths.

Detail: Keep a 2D matrix count and initialize it to 0, X[i,j]=0. For each track, increment X[i,j]s on the path. Once you have processed all the tracks, threshold this matrix to min threshold (what is the minimum number of tracks for it to be a repeated trip?).

Some practical details: Assuming you have set of points through which path goes. You can find the set of points on the path between two such points with http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm . You might want to draw a "thicker line" to account for the noisy nature of the data.