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 |
This comment has been minimized.
This comment has been minimized.
I don't think so. X is always longitude, Y is latitude.
…On May 7, 2012 7:25 PM, "petergitz" < ***@***.***> wrote:
Hey, I think x and y are swapped on line 24.
---
Reply to this email directly or view it on GitHub:
https://gist.github.com/2031157
|
This comment has been minimized.
This comment has been minimized.
Ahh, I think my comment is wrong. The function expects an iterable of x,y
coords (longitude, latitude).
On May 7, 2012 7:32 PM, "Nathan Villaescusa" nathan.villaescusa@gmail.com
wrote:
… I don't think so. X is always longitude, Y is latitude.
On May 7, 2012 7:25 PM, "petergitz" <
***@***.***>
wrote:
> Hey, I think x and y are swapped on line 24.
> ---
>
> Reply to this email directly or view it on GitHub:
> https://gist.github.com/2031157
|
This comment has been minimized.
This comment has been minimized.
petergx
commented
May 7, 2012
Got it. :-) |
This comment has been minimized.
This comment has been minimized.
irees
commented
May 15, 2014
Thanks!! |
This comment has been minimized.
This comment has been minimized.
acedip
commented
May 31, 2015
Hey, the output of decode is longitude,latitude and not latitude,longitude |
This comment has been minimized.
This comment has been minimized.
sujaybhowmick
commented
Sep 26, 2015
Thanks very useful. |
This comment has been minimized.
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. |
This comment has been minimized.
This comment has been minimized.
rushiagr
commented
Dec 14, 2016
•
Could use |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This comment has been minimized.
petergx commentedMay 7, 2012
Hey, I think x and y are swapped on line 24.