Thursday, November 18, 2010

total climbing and descending algorithm: correct version

Last time I demonstrated how important it is to take some care in pruning points to simplify the profile while conserving climbs which are in excess of the minimum threshold. Before that, I'd proposed an algorithm to calculate total climbing and descending, but I was sloppy. Nevertheless even my flawed algorithm demonstrated that a climbing threshold of 5 meters was desirable.

There's one key thing I was missing in my previous algorithm, and that's to make sure pruned segments are bounded on both the high and low side by adjacent points. So here's my revised approach.

First, merge monotonic segments, as follows:
  1. Start with the first point.
  2. Until the following two segments are either climb-descend or descend climb, or until the following point is the final point in the ride, delete the following point.
  3. Move on to the next point and repeat the previous step if there's at least three points past the current point.

So now the profile consists of uphill segments alternating with downhill segments (or perhaps just a single flat segment if there's no climbing or descending in the route). Next we prune it down:
  1. Start with the first point.
  2. Check to make sure there's at least four points starting with the current point; if not, we're done.
  3. If of the four points starting with the present point, if the difference between the middle two are less than the climbing threshold, and if neither of these middle two points are greater than both the first and last points nor less than both the first and last points, then delete the middle two points and back up two positions (or to the start of all points if there's fewer than two points prior to the present position). If there was no deletion, move to the next point.
  4. Repeat step 2.

There we go: that's it. An example, where the threshold is 5, follows. The current point will be marked in green. S point about to be deleted will be marked in red:

We start at the first point:

1, 2, 4, 3, 6, 2, 7, 6, 5, 4, 6, 1

The next The next two segments are both climbing, so we delete the next point:

1, 4, 3, 6, 2, 7, 6, 5, 4, 6, 1

Now we have a climb-descend combo, so we move to the next point:

1, 4, 3, 6, 2, 7, 6, 5, 4, 6, 1

Now a descend-climb, so next point:

1, 4, 3, 6, 2, 7, 6, 5, 4, 6, 1

Climb-descend, so next point:

1, 4, 3, 6, 2, 7, 6, 5, 4, 6, 1

Descend-climb, so next point:

1, 4, 3, 6, 2, 7, 6, 5, 4, 6, 1

Again, to the next point:

1, 4, 3, 6, 2, 7, 6, 6, 4, 6, 1

7-6-6 doesn't have both a climb and a descent, so the middle point goes:

1, 4, 3, 6, 2, 7, 6, 4, 6, 1

7-6-4 lacks a climb, so the middle point gets pruned:

1, 4, 3, 6, 2, 7, 4, 6, 1

Now we have a 7-4-6 descend-climb, so next point:

1, 4, 3, 6, 2, 7, 4, 6, 1

4-6-1 is good, and these are the final three points, so we're done with the first part. Now we go to the second part... back to the first point:

1, 4, 3, 6, 2, 7, 4, 6, 1

The first four points are 1-4-3-6. The middle two points are encapsulated by the outer two, and the difference is less than 5, so they go. Normally we'd back step twice at this point, but we're at the first point already, so there's nowhere to go:

1, 6, 2, 7, 4, 6, 1

Again the points are within 5, and neither is either the largest or smallest of the four points starting with the current point, so again the middle two get snipped:

1, 7, 4, 6, 1

Here the 7 and 4 are less than 5 apart, but the 7 is the largest of the four, so we don't want to delete it. So we move up:

1, 7, 4, 6, 1

Here the 4 and 6 are less than 5 apart, and neither is larger than the 7 or less than the 1, so they go, and we back up:

1, 7, 1

There's fewer than four points left starting with the current point, so we're done.

So from those original points:

1, 2, 4, 3, 6, 2, 7, 6, 6, 4, 6, 1

All we ended up with in the end was the climb from 1 to 7 and the descent back. We could run the points in the opposite order and get the same result.

2 comments:

Péter I. Pápics said...

Thanks for the algorithm, I just implemented it in my python code which I use to analyze and plot my ride data, and it works perfectly. (I have a standard flat training route along a channel, and because of GARMIN's elevation jumps, there was always ~80m of elevation gain accumulating on a 2h ride, now this problem is gone!) I am sure if I had to come up with such a nice solution, it would have taken some time... Your blog is a huge source of ideas for plotting! I love plots :]

BTW, if you are interested, you can have a look at the output of my code, it is mainly plots and a statistics file, everything is under development (but it is just for fun and my personal use), but I think it looks already good. So have a look here: http://ster.kuleuven.be/~peterp/20101003_125318_51547498/

djconnel said...

Very cool! Thanks for testing it out... and for your nice comments!

Dan