Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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
add comment

1 Answer

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: http://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment

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. –  justin.m.chase Dec 5 '12 at 5:44
    
That is a great link though, I will have to reconsider this. Thanks. –  justin.m.chase Dec 5 '12 at 5:49
    
Actually I think that was exactly what I needed, thanks again. –  justin.m.chase 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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.