Google Maps API - decoding polylines for drawing routes

What happens when ggplot2 and GoogleMaps have babies?
Answer: the ggmap package, by David Kahle and Hadley Wickam.

A few weeks ago, the mapdist function in the above package happened to be very useful to me at work.
The magic it does is calculating distances between locations. And you can specify if you want the driving, walking or bicycling distance.

You know what happens when you show people a cat who can sing? They say "well, but he can't play the piano!"
That's me. In fact I wondered why there was no option for distance using public transit.

I looked at Google API documentation and got all the info I needed. It's just a matter of building the right URL and you get a JSON file that is easily read by R.

The JSON contains all one would look for, including distance and time required to cover it for all legs.
But my attention was caught by lines that looked like this:

[1] "es~mGe|scAEXpCBbHHtAE|ATpFnB`DjA~B~@tDlAbBh@p@R^F\\??HBNDLJJPBLCLIDKDQ?UEQAEPEhBk@bI}CRG@BB@HDJ?JEHKFM?GbAc@`DqAfA]xBo@dAKh@KfA]xAu@pA_AzAo@\\Mj@[XQrAkAxAwAzAiAf@St@Wl@ENER?n@?d@Fr@RlAp@h@LN?\\G`@[lAiA|@cAf@o@v@o@^SlBg@v@O^AZCn@?j@F`ATdAd@n@T^@f@Al@IvASvAc@jCwAv@W|Bi@f@QhAq@n@k@X_@Zq@xAaF|@mChAqCpCgHRi@Lm@Jm@PcAJ[h@e@rGgC\\KJ@f@FXLh@\\Zl@JRAB?F?LDP@DDDHFH@JAHEFKDM@OAQEMCC?g@Jm@tAkCdAqA\\WpCyA`Ay@Z_@Zc@TMtA[hEs@n@Kh@SbBmAfAUpGZhBBp@AVEbAa@dHyCjB}@nCqAfKyDnCoAlA_@|A_@~AWnAe@pAy@^U`Be@xGmAnBWbFc@pDSfJo@tIm@fBCnBDjBTzBj@bBn@d@JbANlCGpB]vAa@dAe@lBw@xAk@fA]^Gn@IfDKpBUhJuB~AG`A@lBHr@NRJn@^p@v@T\\x@jBfCnGh@~ApAtC`ChFtDrK\\z@n@t@h@h@f@VdAXnAD~BBjCL|@LpBv@zAx@nAkCENoEoBmDiBaC}AcBuAk@k@eAiA{AqBeR_]umG_aLqC_C_D}ByBuAmBcAyDiBgCaAeDeAaB_@iB[{BUsEQcFBmDP{r@bGsDTqA@cCKmC]iCs@iBs@mAo@a|Au}@cEmBsAi@yC_AcGmAaCYmCSoCIcC?cEL}V|AsBFoCGcD_@{\\yFcBQ_x@}EkBQgB[iAYcC_AwAu@iAu@}b@{\\uCcC{BwBwB_Cwb@gg@qC}CeDwCsD_CaCeAgBm@o^wJmh@kNoCm@{Bc@iG}@sIq@mGQ_NFyoAfBqDJoBRsB`@o@PgC`AqBdA_BfAsAhAwAvAiAvAkBrCmBxDw@pBeAfDmOlg@sFnPgQtl@_@bBq@rDwA`Kw@hGu@`Hs@tHgAdPg@bDJBdBsBB@tAVLBBc@ZkDf@}EZ_DjBf@HHF@^H^P~@X|B`@xHzAxFpAtDp@`HrA~GrA~FbA"

Created by Pretty R at inside-R.org

Again, it's all explained in Google API's documentation. All those funny looking characters are the coordinates of the route after going through an encoder.
I promptly found online some decoding functions written in Javascript (I can't retrieve the links anymore, so apologies to the authors for not crediting them—I'll try to make up for this,) and rolled up my sleeves to translate them in R.

Here's the decoding function I have come up with:

decodeLine <- function(encoded){
  require(bitops)
 
  vlen <- nchar(encoded)
  vindex <- 0
  varray <- NULL
  vlat <- 0
  vlng <- 0
 
  while(vindex < vlen){
    vb <- NULL
    vshift <- 0
    vresult <- 0
    repeat{
      if(vindex + 1 <= vlen){
        vindex <- vindex + 1
        vb <- as.integer(charToRaw(substr(encoded, vindex, vindex))) - 63  
      }
 
      vresult <- bitOr(vresult, bitShiftL(bitAnd(vb, 31), vshift))
      vshift <- vshift + 5
      if(vb < 32) break
    }
 
    dlat <- ifelse(
      bitAnd(vresult, 1)
      , -(bitShiftR(vresult, 1)+1)
      , bitShiftR(vresult, 1)
    )
    vlat <- vlat + dlat
 
    vshift <- 0
    vresult <- 0
    repeat{
      if(vindex + 1 <= vlen) {
        vindex <- vindex+1
        vb <- as.integer(charToRaw(substr(encoded, vindex, vindex))) - 63        
      }
 
      vresult <- bitOr(vresult, bitShiftL(bitAnd(vb, 31), vshift))
      vshift <- vshift + 5
      if(vb < 32) break
    }
 
    dlng <- ifelse(
      bitAnd(vresult, 1)
      , -(bitShiftR(vresult, 1)+1)
      , bitShiftR(vresult, 1)
    )
    vlng <- vlng + dlng
 
    varray <- rbind(varray, c(vlat * 1e-5, vlng * 1e-5))
  }
  coords <- data.frame(varray)
  names(coords) <- c("lat", "lon")
  coords
}

Created by Pretty R at inside-R.org




I tested the decodeLine function on my home-to-work route.

# set the origin, destination and travel mode
# if travel mode is "transit" you need to specify a departure (or arrival) time
origin <- "Sasso Marconi, Italy"
destination <- "Bologna, Italy"
travelMode <- "transit"
departureTime <- Sys.time() #I want to leave now!
 
# build the URL
baseUrl <- "http://maps.googleapis.com/maps/api/directions/json?"
origin <- gsub(" ", "+", origin)
destination <- gsub(" ", "+", destination)
finalUrl <- paste(baseUrl
                  , "origin=", origin
                  , "&destination=", destination
                  , "&sensor=false"
                  , "&mode=", travelMode
                  , "&departure_time=", as.integer(departureTime)
                  , sep = "")
 
# get the JSON returned by Google and convert it to an R list
url_string <- URLencode(finalUrl)
trip <- fromJSON(paste(readLines(url_string), collapse = ""))
 
# get the encoded coordinates for the full trip
tripPathEncoded <- trip$routes[[1]]$overview_polyline$points
tripPathEncoded
 
[1] "es~mGe|scAEXpCBbHHtAE|ATpFnB`DjA~B~@tDlAbBh@p@R^F\\??HBNDLJJPBLCLIDKDQ?UEQAEPEhBk@bI}CRG@BB@HDJ?JEHKFM?GbAc@`DqAfA]xBo@dAKh@KfA]xAu@pA_AzAo@\\Mj@[XQrAkAxAwAzAiAf@St@Wl@ENER?n@?d@Fr@RlAp@h@LN?\\G`@[lAiA|@cAf@o@v@o@^SlBg@v@O^AZCn@?j@F`ATdAd@n@T^@f@Al@IvASvAc@jCwAv@W|Bi@f@QhAq@n@k@X_@Zq@xAaF|@mChAqCpCgHRi@Lm@Jm@PcAJ[h@e@rGgC\\KJ@f@FXLh@\\Zl@JRAB?F?LDP@DDDHFH@JAHEFKDM@OAQEMCC?g@Jm@tAkCdAqA\\WpCyA`Ay@Z_@Zc@TMtA[hEs@n@Kh@SbBmAfAUpGZhBBp@AVEbAa@dHyCjB}@nCqAfKyDnCoAlA_@|A_@~AWnAe@pAy@^U`Be@xGmAnBWbFc@pDSfJo@tIm@fBCnBDjBTzBj@bBn@d@JbANlCGpB]vAa@dAe@lBw@xAk@fA]^Gn@IfDKpBUhJuB~AG`A@lBHr@NRJn@^p@v@T\\x@jBfCnGh@~ApAtC`ChFtDrK\\z@n@t@h@h@f@VdAXnAD~BBjCL|@LpBv@zAx@nAkCENoEoBmDiBaC}AcBuAk@k@eAiA{AqBeR_]umG_aLqC_C_D}ByBuAmBcAyDiBgCaAeDeAaB_@iB[{BUsEQcFBmDP{r@bGsDTqA@cCKmC]iCs@iBs@mAo@a|Au}@cEmBsAi@yC_AcGmAaCYmCSoCIcC?cEL}V|AsBFoCGcD_@{\\yFcBQ_x@}EkBQgB[iAYcC_AwAu@iAu@}b@{\\uCcC{BwBwB_Cwb@gg@qC}CeDwCsD_CaCeAgBm@o^wJmh@kNoCm@{Bc@iG}@sIq@mGQ_NFyoAfBqDJoBRsB`@o@PgC`AqBdA_BfAsAhAwAvAiAvAkBrCmBxDw@pBeAfDmOlg@sFnPgQtl@_@bBq@rDwA`Kw@hGu@`Hs@tHgAdPg@bDJBdBsBB@tAVLBBc@ZkDf@}EZ_DjBf@HHF@^H^P~@X|B`@xHzAxFpAtDp@`HrA~GrA~FbA"
 
 
# decode the encoded coordinates
tripPathCoords <- decodeLine(tripPathEncoded)
head(tripPathCoords)
 
       lat      lon
1 44.39875 11.24819
2 44.39878 11.24806
3 44.39805 11.24804
4 44.39659 11.24799
5 44.39616 11.24802
6 44.39569 11.24791
 
# draw a map
library(ggmap)
map <- get_map(location = "Bologna, Italy")
ggmap(map) +
  geom_path(aes(lon, lat), data=tripPathCoords, lwd = 2)

Created by Pretty R at inside-R.org

Here it is! Actually I take a shorter path when I commute, but the one shown here is not a fault of the decodeLine function—for some reason the train line I use is not available on GoogleMaps (despite it's run by the same company running the displayed one!)

While writing this post, I discovered someone else had already invented this wheel, so you can use Diego Valle's code if you prefer.