CODEWITHSUNDEEP
algorithmgeolocationgpsgis
gregspurrier
gregspurrier

Reputation: 1458

Identifying common route segments from GPS tracks

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.

Upvotes: 9

Views: 2715

Answers (2)

Federico
Federico

Reputation: 296

This seems a very general question that pertains to many GIS problems.

After some search, it seems you would need to apply some algorithms for computing the similarity between any two routes. Wang et al. (2013) analyzes a number of such measures. However, all these measures are implemented by dynamic programming with time complexity of O(N1N2), where N1 and N2 are the number of points in the two routes.

A more efficient solution is provided by Mariescu-Istodor et al. (2017) in which each route is transformed into a set of cells in a predefined grid system. The paper also defines the measure of inclusion as the amount of one route contained inside the other, which seems to relate to the second point in your question.

Upvotes: 1

ElKamina
ElKamina

Reputation: 7807

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.

Upvotes: 1

Related Questions