Simplifying GPS data to plot polylines

I was reading Ryan’s post about Google Maps (Update 7/16/2011: link was 404) and could not resist hacking together a relatively simpleminded track simplifying script. It reads a GPX file and prints out the JavaScript necessary to plot the track using the Google Maps API.

Its use of the Google Maps API is pretty simpleminded (it just centers on the begin point at a fixed zoom level), as is its parsing of the GPX file (it assumes there’s only one track in it and there’s no error checking).

I hurried past those bits so I could see if my idea worked on a skate GPS track. It seems to. It reduced my 225 point sample track to 28 points and looks roughly right when I zoom into gmaps. One could adjust EPISILON for more or less simplifcation. A more sophisticated script could use a more clever mechanism for fitting a path onto the GPS points and then use the minimal number of points to plot the track. My mechansim assumes you want to preserve speed data with the points (though it doesn’t actually use it for anything) — in case you want to show something when there’s a big change in velocity.

A Span has a begin, end, and a time. A Span can be extended to a new end point iff the new endpoint is close (as defined by EPISILON) to where the extrapolated location would be from the old end point + the velocity implied by the Span would be.

Here’s the map. It’s a bit rough in spots, but so is the GPS plot. An EVEN MORE sophisticated version of this could know where the roads/trails are and fix the track accordingly.

Here’s the script:

The script requires numpy (rather gratutiously, but it was convenient) and takes the name of a GPX file as its first argument. It writes to stdout and is almost certainly not useful as anything more than an idea.

I initially planned to do this in JavaScript, but I realized it made a lot more sense to do it on the “server” side, before the data is sucked into the browser over the Internet…

Edit: The idea for this kind of “compression” of GPS plots was taken from the virtual GPS units that Ben implemented on Waterpoint, which record tracks for movement on the simulated ocean but use the same mechanism for reducing the number of track points stored.