Google GPolyline Decode in C#

I started playing with the Google Maps GPolyline format and discovered that there are many implementations in many languages that allow you to Encode a GPolyline, but very few to Decode a GPolyline. The most common implementations that can be found were written in dynamic languages like JavaScript or Python. I am currently working in C#/Silverlight and found very few examples. The challenge is how to use data formatted for Google Maps in Bing Maps?
 
So I decided to write my own decoder. Because I was interested in understanding the algorithm and not trying to minimize code size or maximally optimize performance, you will see that the methods are rather verbose. But a good compiler should be able to optimize it enough to get decent performance.
 
The Encode algorithm is defined at  http://code.google.com/apis/maps/documentation/polylinealgorithm.html as a sequence steps needed to present a list of latitudes and longitudes into a string to be used by Google Maps. So you will see that my comments are these steps presented in reverse order.
 
There are two methods, the first is the generic algorithm to convert a GPolyline string into a Collection of floating point numbers. Although typically used for pairs of lattitude and longitude, there is strictly no requirement that there be an even number of values. The second method is simply a wrapper to pair up the floating point numbers into a Collection of Bing Maps Locations (LocationCollection). You will note that it is passed an existing Collection, I did this because I wanted to merge a number of GPolyline strings into a single Collection without extra copies.
 
I hope you enjoy this and find it useful.
    -David
 

//
// Copyright 2010 David Robinson  All Rights Reserved
//
// Redistribution and use in source and binary forms, with or
// without modification, are permitted provided that any
// reedistributions of source code must retain the above
// copyright notice and this condition.
//

using System;
using System.Collections.ObjectModel;
using System.Text;
using Microsoft.Maps.MapControl;

namespace DaRobins
{
    /// <summary>
    /// Utility class to manipulate Google Encoded GPolylines
    /// </summary>
    public class GPolyline
    {
        /// <summary>
        /// No constructor
        /// </summary>
        private GPolyline() { }

        /// <summary>
        /// Decode a Google Encoded GPolyline
        /// </summary>
        /// <remarks>
        /// The Google Encoded GPolyline specification is defined
        /// at http://code.google.com/apis/maps/documentation/polylinealgorithm.html
        /// </remarks>
        /// <param name="gPolyString">Encoded GPolyline</param>
        /// <returns>Ordered list of floating point numbers</returns>
        /// <exception cref="System.ArgumentOutOfRangeException">Thrown when the GPolyline has a malformed byte</exception>
        public static Collection<double> DecodeGPolyline(string gPolyString)
        {
            const int MaxGPolyChunks = 7;
            var GPolyElementList = new Collection<double>();

            //
            // Step 11: Convert the GPolyline string back into an array of chunks
            //

            var GPolyBytes = Encoding.UTF8.GetBytes(gPolyString);

            //
            // Walk through the array of chunks splitting it into a list of elements
            //

            var TempChunk = new byte[MaxGPolyChunks];
            int TempChunkIndex = 0;

            for (int i = 0; i < GPolyBytes.Length; i++)
            {
                //
                // A element cannot have more than 7 chunks
                //

                if (TempChunkIndex >= MaxGPolyChunks)
                    throw new ArgumentOutOfRangeException();

                //
                // Step 10 & 9: Chunks are ASCII "base" 63 values
                //

                if (GPolyBytes[i] < 63)
                    throw new ArgumentOutOfRangeException();

                TempChunk[TempChunkIndex] = (byte)(GPolyBytes[i] - 63);

                //
                // A chunk is a 6 bit value: 5 bits data with an upper continuation bit
                //

                if ((TempChunk[TempChunkIndex] & 0xC0) != 0)
                    throw new ArgumentOutOfRangeException();

                if ((TempChunk[TempChunkIndex] & 0x20) != 0)
                {
                    //
                    // Step 8: Clear the continuation bit
                    //

                    TempChunk[TempChunkIndex] &= 0x1F;

                    TempChunkIndex++;

                    continue;
                }

                //
                // Step 7 & 6: Reverse the chunk order and convert to a 32-bit integer
                //

                uint PolyPointDecimal = 0;

                for (var l = 0; l < TempChunkIndex + 1; l++)
                {
                    PolyPointDecimal += (uint)((1 << (5 * l)) * TempChunk[l]);
                }

                //
                // Step 5: If the low order bit is set, the original value was negative, invert.
                //

                if ((PolyPointDecimal & 0x1) == 1)
                    PolyPointDecimal = ~PolyPointDecimal;

                //
                // Step 4: Right shift the value 1 bit
                // Step 3 & 2: Convert back to floating point by dividing by 1e5
                //

                var PolyPoint = (double)((int)PolyPointDecimal >> 1) / 100000;

                //
                // Add chunks to the element list
                //

                GPolyElementList.Add(PolyPoint);

                //
                // Start a new chunk
                //

                Array.Clear(TempChunk, 0, MaxGPolyChunks);
                TempChunkIndex = 0;
            }

            //
            // The last chunk in the GPolyline must not be a continution chunk
            //

            if (TempChunkIndex != 0)
                throw new ArgumentOutOfRangeException();

            return GPolyElementList;
        }

        /// <summary>
        /// Decode a Google Encoded GPolyline into a LocationCollection
        /// </summary>
        /// <remarks>
        /// The Google Encoded GPolyline specification is defined
        /// at http://code.google.com/apis/maps/documentation/polylinealgorithm.html
        /// </remarks>
        /// <param name="gPolyString">Encoded GPolyline</param>
        /// <param name="GPolyLocationCollection">Collection Locations will be added to</param>
        /// <returns>Void</returns>
        /// <exception cref="System.ArgumentException">Thrown when there are no points in the GPolyline or an odd number of points</exception>
        public static void DecodeGPolylineToLocationCollection(string gPolyString, LocationCollection GPolyLocationCollection)
        {
            //
            // The caller may have sent us an empty string
            //

            if (String.IsNullOrWhiteSpace(gPolyString))
                return;

            var GPolyElementList = DecodeGPolyline(gPolyString);

            if ((GPolyElementList.Count % 2) != 0)
                throw new ArgumentException();

            if (GPolyElementList.Count == 0)
                return;

            var LastLocation = new Location(0.0, 0.0);
            bool IsLat = true;
            Location ElLoc = null;

            foreach (var El in GPolyElementList)
            {
                if (IsLat)
                {
                    ElLoc = new Location();

                    ElLoc.Latitude = El + LastLocation.Latitude;
                    IsLat = false;
                }
                else
                {
                    ElLoc.Longitude = El + LastLocation.Longitude;
                    IsLat = true;
                    GPolyLocationCollection.Add(ElLoc);
                    LastLocation = ElLoc;
                }
            }

            return;
        }
    }
}

Advertisements
This entry was posted in Computers and Internet. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s