Instantly share code, notes, and snippets.

Embed
What would you like to do?
Google Polyline encoder & decoder
'''Provides utility functions for encoding and decoding linestrings using the
Google encoded polyline algorithm.
'''
def encode_coords(coords):
'''Encodes a polyline using Google's polyline algorithm
See http://code.google.com/apis/maps/documentation/polylinealgorithm.html
for more information.
:param coords: Coordinates to transform (list of tuples in order: latitude,
longitude).
:type coords: list
:returns: Google-encoded polyline string.
:rtype: string
'''
result = []
prev_lat = 0
prev_lng = 0
for x, y in coords:
lat, lng = int(y * 1e5), int(x * 1e5)
d_lat = _encode_value(lat - prev_lat)
d_lng = _encode_value(lng - prev_lng)
prev_lat, prev_lng = lat, lng
result.append(d_lat)
result.append(d_lng)
return ''.join(c for r in result for c in r)
def _split_into_chunks(value):
while value >= 32: #2^5, while there are at least 5 bits
# first & with 2^5-1, zeros out all the bits other than the first five
# then OR with 0x20 if another bit chunk follows
yield (value & 31) | 0x20
value >>= 5
yield value
def _encode_value(value):
# Step 2 & 4
value = ~(value << 1) if value < 0 else (value << 1)
# Step 5 - 8
chunks = _split_into_chunks(value)
# Step 9-10
return (chr(chunk + 63) for chunk in chunks)
def decode(point_str):
'''Decodes a polyline that has been encoded using Google's algorithm
http://code.google.com/apis/maps/documentation/polylinealgorithm.html
This is a generic method that returns a list of (latitude, longitude)
tuples.
:param point_str: Encoded polyline string.
:type point_str: string
:returns: List of 2-tuples where each tuple is (latitude, longitude)
:rtype: list
'''
# sone coordinate offset is represented by 4 to 5 binary chunks
coord_chunks = [[]]
for char in point_str:
# convert each character to decimal from ascii
value = ord(char) - 63
# values that have a chunk following have an extra 1 on the left
split_after = not (value & 0x20)
value &= 0x1F
coord_chunks[-1].append(value)
if split_after:
coord_chunks.append([])
del coord_chunks[-1]
coords = []
for coord_chunk in coord_chunks:
coord = 0
for i, chunk in enumerate(coord_chunk):
coord |= chunk << (i * 5)
#there is a 1 on the right if the coord is negative
if coord & 0x1:
coord = ~coord #invert
coord >>= 1
coord /= 100000.0
coords.append(coord)
# convert the 1 dimensional list to a 2 dimensional list and offsets to
# actual values
points = []
prev_x = 0
prev_y = 0
for i in xrange(0, len(coords) - 1, 2):
if coords[i] == 0 and coords[i + 1] == 0:
continue
prev_x += coords[i + 1]
prev_y += coords[i]
# a round to 6 digits ensures that the floats are the same as when
# they were encoded
points.append((round(prev_x, 6), round(prev_y, 6)))
return points
@petergx

This comment has been minimized.

petergx commented May 7, 2012

Hey, I think x and y are swapped on line 24.

@signed0

This comment has been minimized.

Owner

signed0 commented May 7, 2012

@signed0

This comment has been minimized.

Owner

signed0 commented May 7, 2012

@petergx

This comment has been minimized.

petergx commented May 7, 2012

Got it. :-)

@irees

This comment has been minimized.

irees commented May 15, 2014

Thanks!!

@acedip

This comment has been minimized.

acedip commented May 31, 2015

Hey, the output of decode is longitude,latitude and not latitude,longitude

@sujaybhowmick

This comment has been minimized.

sujaybhowmick commented Sep 26, 2015

Thanks very useful.

@cywiz34

This comment has been minimized.

cywiz34 commented Aug 12, 2016

Is there any regularity in the decode function output. As in , does it give the co-ordinates at regular intervals on a given route.

@rushiagr

This comment has been minimized.

rushiagr commented Dec 14, 2016

Could use range instead of xrange, and the code is Python 3 compatible. Many thanks regardless :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment