5x12 pentomino tiling

Going Up ... and Down


I've been struggling for some time now with the problem of calculating ascent and descent for a walk based on a GPX track (where you've been as recorded on a GPS) or route (where you intend to go).

There's two problems with this. The first is that of how high you actually are at any point on your walk. Although your GPS is very good at working out where you are in the X and Y axis, typical accuracy even without WAAS/EGNOS when your GPS is able to get a good view of the sky can be pretty damn good, certainly within a few metres. The Z axis is another matter. It takes a typical GPS rather longer to get a vertical fix and, when it does, it is less accurate, ±10-20m perhaps1, depending on what satellites it can see2.

So this presents me with a problem in that users turn on their GPS, get a 2D fix and then reset the track data before they've got a 3D fix. Hence the first few track points they record have height data which is either non-existent or way off.

The other related problem I have is that I would like to be able to calculate ascent and descent for a GPX route which has been created using software (like one of our mapping web sites for example). Here I have no elevation data in the route: routes are two dimensional consisting of a series of waypoints defined by latitude and longitude but not height.

So both of these issues leave me scratching about for another source of height data and this is where I get lucky as the Ordnance Survey have released their height data on an Open Data licence. It's called Land-Form PANORAMA®. So I've got the height of every point in the UK on a 50m x 50m grid to an apparent accuracy of 1m which I have stored in a 4GB MySQL database on one of our servers.

This frees me up from relying on GPS elevation data, instead I can use the Ordnance Survey data to determine heights. So what I do to work out the height of any arbitrary point is to take the weighted average of the heights of the four points on the corners of the 50m x 50m square it lies within.

With that technology I can then look at my track or route. Starting at the first point I then walk along a line to the next point in my track or route stopping every 100m to take another height sample if it's more than than 100m between points (which it typically is with routes but isn't with tracks).

So it's easy now, you're thinking, all Paul needs to do is compare each new step to the previous one and if it's higher add the delta to the total ascent and if it's lower add the delta to the total descent.

And indeed, that what I did. But that's where the second problem came in as it's always produced results which looked less than plausible. Total ascent and descent were far higher than seemed likely. This for example is a walk we did up Ingleborough a couple of years ago:

Date started:27/08/09
Distance:9.6 miles
Time taken:23580
Moving time:5:1
Average speed:1.92mph
Maximum speed:22.05mph

The start point of that walk is at about 170m. The summit of Ingleborough is 724m and the walk is pretty much up and down, there's very little in the way of intermediate down. So you'd expect the ascent and descent to be around 600m. In reality I was getting figures of over 1000m. Even after revisiting the code and tweaking the way the figures were calculated I still was getting total ascent of 873m and descent of 714m which we're both implausibly high and oddly asymmetric.

Finally I did what I always told my programmers to do when I had a proper job: I sat down and put some debug in. I dumped all the heights my code was calculating: 873 of them and looked at the deltas I was getting. And there it was - lots of jitter, even using the OS data. Typically less than a metre but over that many points it starts to add up and I think that's where the problem was.

So today I switched to a new algorithm. I start off by deciding if we're going up or down. Assuming we're going up I log the start height and then track the maximum height we've reached ignoring any drops I see which are less than the maximum height by under 5m. Only when I see a drop of more than 5m do I declare a change of direction adding the distance climbed since last change in direction (i.e. maximum height minus start height) to my total ascent and making the highest point my new start height for my descent. Now I work the algorithm in reverse, ignoring small rises of less than 5m.

And this seems to work. The figures for this walk come out at 635m and 635m descent which seems more plausibly symmetric and far closer to the result I was expecting.

  1. My thanks to Hugo for confirming this, and for his words of wisdom in relation to footnote 2.
  2. And that's before you start worrying about what datum they're using in which to give you the heights. My Garmin Fortrex 301 GPS for example gives heights which appear to be a lot closer to OSGB36 than WGS84, so you end up with a GPX file containing X and Y coordinates in one datum and Z coordinates in a different datum! But that's another story, and as we're only concerned with changes in height here it's not an issue.

Tags: maps, web design Written 19/04/12

Comment on this article

You can follow these posts on Twitter at @Wibblings
I am currently reading:

Fire and Steam by Christian Wolmar Snuff by Terry Pratchett

Word of the Day: