Google Maps Polyline

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# Author: Claudio Polegato Junior
# Date..: 18/Nov/2012
# E-mail: linux.at.juniorpolegato.com.br
# File..: gmaps_polyline.py
# Descr.: Encode and decode latitude, longitude, level and polyline

def gm_encode(number, encode_level = False):
    ('Encode number for polyline in Google Maps. To encode level, just'
     'skip the 6 first steps. From: https://developers.google.com/maps'
     '/documentation/utilities/polylinealgorithm')
    if not encode_level:
        # Take the initial signed value: number
        #-179.9832104
        # Take the decimal value and multiply it by 1e5,
        #rounding the result:
        number = int(round(number * 1e5))
        #Convert the decimal value to binary. Note that a negative
        #value must be calculated using its two's complement
        #by inverting the binary value and adding one to the result:
        #00000001 00010010 10100001 11110001
        #11111110 11101101 01011110 00001110
        #11111110 11101101 01011110 00001111
        if number < 0:
            number = -number - (1 << 32)
        #Left-shift the binary value one bit:
        #11111101 11011010 10111100 00011110
        number = number << 1
    #If the original decimal value is negative, invert this encoding:
    #00000010 00100101 01000011 11100001
    if number < 0:
        # exclude -0b and change 0 and 1
        binary = bin(number)[3:].replace('0', '\0').replace('1', '0').\
                                                      replace('\0', '1')
        # get 32 lowest bits completing with 1 at right
        # can be 30 bits, because we will use just 30, but...
        binary = ('1' * 31 + binary)[-32:]
    else:
        # exclude 0b
        binary = bin(number)[2:]
        # get 32 lowest bits completing with 0 at right
        # can be 30 bits, because we will use just 30, but...
        binary = ('0' * 31 + binary)[-32:]
    #Break the binary value out into 5-bit chunks
    #(starting from the right hand side):
    #00001 00010 01010 10000 11111 00001
    #Place the 5-bit chunks into reverse order:
    #00001 11111 10000 01010 00010 00001
    chunks = [binary[i - 5:i] for i in range(32, 2, -5)]
    #-----------> The step to exclude '00000' from the end was forgotten
    while chunks[-1] == '00000':
        chunks.pop()
    #OR each value with 0x20 if another bit chunk follows:
    #100001 111111 110000 101010 100010 000001
    chunks = ['1' + c for c in chunks[:-1]] + [chunks[-1]]
    #Convert each value to decimal:
    #33 63 48 42 34 1
    #Add 63 to each value:
    #96 126 111 105 97 64
    #Convert each value to its ASCII equivalent:
    #`~oia@
    return ''.join([chr(int(c, 2) + 63) for c in chunks])

def gm_decode(encoded_number, decode_level = False):
    # reverse return above
    chunks = [bin(ord(c) - 63)[2:] for c in encoded_number]
    # remove the marks '1' from chunks, except the last
    chunks = [chunk[1:] for chunk in chunks[:-1]] + [chunks[-1]]
    # restore binary bits join chunks of a value in reverse order
    binary = ''.join(chunks[::-1])
    if not decode_level:
        # if the lowest bit is 1, then the number is negative, so we
        # need to do the complement, ignoring the lowest bit
        if binary[-1] == '1':
            number = -(int(binary, 2) >> 1) - 1
        else:
            # get the number casting binary ignoring the lowest bit
            number = int(binary, 2) >> 1
        # divide the number by 1e5
        number /= 1e5
    else:
        # when in decode_level, just cast binary to int
        number = int(binary, 2)
    return number

def gm_encode_polyline(polyline, print_table = False):
    if print_table:
        print ('\n|  Latitude| Longitude|Change In Latitude|Change In'
               ' Longitude|Encoded Latitude|Encoded Longitude|Encoded'
               ' Point|')
    last = (0, 0)
    encoded_polyline = ''
    for latitude, longitude in polyline:
        # calcule the distance from the last point
        point = (latitude - last[0], longitude - last[1])
        # last point is this point now
        last = (latitude, longitude)
        # encode the distance
        encoded = (gm_encode(point[0]), gm_encode(point[1]))
        if print_table:
            print '|%10.5f|%10.5f|%18.5f|%19.5f|%16s|%17s|%13s|' % (
                    latitude, longitude, point[0], point[1],
                    encoded[0], encoded[1], ''.join(encoded))
        # join the encoded values with encoded_polyline
        encoded_polyline += ''.join(encoded)
    return encoded_polyline

def gm_decode_polyline(encoded_polyline):
    polyline = []
    latitude = None
    # split the encoded_polyline where the ord - 63 of last caracter is
    # less than 0x20, this is the marks in gm_encode for the last one
    splits = [c for c in encoded_polyline if ord(c) - 63 < 0x20]
    for c in splits:
        # get the encoded value and rest of encoded_polyline
        value, encoded_polyline = encoded_polyline.split(c, 1)
        # decode the value
        value = gm_decode(value + c)
        # if latitude is none, then this value is the latitude
        if latitude is None:
            latitude = value
        # else, if we had have latitude, this value is the longitude
        # now we have a point
        else:
            # if we have a point in polyline, this point is the
            # distance, then we plus this point with the last
            if polyline:
                last = polyline[-1]
                polyline.append((last[0] + latitude, last[1] + value))
            # else, this is the first point
            else:
                polyline.append((latitude, value))
            # latitude is none to get a new latitude
            latitude = None
    # return polyline like a tuple
    return tuple(polyline)

print '\nTeste if encode of -179.9832104 is "`~oia@"...'
print "Great! Excelente!" if gm_encode(-179.9832104) == "`~oia@"\
                                           else "Oh no, theres a error!"

print '\nTeste if decode of "`~oia@" is -179.98321...'
print "Great! Excelente!" if gm_decode("`~oia@") == -179.98321\
                                           else "Oh no, theres a error!"

print '\nTeste if encode of level 174 is "mD"...'
print "Great! Excelente!" if gm_encode(174, True) == "mD"\
                                           else "Oh no, theres a error!"

print '\nTeste if decode of level "mD" is 174...'
print "Great! Excelente!" if gm_decode("mD", True) == 174\
                                           else "Oh no, theres a error!"

polyline = ((38.5, -120.2), (40.7, -120.95), (43.252, -126.453))
encoded_polyline = gm_encode_polyline(polyline, True)

print "\nEncoded Polyline:", encoded_polyline
print "Great! Excelente!" if encoded_polyline ==\
             "_p~iF~ps|U_ulLnnqC_mqNvxq`@" else "Oh no, theres a error!"

print ('\nTeste if decode of decode of polyline '
           '"_p~iF~ps|U_ulLnnqC_mqNvxq`@" is ' + repr(polyline) + '...')
print "Great! Excelente!" if gm_decode_polyline(
                             "_p~iF~ps|U_ulLnnqC_mqNvxq`@") == polyline\
                                           else "Oh no, theres a error!"