1 people like it.

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:10 years ago
Author:Chris Ballard
Tags: google , api , polyline , decode , sequence , bit shifting