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.

  • Pick your first coordinate. Now, skip the rest until you find one more than {threshold} miles away. Process that coordinate, then repeat. – Dan Pichelman Oct 2 '15 at 21:25
  • Maybe this site is a better place to ask this question: gis.stackexchange.com . Also, the pronoum "I", in english, is always capitalized, not only at the beginning of a sentence, but anywhere it appears. – Tulains Córdova Dec 17 '16 at 23:45
  • @TulainsCórdova Since i'm asking for help with an algorithm, so i believe i'm in the right place. Also i write my Is in lower case letters intentionally. But speaking of grammar, pretty sure "pronoum" is written with an "n" at the end, thus rendering your reply as unconstructive as this. – konqi Dec 19 '16 at 10:04

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.

  • Thanks for this insightful answer. I agree that bike rides are, relatively speaking, short. However there is one GPS point per second and given the slow nature of bikes (again relatively speaking) the data masses up to a pretty dense point cloud, so reducing the data is in order first. Just an example: My rides are usually about 4 hours long, that's around 14k data points making the location api request quite heavy. Ideally i'd like to reduce the GPS points to their statistical anomalies (pauses&co) and request location data for just those. For now i'll dig into all those topics you mentioned. – konqi Oct 16 '15 at 9:33
  • Do you have a bounding box API? I agree that without that, you certainly will want to reduce the number of points first. With a bounding box API, your problem starts to depend more on the area enclosed (sort of) than the number of points. – J Trana Oct 17 '15 at 13:30

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.

  • Thanks for your answer. This will probably solve the amount of requests but does not help much with the liklyhood of a location beeing visited or being the intended destination. Any ideas for that? – konqi Oct 6 '15 at 9:45
  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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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