This blog post is part of a series that start here.
I have already descrived what the Running Mate is and why I would like to build such a thing. Now, it’s time to get my hands a bit dirty with the mathematical theory that’s needed for this. I would not say that it is an advanced mathematics, but it is definitly a fun applicability since it is really easy to see and understand the purpose and need for the mathematic formulas.
So here’s my 10 km run again. Let us focus on small area of this run: the square that the red arrow points at:
If we enlarge this square area, it would look something like this:
As you can see, I’ve painted some blue stars on the map and high-lighted the road with a black line. The blue stars signify the GPS points that my running mate is picking up with the help of the satellite(s). I don’t know how often these coordinates actually come, but naturally, I will not be able to get the exact track of my run. By drawing a line between the coordinates we will se how the running path looks like according to the PGS system. Here is another image high lighting the coordinates with their straight lines between them in an X-Y graph instead:
Calculating the distance between these stars in this graph is simply a matter of utilizing the Pythagorean Theorem. I honestly think that no matter how rusty your math knowledge becomes, this formula will forever stick in your head:
z2 = x2+y2,
z is evidently being the sought distance between two of the stars in my graph. So in order to withdraw the distance between the second and the third coordinate, the formula becomes:
z2 = (x3-x2)2+(y3-y2)2
Calculating all distances between all coordinates on the map gives us the total distance which is exactly what shapelink.com did for me when I utilised their service to draw my run on a map. Basically, I gave them the coordinates by clicking on the map and they drew the lines in between these coordinates and calculated the total distance of the run.
But we are still not at where I want to be: getting the current time comparison of each spot to a previous run. And this is where the fun begins.
The difficult part here would be to compare different coordinates from different races with each other. Naturally, the coordinates will not be on the exact same place as the previous coordinate. This image will illustrate this:
Here I have high-lighted a second race coordinate with red stars. As you can see I did not run the exact same spots as I did the last time I ran the race. The deviation shown is most likely larger than what would be in reality considering that the track I run on is quite narrow. But nevertheless, I obviously have to take this into account when comparing the coordinates.
Naturally each coordinate also has an associated timestamp. As I see it, finding the coordinates that are closest to each other in order to calculate the difference between the two timestamps can be done in at least two different ways. Let us start with the easiest one.
Algorithm: Finding the closest coordinate
So, as this image shows, we have to calculate the distance (d1, d2, and d3) for each red coordinate to all blue coordinate and pick the one that is the closest to the red coordinate. The needed calculation is basically just a matter of using the Pythagorean Theorem again a number of times, so it is a piece of cake really.
In the example in this image, the d3 distance is obviosly the shortest one so this coorrelating blue coordinate is selected as the one to compare against the red coordinate. The difference in timestamp between these two coordinates would give you the desired result for the Running Mate application. If we don't need a more accuracy result, this is where we would stop.
However, of course we want more accuracy, so let us move on to the more interesting algorithm.
Algorithm: Interpolating the time
As you might have gathered, the previous algorithm is not particularly accurate when the number of coordinates is low for a run. If the number of coordinates approaches infinity (as mathematicians do love to state) the result would indeed be good. But if merely a few coordinates would have been used for the whole track, naturally this first algorithm just doesn’t cut it. This is when time interpolation is needed.
In this image we are focusing on two of the blue coordinates, B1 and B2, that lies closest to one of the red coordinate, R1. Basically, we want to find the V (as in Virtual) coordinate in order to find the time interpolation between the B1 and B2 coordinate. All we have to do is to calculate the ratio of the distances between the coordinate V and the B1 and B2 coordinates. This ratio will give us the needed number in order to calculate a new blue time stamp at which the virtual V coordinate is located.
So in theory, this algorithm seem to boil down to the following steps:
- Find the two blue stars that are closest to the red star.
- Find the coordinates of the virtual coordinate V.
- Calculate the ratio of the distances between coordinate V and the two closest blue coordinate.
- Calculate the virtual timestamp of coordinate V using the ratio found in step 3.
- Compare the timestamp for the red coordinate with the new virtual timestamp for the coordinate V.
The only difficulty here really lies in the second step of this algorithm, i.e. finding coordinate V. So let us concentrate on the information we do know, i.e. the known variables. Consider the following image:
Here, d1 is the distance between B1 and R1, d2 similarly between R1 and B2, and finally d3 being the distance between B1 and B2. Ok, these distances are not known, but we do know that if we have the coordinates, we can easily calculate the distances using … yes you guessed it: the Pythagorean Theorem. So we can consider these distances as known.
Ok, next would be to calculate the angle α at the B1 coordinate. Knowing all distances d1, d2, and d3 in this triangle we can utilize the Law of cosines:
d22 = d12 + d32 - 2d1d3cos(α)
The only unknown variable here is the α angle which a bit of algebra magic solves for us.
So when we have α, we can calculate the distance dv, i.e. the distance between B1 and V coordinates with the following basic trigonometry formula:
Cos(α) = dv / d1.
Again, a bit of algebra gives us dv and you know what? We are actually home safe now with this knowledge. Basically we now know the ratio in distance V between B1 and B2. Now all we have to do is to apply that ratio to the timestamp of B1 to get V coordinates virtual timestamp.
I have not yet had the time to implement the second “interpolating the time” algorithm in my Running Mate code demo as available at Codeplex, but when I have I will delete this sentence and add a comment about it.