Google Maps is a great service. It's a marvel of modern hackery that we can view a fully-featured cartograph inside the frankenstein monster of the internet we commonly call a web browser. A piece of software that was originally intended only to view multimedia documents (images and text, basically), now feels almost like a desktop GIS application. It's truly amazing.
And with the continually growing list of API features (geocoding, marker management, etc), it seems like there's litte left for us client developers to tackle. Well, it turns out there are still a few interesting problems that Google Maps' API has not solved yet. One of those problems is something that's been plaguing WalkingBoss lately: slow or faulty page loads due to very large numbers of track points (GPoints).
WalkingBoss users routinely upload trips that number in the multiple thousands (if not tens of thousands) of points. When plotting these directly on a Google Map, you'll be dealing with a very sluggish browser. In some cases, the page won't load at all due to "script timeouts." Firefox has become more forgiving of these long page loads in the recent releases, but Camino is still very uncooperative in this respect. I would estimate that 30-50% of the trips on WalkingBoss are not viewable in Camino because of this problem. Yikes!
So, naturally, I've been wanting to solve this problem for a long time. The most obvious approach is to plot as few points as possible without deforming the shape of the original track. In the vast majority of cases, this is, in the words of Darth, "All too easy."
Most GPS devices are bubbly chatterboxes when it comes to logging track points. They spew multiple points per minute, which is far more than most of us (who are not traveling in rocketships) need to view our tracks. The real problem, then, is what kind of funky math do we need to know in order to find the points that are just extra "noise" on the trackline?
I considered putting on my own thinking cap and re-inventing the wheel on this one, but I'm so lazy. Larry Wall would be proud of my laziness. It's that good. So rather than breaking out my old trigonometry books (which I've long since sold or lost), I just passively googled for about 5 months, looking for terms like "route reduction", "track simplification", and "how do i get rid of all these f#$%ing gps points?" In this day and age of Google solving all my problems, I was really surprised at the small amount of material I found on this subject. In the end, I bookmarked two pages. That's it. After reviewing probably hundreds of search results, I found two pages.
Here they are: Route Reduction by greatred and the GPSBabel docs on their Simplify Routes filter. The route reduction algorithm described by greatred is a distance-based algorithm, where the points with the least effect on a track's total distance are selected for removal. One of the two filters employed by GPSBabel is based on a similar metric (it might be identical, I'm not sure). The other simplification filter from GPSBabel is based on cross track error (XTE), or the perpendicular distance from a given track to a position outside of that track.
All of these algorithms are essentially the same basic algorithm--the difference is the metric used in determining which points to keep and which to throw out.
I came up with the diagram at right to illustrate how these algorithms work. A sliding three-point window iterates over all points in the track, assigning a metric to each point. At the end of this iteration, the points are sorted by the metric, and those points with a low value for this metric can be safely removed without disturbing the overall route shape.
My implementation of this, based heavily on GPSBabel's excellent XTE code, but written, of course, in Ruby, has improved the load time in some WalkingBoss pages by factors of ten! I'm still in the testing phase for this enhancement, but I hope to have WalkingBoss automatically simplifying large tracks on upload by the end of next month. Of course, once it's ready, I'll make it part of the GPX gem, so you can run it standalone on your own tracks.
If you are one of my non-programming readers and you've made it this far, God bless you! Next post will be much less boring, I promise!
Leave a Reply