Invitation Digital Tech Blog

Building Scalable & Responsive Architecture

By

Google PolyLine in .NET

Google’s PolyLine algorithm is designed as a lossy compression algoithm for latitude and longitude waypoint information into a compact and efficient string for transfering in their MapsAPI responses. We have built a GoogleMapsAPI client that uses a simple request/response pattern for retrieving data with minimal fuss, it’s now in production on the the vouchercloud website. As part of this we implemented a C# version of the PolyLine decoding logic. Below is an explanation of the algorithm.

When coming up with the algorithm it was noted that rather than have to represent each point in its entirety, it would be better to just take the differences between the current point and the previous. This would mean that each value could be represented using less than 32 bits therefore an instant saving, the purpose if this is to compress the values after all. The steps are very well explained on the Google developers site, here is each one with a brief explanation of why each one has been done.

  1. Take the initial signed value, this is either the first lat/long or the difference between the current one and the previous.
  2. Multiply by 1e5. This is to get the nearest integer rather than working with floats as they are much easier to represent in binary.
  3. Convert the integer to its binary representation using its two’s compliment. This is a standard way to handle negative numbers by inverting the binary value and adding one, this way we know that values where the most significant bit is 1 are positive and 0 are negative. Unfortunately in doing this small negative numbers get all of their high bits set and as the idea here is to use as little data as possible there needs to be a change made at this point. That happens in the next two steps using a sign bit.
  4. Left shift the binary values left by one bit.
  5. If the original number was negative, invert this encoding. That gets rid of all the 1s and puts a 1 in the most significant bit indicating that this is a negative number.
  6. All of the blocks are inverted now so that they are read in the order that they are streamed, read from right to left as they arrive.
  7. The block of binary is split into chunks of 5, this is so that we can add a continuation bit and have 6 bits for the base 64 encoding. We could have a block that represented the length of the section that we are encoding or decoding but it’s more efficient to use a continuation bit. This means that when we’re decoding the string, if (characterValue & 0x20) != 0x20 then we are at the end of a block and we need to continue getting the binary values for this integer. Once we find a 0 in our continuation bit we know that we’ve got a value and we can deal with it.
  8. Now add 63 to the values to guarantee that they are going to land in range that can be represented in ASCII
  9. Lastly convert it to its ascii value and you have a PolyLine string

Here is the code to decrypt a PolyLine string to an array of latitude and longitude values that represent the differences between the previous values rather than an actual point itself.

public static Location[] ToLocationPoints(this string polyLine)
{
    var binary = 0;
    var shiftCounter = 0;
    var locations = new List<Location>();
    var iteration = 0;
    var currentLatitude = 0d;
    var currentLongitude = 0d;

    foreach (var characterValue in polyLine.Select(t => t - 63))
    {
        var shift = shiftCounter++ * 5;
        if ((characterValue & 0x20) == 0x20)
        {
            binary |= (characterValue & ~0x20) << shift;
        }
        else
        {
            binary |= characterValue << shift;
            var value = Convert.ToDouble(((binary & 1) == 1 ? ~binary : binary) >> 1) / 1E5;
            if (iteration++ % 2 == 0)
            {
                currentLatitude += value;
            }
            else
            {
                currentLongitude += value;
                locations.Add(new Location { Latitude = currentLatitude, Longitude = currentLongitude });
            }

            binary = 0;
            shiftCounter = 0;
        }
    }

    return locations.ToArray();
}