I am working on a tool which uses the Google directions API in order to follow a particular walking route automatically using Google StreetView images. The directions API returns a lot of details in either XML or JSON formats, but the specifics of the route are encoded using an ASCII encoding technique (Encoded Polyline Algorithm).

For example, if I look for a walking route from the London Eye (`51.503177, -0.119451`

) to Trafalgar Square (`51.507651, -0.127734`

), I access the API with the URL `http://maps.googleapis.com/maps/api/directions/json?origin=51.503177,-0.119451&destination=51.507651,-0.127734&mode=walking`

and get the following encoding for the route overview (note that it includes an escape sequence: `\\`

)

{ejyHriVuBa@oE{A]SWWMQADC?WSCB_FhUe@lBM`AFFEZE\\EjB{@zHkAhKOFMTCZAD

### Initial Conversion

In order to decode, the first thing I need to do is convert the character values back into the individual 5 bit values as per the algorithm, so with a bit of magic:

let s = "{ejyHriVuBa@oE{A]SWWMQADC?WSCB_FhUe@lBM`AFFEZE\\EjB{@zHkAhKOFMTCZAD" s |> Seq.map (fun ch -> int(ch) - 63)

This gives the following result (converted to an array just for the purposes of displaying more than 4 elements):

val it : int [] = [|60; 38; 43; 58; 9; 51; 42; 23; 54; 3|]

Note that this sequence is 5 bit values in a 6 bit encoding. The high order bit is set to indicate when more values follow, so in the above case there are three sequences: 60,38,43,58,9 then 51,42,23 and 54,3.

### Splitting up the Input Sequence

What I need now is to split the overall sequence into subsequences based on subsequence termination when the high order bit is clear (i.e. the value is less than 32). I could use `Seq.takeWhile (fun d -> (d &&& 32) = 1)`

but unfortunately this sequence would omit the final value. For this reason, I wrote a revision of `takeWhile`

and `skipWhile`

along with a function for splitting the sequence (this is also published on fssnip as a generally useful set of functions – and I welcome tips on how to improve them).

let notEmpty s = not (Seq.isEmpty s) // inclusive version of takeWhile - includes the element which broke the condition let takeWhileInc cond s = seq { yield! s |> Seq.takeWhile cond let r = s |> Seq.skipWhile cond if notEmpty r then yield r |> Seq.head } // inclusive version of skipWhile - also skips the first element which broke the condition let skipWhileInc cond s = let r = s |> Seq.skipWhile cond if notEmpty r then (r |> Seq.skip 1) else r // split a large sequence into a sequence of sequences, determined by a splitter condition let rec splitSubSequences cond s = seq { if not (s |> Seq.isEmpty) then yield (s |> takeWhileInc cond) yield! (s |> skipWhileInc cond |> splitSubSequences cond) }

This means that we can use any predicate we like in order to determine the sequence seperators. So in order to test this method, I can try something like:

> [| 1;1;0;0;1;0;1 |] |> splitSubSequences (fun d -> d = 1) val it : seq<seq<int>> = seq [seq [1; 1; 0]; seq [0]; seq [1; 0]; seq [1]]

Therefore we can pipe the output of our previous conversion into this function, with a modified predicate:

s |> Seq.map (fun ch -> int(ch) - 63) |> splitSubSequences (fun d -> (d &&& 0x20) = 0x20)

Giving:

val it : seq<seq<int>> = seq [seq [60; 38; 43; 58; ...]; seq [51; 42; 23]; seq [54; 3]; seq [34; 1]; ...]

Fantastic. So at this point we now have the groups of values, each of which represents a single coordinate offset value … except that some have the high order (sixth) bit set – we will need to clear this down before we can convert these groups into the single values. Note that the most efficient way to do that would be within `splitSubSequences`

, but I want to keep that function nice and generic, so instead we will pass through another map on the pipleline:

|> Seq.map (fun r -> r |> Seq.map (fun d -> d &&& 0x1F))

Note that this is one map for the outer sequence, and another map for each inner sequence, resulting in the desired sets of 5 bit values.

### Some bit Shifting

This is the point where the imperative implementations I looked at start to get ugly. Each value in the set represents five bits. We need to combine these values into one, starting with the first (which is the low order five bits) and adding in each successive value, shifting the bits left by five each time. In a functional language, this can be achieved using a single `fold`

:

|> Seq.map (fun r -> r |> Seq.fold (fun (sh,tot) it -> (sh+5),(tot ||| (it<<<sh))) (0,0))

Once again we use a map for the outer sequence, and apply the fold to each inner sequence. For the fold, our accumulator is a tuple, the first value being the number of bits to shift left by, the second being the accumulated value itself. Note that this results in a sequence of tuples where we only want the value from the second element, so we will need a `Seq.map snd`

to result in a sequence of the final values.

### Final Conversion

Finally the algorithm requires us to negate the overall value if the low order bit is set, then shift it right by one. Once this is done, we can convert to floating point and then make the value five orders of magnitude smaller to get the desired precision.

|> Seq.map (fun d -> if (d &&& 0x01) = 0x01 then ~~~(d>>>1) else (d>>>1)) |> Seq.map (fun d -> float(d) / 1e5)

### Making Tuples

What we now have is a sequence of alternating lattitude and longitude offsets – these should really be pairs. We need a way to convert a sequence in the form `[| a1; b1; a2; b2; a3; c3 |]`

into `[| (a1,b1); (a2,b2); (a3,b3) |]`

. Now I can’t find anything in the standard libraries for performing this action, but can’t help feeling there probably is something there already – if so, please call me an idiot and let me know in the comments! In the meantime, here is my `tuplise`

function:

let rec tuplise s = seq { if not (s |> Seq.isEmpty) then yield (s |> Seq.head),(s |> Seq.skip 1 |> Seq.head) yield! (s |> Seq.skip 2 |> tuplise) }

Note that this assumes the sequence has an even number of elements. If not, the `Seq.skip`

will fail. We can try this out now:

> [| 1; 1; 2; 2; 3; 3 |] |> tuplise;; val it : seq = seq [(1, 1); (2, 2); (3, 3)]

So with this function, we can now map the sequence of value pairs into a sequence of tuples.

|> tuplise

### Converting Coordinate offsets into Absolute Coordinates

The final stage in the conversion process could be left as an exercise for the reader, but I am feeling generous today! We need to iterate over the sequence, keeping a record at each step of the previous coordinate pairs, so that we can apply the offset values to those, giving us our absolute values:

let buildCoordPairs s = let rec innerBuildCoordPairs s (pla,plo) = seq { if notEmpty s then let (la,lo) = s |> Seq.head yield (pla+la,plo+lo) yield! innerBuildCoordPairs (s |> Seq.skip 1) (pla+la,plo+lo) } innerBuildCoordPairs s (0.0,0.0)

Now it is possible to build the complete `decodePolyline`

function and test that against our simple London Eye to Trafalgar Square route:

let decodePolyline (s:string) = s |> Seq.map (fun ch -> int(ch) - 63) |> splitSubSequences (fun d -> (d &&& 0x20) = 0x20) |> Seq.map (fun r -> r |> Seq.map (fun d -> d &&& 0x1F)) |> Seq.map (fun r -> r |> Seq.fold (fun (sh,tot) it -> (sh+5),(tot ||| (it<<<sh))) (0,0)) |> Seq.map snd |> Seq.map (fun d -> if (d &&& 0x01) = 0x01 then ~~~(d>>>1) else (d>>>1)) |> Seq.map (fun d -> float(d) / 1e5) |> tuplise |> buildCoordPairs > let s = "{ejyHriVuBa@oE{A]SWWMQADC?WSCB_FhUe@lBM`AFFEZE\\EjB{@zHkAhKOFMTCZAD";; val s : string = "{ejyHriVuBa@oE{A]SWWMQADC?WSCB_FhUe@lBM`AFFEZE\EjB{@zHkAhKOFMTCZAD" > s |> decodePolyline |> Array.ofSeq;; val it : (float * float) [] = [|(51.50318, -0.11946); (51.50377, -0.11929); (51.50481, -0.11883); (51.50496, -0.11873); (51.50508, -0.11861); (51.50515, -0.11852); (51.50516, -0.11855); (51.50518, -0.11855); (51.5053, -0.11845); (51.50532, -0.11847); (51.50644, -0.12204); (51.50663, -0.12259); (51.5067, -0.12292); (51.50666, -0.12296); (51.50669, -0.1231); (51.50672, -0.12325); (51.50675, -0.12379); (51.50705, -0.12537); (51.50743, -0.12734); (51.50751, -0.12738); (51.50758, -0.12749); (51.5076, -0.12763); (51.50761, -0.12766)|]

Again, converting to array so that we can see all the results in the interactive window. We can now copy & paste these values into google maps directions, just to confirm this route:

### Conclusion

I think this is a good example of how a purely functional style can quite neatly resolve an algorithm which tends to look pretty ugly in all the imperative implementations that I have seen.

*EDIT: full source code is available on fssnip. Also fixed sample data to ensure that the escape character is decoded, otherwise the sequence has mismatched pairs.*