Splining GPS Tracks

The above image shows the original GPS track in green and the splined curve in yellow. Image was taken from TopoFusion. To spline (and simplify) a track in TopoFusion, right click on it in the main map window and select Spline/Simplify Track.

Select either simplify or spline and use the appropriate slider to control how many points are added to or deleted from the track. As the sliders are moved the result is shown in a different color in the map window. Pressing OK on the dialog will replace the original data with the simplified or splined data (you can then right click on the file and use Save as.. if desired). Hitting cancel will leave the data unchanged. Details on the implementations of both functions follow.




Simplification

Simplification is performed by evaluating the error introduced by eliminating each point from the track. The point which when deleted will yield the smallest error from the original track is selected and deleted. This process continues until the desired number of points is reached. The algorithm is implemented as efficiently as possible--distances are precomputed and only updated when necessary. It runs fast enough that it was hooked up to the slider bar to run as the value changes. It's interesting to see how you can eliminate many points without losing much detail in the track.

Interpolation

Tracks recorded by GPS devices are approximations. They are a set of discrete data points taken along a curve--the actual path traveled. Splining, or interpolating these data points is an attempt to recreate the actual curve traveled. The result is a more accurate and better looking track. Typically the length of a track will increase to a more accurate level when splined. For trails with switchbacks or sharp corners splined tracks produce a better mapping of the trail.

First, we are using interpolating splines rather than approximating splines. We trust the actual GPS data points to be accurate (as accurate as possible during collection) and therefore we want the curve to actually go through every data point. Approximating splines do not have this requirement. Typically, GPS points are at least accurate with respect to surrounding points; so the overall shape and relative positions should at least be trusted.

We have found the following method to give the most satisfactory results for interpolating GPS collected data. We use piece-wise cubic Bessel interpolation. Piece-wise means that we fit a cubic curve between each pair of successive data points. We employ Hermite boundary conditions which ensures continuity of slope at each join point. Bessel interpolation is used (by fitting a parabola through each of three consecutive points) to estimate the value of the first derivative at each data point.




Choice of parameterization

There is a key difference between splining a function and splining a curve. With GPS data we have no function, only discrete data points placed in order. Our data points are 4D, (x,y,elevation and time). To fit a curve to this data requires defining four parametric functions (one for each dimension). One must choose the T values corresponding to each data point.

The obvious question presents itself: which parameterization is best? It turns out that this is still an open research area. No "best" parameterization has been found. Examples paremeterizations include: uniform, chord length and centripetal, but there are many other, more complex methods. We have experimented with all three methods as well as different methods for approximating the derivatives by fitting quadratic curves.

TopoFusion's spline function gives you the choice between uniform and non-uniform parameterization. The non-uniform case uses a parameterization based on the 2D distance between the points. This method gives the best results for the data we have tested on.

The spline function also allows you to control the number of points inserted between data points. This will control the factor by which the GPS data will grow. Another slider allows control over the strength of the first derivatives at each point. This value is simply multiplied by all of the derivatives. Increasing the slider will push the curve out further from the original polygonal line and will often result in self-intersecting loops (a major problem with all choices of parameterization). This slider gives the user control over the resulting curve.

Download splined GPS data for Fantasy Island in GPX format (zipped).
The original data can be downloaded on GPX Maps

Warning: Splined GPS data can get large (20,000+ points). Be careful loading spline GPX files in programs other than TopoFusion!

Note: Most of our experiments were performed on GPS data collected using various Garmin eTrex units on the "Auto" collection method.