Comparing Paths

Strava is a service that allows you to record, analyze and share your sporting activities. Strava RS is a TUI (terminal user interface) client for Strava that I’m working on. It provides an offline, keyboard driven, interface to Strava using data collected fro the Strava API.

One of the feature the Strava app provides is Matched Routes. If an activity you performed closely matches the route of any previous activities, you can list and compare your previous performances.

In Strava this is a premium feature. I wanted to implement this feature in Strava RS, which essentially boils down to: How similar is route A to route B?

I had no idea how to answer this question so, after googling and not finding anything was applicable (or if it was, I didn’t understand), I decided to figure it out by myself.

Disclaimer: there may well be better ways to solve this problem, my solution will be blindingly obvious to some, it’s possibly also wrong. But, well, I got a new graphics tablet and wanted to try it out.

The Problem ¶

Strava provides the routes as a series of latitude/longitude coordinates encoded using the Google Polyline Algorithm. Once decoded you have:

-2.44698, 50.62649
-2.44728, 50.62669
-2.44753, 50.62678
-2.44774, 50.6269
-2.44798, 50.62694
-2.44844, 50.62707
...

The full series would be plotted like this in Strava RS (actually the ParkRun in Weymouth)

⠈⢣                   
 ⢸⡀                  
  ⠑⡆                 
   ⠘⠦⣀⣀⡀             
     ⠈⠁⠱⡀   ⢀⣀       
        ⢣ ⡠⠊⠉⠉⡇      
         ⠉    ⡇      
              ⢣      
              ⣎⠖⢄    
              ⡇ ⠈⢲⡀  
              ⠧⡀  ⠑⢦ 
               ⠈⠑⢤⡀ ⡳
                  ⠉⠢⡟

Now, I want to compare my times for all attempts I made on this route. It’s inevitable that the exact set of coordinates for each attempt will deviate slightly.

Three similar and one dissimilar routes

Above we can clearly see that routes 1, 2 and 4 are the same shapes, and that 3 is clearly different. In this case 3 is actually the Dorchester ParkRun:

Weymouth and Dorchester are 5 miles apart

Route 3 doesn’t intersect with our run in Weymouth. Let’s overlay the 3 Weymouth Parkruns:

Three similar routes overlaid on top of one another

As a human we recognise them as the same “route”:

• They share the same geographical area.
• The paths are very close together.

But how to get a computer to recognise this? We can calculate the distance between the points.

Similarity Score ¶

Comparing two similar routes

Adding all the distances gives a score, in this case 0.76 and we can say that the black route has a similarity score of 0.76 against the green route.

Dorchester and Weymouth are not similar

Dorchester and Weymouth are clearly not the same route giving a similarity score of 481, so we could say that if the similarity score is less than 1.0 then we have a match! This seems like a good approach to start with.

However, as a human I was able to draw some arbitrary lines to geographically similar points, but unfortunately making the computer do this would be a whole different problem to solve. How do we determine which points to compare?

Normalisation ¶

Two similar routes with different number of coordinates

Route A has 20 coordinates and route B has 15 coordinates (vastly simplified).

We can normalize the routes to have the same number of coordinates, we can then score each coordinate against its counterpart:

Normalized routes with same number of coordinates

So we can now summarise the proposal

• Normalize the two routes so that they have the same number of coordinates.
• Sum the difference between the opposing coordinates to produce a similarity score.
• If the similarity score between two routes is below a given threshold it’s a match!

Now we’re getting somewhere, the number of segments will contribute to the accuracy of the matching. The more segments the greater the matching precision.

As a human I would obviously calculate the length of the path, divide it by the desired number of segments to get the segment length and then at each length interval add a new coordinate… or… wait there are more problems than answers in that solution:

• How to calculate the length?
• How to determine what the new coordinates should be?

Route Length ¶

I have been drawing curvy “analogue” routes, but in reality the route is a series of straight lines:

Routes are a series of straight lines

All we need to do is determine the length of each straight line. But how? Pythagoras to the rescue!

The Pythagorean Theorem allows us to determine the length of hypotenuse in a right-angled triangle if we have the lengths of the sides with the formular: c = √(a² + b²) (c is the square root of the sum of a multiplied by a and b multiplied by b).

Pythagorean Theorem

Our route can be represented as a bunch of triangles:

Triangles

And for each triangle we can determine the length c of the sides a and b and the sum of all those c values will be the length of our route.

Given the coordinates (a list of x and y):

1.5, 2.5
2.5, 3.6
2.9, 2.9
...

We can then determine the distance between each coordinate by considering two coordinates as a triangle and determining the length of the sides:

• side a has a length of xᵢ - xᵢ₋₁ (e.g. 2.5 - 1.5 = 0.75)
• side b has a length of yᵢ - yᵢ₋₁ (e.g. 3.6 - 2.5 = 1.1)
• the length of the line between the first and second coordinates is then length = √(0.75² + 1.1²) = 1.3313

So now we can calculate the length for each segment and sum them all to provide a length.

Plotting the New Coordinates ¶

Now that we have the length of the original path and can determine the segment length we can “walk” the path and record the coordinates where each segment ends. Surely the only way to do this is with a red carpet:

As preparation:

• Ensure you have a very long (infinitely so if possible) red carpet.
• Cut the carpet to the length of the route.
• Cut the carpet into 100 strips of equal length (increase number of strips for accuracy).
• Walk up to the first coordinate and roll out a strip of carpet matching the direction of the segment.

Then:

• Does the carpet extend further than the next coordinate?
• If so cut it at the intersection and place the remaining strip in the direction of the next coordinate.
• Otherwise calculate[*] the new coordinates based on the direction of the old segment and the length of the carpet from the last intersection and write them down.
• Repeat.

The only way to do this (a flowchart)

Having finished you should have a list of the normalized coordinates, but unfortunately there was a [*] as we didn’t explain how to calculate the new coordinates…

[*] Calculating the New Co-ordinates ¶

To determine the new coordinates we can determine the ratio (or percentage) of the segment that is occupied by the slice of red carpet.

• Calculate the remaining length c from the last known carpet-coordinate to the end of the original segment using pythagoras as before:

Calculate the remaining distance

• Divide the carpet slice length sl by the remaining length c to obtain the ratio or “percentage” (ratio = sl / c)
• Multiple the last known coordinates by the resulting ratio to obtain the new coordinates: xᵢ₊₁ = xᵢ * ratio and yᵢ₊₁ = yᵢ * ratio

Scoring ¶

Now we have two routes with the same number of coordinates and we can directly compare them:

To do this we need to determine the distance/length between the adjacent carpet coordinates (using Pythagoras again) and sum them up:

0.38 = sum(
    √((1.0-1.1)² + (0.5-0.6)²) = 0.14
    √((2.0-1.9)² + (1.3-1.3)²) = 0.10
    √((2.2-2.1)² + (2.1-2.0)²) = 0.14
)

Given the three points above we get a similarity score of 0.38!

Summary ¶

That’s basically how the route matching works in Strava RS - for any given route you can filter by “similarity”. The route will currently be compared against “all” routes which isn’t very efficient, but this can be vastly improved by pre-filtering by route length and perhaps then geographic boundaries.

Finish