Sign up ×

I am attempting to take GPS data and track it on a map and see if it follows a given path. I have the path as a set of points and the GPS data streams in as a similar set of points. I am attempting to track the progression of the current position across the path and I am wondering if there are any well known algorithms for this. I have come up with my own that works ok but it is a complex enough problem that I would like to minimize the amount of re-inventing of the wheel that I do.

What approach or algorithm would you recommend taking for this problem?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Just thinking it out, first I would get the formula to calculate the nearest distance from a point to a line. When you say you have the path as a set of points, I assume it's a directional graph and not just a set of points.

Then I would do an algorithm like this: (there are probably logical errors, but the idea is there):

loop through every line in the path
     get the line which is closest to your current point
if the nearest distance is greater than some threshold
     return not on path
#you could check if the nearest line segment is the next expected one if you want to do checkpoints 

for the formula:

share|improve this answer
Yes the points form lines, though with U-turns and looping on ramps it gets pretty interesting. I actually started out with what you were recommending but found that it had problems with U-turns, where a point further down the path might actually be closer to your current position which is actually between two earlier points. – Dec 5 '12 at 5:44
That is a great link though, I will have to reconsider this. Thanks. – Dec 5 '12 at 5:49
Actually I think that was exactly what I needed, thanks again. – Dec 5 '12 at 6:16
glad it helped. If you leave out the commented section at the end it will work regardless of what direction you're moving on the path. It just keeps track of how far you deviate from the path in general. Keep in mind this is a brute force approach and could probably benefit from some graph, trig, or heuristic trick that I wasn't thinking of, but on graphs of linear size it should be fine – brandon Dec 5 '12 at 14:55

Your Answer


