Decoder for Google API polylines

Full source code for my blog entry on this subject - http://chrsb.co/BNqAbM

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
55: 
56: 
57: 
58: 
59: 
60: 
61:

// just to keep things tidy
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)
    }

// take a sequence in the form a1;b1;a2;b2;a3;b3 and make sequence
// of tuples (a1,b1);(a2,b2)...
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)
  }

// convert a list of relative coordinate pairs into absolute coordinates
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)

// take a google encoded polyline and decode to a sequence of absolute
// coordinate (lat,long) pairs
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

val notEmpty : s:seq<'a> -> bool

Full name: Script.notEmpty

val s : seq<'a>

val not : value:bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not

module Seq

from Microsoft.FSharp.Collections

val isEmpty : source:seq<'T> -> bool

Full name: Microsoft.FSharp.Collections.Seq.isEmpty

val takeWhileInc : cond:('a -> bool) -> s:seq<'a> -> seq<'a>

Full name: Script.takeWhileInc

val cond : ('a -> bool)

Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>

val takeWhile : predicate:('T -> bool) -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.takeWhile

val r : seq<'a>

val skipWhile : predicate:('T -> bool) -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.skipWhile

val head : source:seq<'T> -> 'T

Full name: Microsoft.FSharp.Collections.Seq.head

val skipWhileInc : cond:('a -> bool) -> s:seq<'a> -> seq<'a>

Full name: Script.skipWhileInc

val skip : count:int -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.skip

val splitSubSequences : cond:('a -> bool) -> s:seq<'a> -> seq<seq<'a>>

Full name: Script.splitSubSequences

val tuplise : s:seq<'a> -> seq<'a * 'a>

Full name: Script.tuplise

val buildCoordPairs : s:seq<float * float> -> seq<float * float>

Full name: Script.buildCoordPairs

val s : seq<float * float>

val innerBuildCoordPairs : (seq<float * float> -> float * float -> seq<float * float>)

val pla : float

val plo : float

val la : float

val lo : float

val decodePolyline : s:string -> seq<float * float>

Full name: Script.decodePolyline

val s : string

Multiple items
val string : value:'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

--------------------
type string = System.String

Full name: Microsoft.FSharp.Core.string

val map : mapping:('T -> 'U) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map

val ch : char

Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>

val d : int

val r : seq<int>

val fold : folder:('State -> 'T -> 'State) -> state:'State -> source:seq<'T> -> 'State

Full name: Microsoft.FSharp.Collections.Seq.fold

val sh : int32

val tot : int

val it : int

val snd : tuple:('T1 * 'T2) -> 'T2

Full name: Microsoft.FSharp.Core.Operators.snd

Multiple items
val float : value:'T -> float (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.float

--------------------
type float = System.Double

Full name: Microsoft.FSharp.Core.float

--------------------
type float<'Measure> = float

Full name: Microsoft.FSharp.Core.float<_>

Raw view Test code New version

More information

Link:	http://fssnip.net/na
Posted:	9 years ago
Author:	Chris Ballard
Tags:	google , api , polyline , decode , sequence , bit shifting