Determining path user is on based on GPS location

Question

I'm writing an app that takes advantage of GPS information to determine what road/trail (or "way" in OpenStreetMaps terms) a user is on. Ways in OSM do not include width information, just a series of points connected together, so it isn't a matter of figuring out which poly box a GPS coordinate is in.

The information I have is the list of points that define the trail as it bends (if it was just a straight trail, could be 2 points 1/2 mile apart). These trails are usually separated by tree-lines (say 50-300m apart) and there can be lots of them within a park so accuracy without width information can be tricky in edge cases. Usually the way definition runs down the center of the trail.

It seems like I need to calculate all the individual vectors on a trail, then find the nearest vector. I'm concerned about this being rather intensive to do with every new GPS update (every 1-4 seconds?). I could at least try to fill out the points on each trail (force a point every x meters) ahead of time and then just get nearest point as the GPS updates.

Are there any structures that the point-data could be adapted into up-front to assist in the calculations? Any other known algorithms to solve this problem that are mobile-contraint-friendly? Seems like this should be an already-solved problem.

Answer 1

This is solved, it is called Map Matching.
I have written such a system for tolling purpose. There are variants related to be real time matching, like in navigation systems, or non real time like mine for post processing GPS data.
But in every case it is at least some month of developing effort.

Things start to get difficult if you have one trail which forks in two paths.
If you don't have a problem when the wrong path is matched in such situations, you can simply search the nearest one.

To avoid to much CPU power use a geo spatial index, like quad tree or k-d tree.

Answer 2

Presumably you're using a map rendering API which draws the map from some data format. This is essentially a special-purpose database known as a spatial database. It should, in an ideal world, have an efficient function for finding all the roads and paths within a certain distance, say 50 metres.

Once you have that list of nearby roads and paths, which even in a heavily built up area, right next to a junction, won't exceed the low tens in number, you can go through them one by one and find the closest one to your GPS fix. There are standard ways to find the closest point to a line; there's a discussion here: get closest point to a line.

This system should (from my experience) be easily fast enough for GPS updates every second.

It's even faster if you're following a predetermined route, because then you need only check the segments of the route - and, of course, notify the user if he or she is too far from the route to be deemed to be on it, and then create a new route. That's what sat-nav systems do.