{{ message }}

Instantly share code, notes, and snippets.

# signed0/gist:2031157

Created Mar 13, 2012
 '''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 commented May 7, 2012

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

### signed0 commented May 7, 2012

 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

### signed0 commented May 7, 2012

 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

### petergx commented May 7, 2012

 Got it. :-)

### irees commented May 15, 2014

 Thanks!!

### acedip commented May 31, 2015

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

### sujaybhowmick commented Sep 26, 2015

 Thanks very useful.

### 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 commented Dec 14, 2016 • edited

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