Find likely candidates for visited locations along GPS track

Question

I'm creating a visualization tool for workout data, specializing on bicycle rides. I'm looking for ways to generate more value from the data that was recorded. Since there usually is a GPS track available I was wondering if and how I could extract possible visited towns or special locations during the trip. I'm especially interested in the possible intended destination of a trip.

Now this is really easy if you have a track that goes from location A to B but my tracks are usually round courses where the start and end location are the same.

Some special cases exist where the destination should be relatively easy to determine. Those are:

• There is a location where the recording was paused, thus causing a gap in the recorded data
• Recording isn't paused but the location stays the same for a considerable time. The likely candidate for the intended destination would be the longest of such periods.

Assuming we don't encounter one of the above circumstances I'd like to create a list of cities / special locations visited or rode by.

I can imagine narrowing down the search by dividing the track into thirds and only analyze the middle segment, which most likely contains the intended destination.

Now there are APIs available that could give me nearby locations to any given GPS point but asking for the information for every point would cause thousands of requests, since there usually is one GPS point available every second.

Now my question is:

Is there any known algorithm or technique that would decrease the number of requests I would have to send to a location API? If not, what would be a good way to find possible intended locations along a GPS track if the track contains no pauses or hot spots where the location is approximately the same for a extended period. I realize this is the same question as asking for any special location along a segment of a GPS track, which I have no good idea for either.

An example of the desired result would look like this:

1. A GPS track is uploaded
2. The algorithm/program returns a list of locations with name and address, like:
   • City A, address
   • City B, address
   • Restaurant A, address

Also all ideas including how I could structure and group the location data to help with the analysis are appreciated.

Answer 1

The API which gives you nearby locations to a given GPS point must work with some kind of radius, either implied (stated in the documentation) or explicitly passed as a parameter. Suppose this radius is R.

So, send a request for the first point in the path, and then start skipping subsequent points for as long as you are within R. Once you reach a point outside R, send your next request, and start counting from that point. This way, you are not sending unnecessary requests, so the number of requests will be significantly reduced.

If you find that you are still sending too many requests, then increase R.

Answer 2

So I think it is going to depend on the nature of your data quite a bit. Whatever you choose to do, understanding how your data looks, feels, and scales is going to be important.

Frankly, assuming bike rides are often short, I suspect that calculating one or more bounding boxes for the bike ride, fetching all points of interest within the box, and then doing all further processing locally is going to be your best option. Again, try to get a feel for the scales involved, but that's my hunch. One or a few heavy requests vs. thousands of pinpricks is likely going to be way faster.

So once you have the list of locations, you can do local distance calculations without too much pain. Note that depending on scale you may need to employ a spatial structure like an R-tree etc. locally; another potential tool would be to reduce the curve to a much smaller series of line segments and then consider point-line segment distances.

After that, it's going to get subjective with regards to finding the final destination/waypoints. Here are some thoughts:

• In addition to pauses and stops, I think your hypothesis of the middle third is good. You may be able to extend this to a general weighting scheme, or generalize to more of a "k-means" sort of an approach.
• Do you have information regarding the general type of point of interest? Some points of interest inherently require stopping to feast (cycling past a restaurant is just not as satisfying) and some may be primarily a feast for the eyes (parks etc.). So that can be used to filter too: going near a restaurant without a stop is an unlikely destination, going near a park likely does not require stopping. Note that a simple heuristic by name may go a decent ways here for type of stop.
• Similarly, distance by type of point of interest may be valuable. Restaurants would require an exact hit, parks would require a close hit, and scenic views may be much more distant.
• It would be interesting to look at the role of inflection points in the curve vs. points of interest - I don't know if there is a positive correlation but there could be.

Good luck! Let us know how it turns out.

Answer 3

1. Get all possible destinations within bounding box of your GPS trace.
2. Find the ones that are closest to the actual route.
3. Rank them by:
   • time spent in their vicinity
   • time spent before and after them (ie, weighting for "middle of the trip")
   • other factors like interestingness of destination (based on whatever you know about your user(s))
4. Pick the best.