How to decode the Google Directions API polylines

Question

I want to draw routes on a map corresponding to directions JSON which I am getting through the Google Directions API: http://code.google.com/apis/maps/documentation/directions/

I have figured out how to extract the latitude and longitude from the steps field, however this doesn't follow curvy roads very well. I think what I need is to decode the polyline information, I found Googles instructions on how to encode polylines: http://code.google.com/apis/maps/documentation/utilities/polylinealgorithm.html

I did find some code here for Android and also Javascript on decoding the polylines, for example:

Map View draw directions using google Directions API - decoding polylines

android get and parse Google Directions

But I can't find same for Objective-C iPhone code, can anybody help me with this? I'm sure I can do it myself if I have to, but it sure would save me some time if it's already available somewhere...

EDIT: the key here is being able to decode the base64 encoding on a character by character basis. To be more specific, I get something like this in JSON from Google which is encoded using base64 encoding among other things:

...   "overview_polyline" : {
        "points" : "ydelDz~vpN_@NO@QEKWIYIIO?YCS@WFGBEBICCAE?G@y@RKBEBEBAD?HTpB@LALALCNEJEFSP_@LyDv@aB\\GBMB"
       },
...

Note: I should mention that this question refers to Google Maps API v1, it is much easier to do this in v2 using GMSPolyLine polyLineWithPath as many answers below will tell you (thanks to @cdescours).

Answer 1

If you are working with Google Map on iOS and want to draw the route including the polylines, google itself provides an easier way to get the GMSPath from polyline as,

GMSPath *pathFromPolyline = [GMSPath pathFromEncodedPath:polyLinePoints];

Here is the complete code:

+ (void)callGoogleServiceToGetRouteDataFromSource:(CLLocation *)sourceLocation toDestination:(CLLocation *)destinationLocation onMap:(GMSMapView *)mapView_{
    NSString *baseUrl = [NSString stringWithFormat:@"http://maps.googleapis.com/maps/api/directions/json?origin=%f,%f&destination=%f,%f&sensor=false", sourceLocation.coordinate.latitude,  sourceLocation.coordinate.longitude, destinationLocation.coordinate.latitude,  destinationLocation.coordinate.longitude];

    NSURL *url = [NSURL URLWithString:[baseUrl stringByAddingPercentEscapesUsingEncoding:NSUTF8StringEncoding]];

    NSLog(@"Url: %@", url);

    NSURLRequest *request = [NSURLRequest requestWithURL:url];

    [NSURLConnection sendAsynchronousRequest:request queue:[NSOperationQueue mainQueue] completionHandler:^(NSURLResponse *response, NSData *data, NSError *connectionError) {

        GMSMutablePath *path = [GMSMutablePath path];

        NSError *error = nil;
        NSDictionary *result = [NSJSONSerialization JSONObjectWithData:data options:0 error:&error];

        NSArray *routes = [result objectForKey:@"routes"];

        NSDictionary *firstRoute = [routes objectAtIndex:0];

        NSDictionary *leg =  [[firstRoute objectForKey:@"legs"] objectAtIndex:0];

        NSArray *steps = [leg objectForKey:@"steps"];

        int stepIndex = 0;

        CLLocationCoordinate2D stepCoordinates[1  + [steps count] + 1];

        for (NSDictionary *step in steps) {

            NSDictionary *start_location = [step objectForKey:@"start_location"];
            stepCoordinates[++stepIndex] = [self coordinateWithLocation:start_location];
            [path addCoordinate:[self coordinateWithLocation:start_location]];

            NSString *polyLinePoints = [[step objectForKey:@"polyline"] objectForKey:@"points"];
            GMSPath *polyLinePath = [GMSPath pathFromEncodedPath:polyLinePoints];
            for (int p=0; p<polyLinePath.count; p++) {
                [path addCoordinate:[polyLinePath coordinateAtIndex:p]];
            }


            if ([steps count] == stepIndex){
                NSDictionary *end_location = [step objectForKey:@"end_location"];
                stepCoordinates[++stepIndex] = [self coordinateWithLocation:end_location];
                [path addCoordinate:[self coordinateWithLocation:end_location]];
            }
        }

        GMSPolyline *polyline = nil;
        polyline = [GMSPolyline polylineWithPath:path];
        polyline.strokeColor = [UIColor grayColor];
        polyline.strokeWidth = 3.f;
        polyline.map = mapView_;
    }];
}

+ (CLLocationCoordinate2D)coordinateWithLocation:(NSDictionary*)location
{
    double latitude = [[location objectForKey:@"lat"] doubleValue];
    double longitude = [[location objectForKey:@"lng"] doubleValue];

    return CLLocationCoordinate2DMake(latitude, longitude);
}

Answer 2

The best and lightest answer should be to use the method provided by Google in the framework :

[GMSPolyline polylineWithPath:[GMSPath pathFromEncodedPath:encodedPath]]

Answer 3

The other answers here seem to be about using Apple Maps, for using Google Maps I found I had to make some modifications to @SedateAlien's great category.

MODIFIED CATEGORY

+ (GMSPolyline *)polylineWithEncodedString:(NSString *)encodedString {
    const char *bytes = [encodedString UTF8String];
    NSUInteger length = [encodedString lengthOfBytesUsingEncoding:NSUTF8StringEncoding];
    NSUInteger idx = 0;

    NSUInteger count = length / 4;
    CLLocationCoordinate2D *coords = calloc(count, sizeof(CLLocationCoordinate2D));
    NSUInteger coordIdx = 0;

    float latitude = 0;
    float longitude = 0;
    while (idx < length) {
        char byte = 0;
        int res = 0;
        char shift = 0;

        do {
            byte = bytes[idx++] - 63;
            res |= (byte & 0x1F) << shift;
            shift += 5;
        } while (byte >= 0x20);

        float deltaLat = ((res & 1) ? ~(res >> 1) : (res >> 1));
        latitude += deltaLat;

        shift = 0;
        res = 0;

        do {
            byte = bytes[idx++] - 0x3F;
            res |= (byte & 0x1F) << shift;
            shift += 5;
        } while (byte >= 0x20);

        float deltaLon = ((res & 1) ? ~(res >> 1) : (res >> 1));
        longitude += deltaLon;

        float finalLat = latitude * 1E-5;
        float finalLon = longitude * 1E-5;

        CLLocationCoordinate2D coord = CLLocationCoordinate2DMake(finalLat, finalLon);
        coords[coordIdx++] = coord;

        if (coordIdx == count) {
            NSUInteger newCount = count + 10;
            coords = realloc(coords, newCount * sizeof(CLLocationCoordinate2D));
            count = newCount;
        }
    }

    GMSMutablePath *path = [[GMSMutablePath alloc] init];

    int i;
    for (i = 0; i < coordIdx; i++)
    {
        [path addCoordinate:coords[i]];
    }

    GMSPolyline *polyline = [GMSPolyline polylineWithPath:path];
    free(coords);

    return polyline;
}

USAGE

// Here I make the call to the Google Maps API to get the routes between two points...

....

// Get the encoded array of points.
NSString *points = routes[@"routes"][0][@"overview_polyline"][@"points"];

// Use the modified category to get a polyline from the points.
GMSPolyline *polyline = [GMSPolyline polylineWithEncodedString:points];

// Add the polyline to the map.
polyline.strokeColor = [UIColor redColor];
polyline.strokeWidth = 10.f;
polyline.map = theMapView;
}

Answer 4

Python Implementation

This isn't in Objective-C, but this thread is where Google drops you if you're looking to decode polyline strings from Google Maps. In case anyone else needs it (much like I did), here's a Python implementation for decoding polyline strings. This is ported from the Mapbox JavaScript version; more info found on my repo page.

def decode_polyline(polyline_str):
    index, lat, lng = 0, 0, 0
    coordinates = []
    changes = {'latitude': 0, 'longitude': 0}

    # Coordinates have variable length when encoded, so just keep
    # track of whether we've hit the end of the string. In each
    # while loop iteration, a single coordinate is decoded.
    while index < len(polyline_str):
        # Gather lat/lon changes, store them in a dictionary to apply them later
        for unit in ['latitude', 'longitude']: 
            shift, result = 0, 0

            while True:
                byte = ord(polyline_str[index]) - 63
                index+=1
                result |= (byte & 0x1f) << shift
                shift += 5
                if not byte >= 0x20:
                    break

            if (result & 1):
                changes[unit] = ~(result >> 1)
            else:
                changes[unit] = (result >> 1)

        lat += changes['latitude']
        lng += changes['longitude']

        coordinates.append((lat / 100000.0, lng / 100000.0))

    return coordinates

Answer 5

If anybody else is trying to do this in swift, here's @RootCode's answer adapted to swift (2.3):

let path = GMSMutablePath()
let steps = directionsToShowOnMap.steps
for (idx, step) in steps.enumerate() {
    path.addCoordinate(coordinateFromJson(step["start_location"]))
    if let polylinePoints = step["polyline"].string, subpath = GMSPath(fromEncodedPath: polylinePoints) {
        for c in 0 ..< subpath.count() {
            path.addCoordinate(subpath.coordinateAtIndex(c))
        }   
    }
    if idx == steps.count - 1 {
        path.addCoordinate(coordinateFromJson(step["end_location"]))
    }
}
let polyline = GMSPolyline(path: path)
polyline.strokeColor = UIColor.blueColor()
polyline.strokeWidth = 3
polyline.map = mapView

and then:

private func coordinateFromJson(location: JSON) -> CLLocationCoordinate2D {
    return CLLocationCoordinate2DMake(location["lat"].double!, location["lng"].double!)
}

Answer 6

I hope it's not against the rules to link to my own blog post if it's relevant to the question, but I've solved this problem in the past. Stand-alone answer from linked post:

@implementation MKPolyline (MKPolyline_EncodedString)

+ (MKPolyline *)polylineWithEncodedString:(NSString *)encodedString {
    const char *bytes = [encodedString UTF8String];
    NSUInteger length = [encodedString lengthOfBytesUsingEncoding:NSUTF8StringEncoding];
    NSUInteger idx = 0;

    NSUInteger count = length / 4;
    CLLocationCoordinate2D *coords = calloc(count, sizeof(CLLocationCoordinate2D));
    NSUInteger coordIdx = 0;

    float latitude = 0;
    float longitude = 0;
    while (idx < length) {
        char byte = 0;
        int res = 0;
        char shift = 0;

        do {
            byte = bytes[idx++] - 63;
            res |= (byte & 0x1F) << shift;
            shift += 5;
        } while (byte >= 0x20);

        float deltaLat = ((res & 1) ? ~(res >> 1) : (res >> 1));
        latitude += deltaLat;

        shift = 0;
        res = 0;

        do {
            byte = bytes[idx++] - 0x3F;
            res |= (byte & 0x1F) << shift;
            shift += 5;
        } while (byte >= 0x20);

        float deltaLon = ((res & 1) ? ~(res >> 1) : (res >> 1));
        longitude += deltaLon;

        float finalLat = latitude * 1E-5;
        float finalLon = longitude * 1E-5;

        CLLocationCoordinate2D coord = CLLocationCoordinate2DMake(finalLat, finalLon);
        coords[coordIdx++] = coord;

        if (coordIdx == count) {
            NSUInteger newCount = count + 10;
            coords = realloc(coords, newCount * sizeof(CLLocationCoordinate2D));
            count = newCount;
        }
    }

    MKPolyline *polyline = [MKPolyline polylineWithCoordinates:coords count:coordIdx];
    free(coords);

    return polyline;
}

@end