Google Polyline Encoding

The Google Polyline Encoding is used by Google to encode latitudes and longitudes so that later a line can be drawn on a map by decoding the values. You can see the algorithm for encoding a series of latitudes and longitudes to a polyline here.

I have written a C implementation to encode and decode Google Polylines, along with a test iPad app here.

What is this algorithm doing, and why?

The aim of the algorithm is to dramatically decrease the amount of space required to represent the coordinates of the line (especially when encoded as a string). This is done by noticing that the gap between each point is small and so if you encode these diferences then you will need far less than 32 bits to encode each change in value.

Firstly, we need to work out the value that we are going to encode (we will do the latitude, encoding the longitude is identical in process). So we take the current latitude, multiply it by 1e5 and round the value to the nearest integer. Integers have a simpler representation than floats making them easier to manipulate.

From this value we subtract the previous integer latitude (which we calculated in the same way). This small difference between the latitudes is the value that we encode (if there is no previous latitude we choose it as 0).

We now likely have a small value to encode, so we could do with a way of encoding the value that doesn’t require a minimum of 32 bits. We’ll go through the algorithm with the positive value 35, and the negative value -35.

The first problem is negative values. Computers generally encode integers using twos compliment arithmetic; if the value is negative then the top bit is set, worse, small negative values have all of the high bits set. As the aim is to use as few bits as possible we need to encode negative values differently. The binary representations of our values are:

So instead of using twos compliment, the Google algorithm uses a sign bit (this means that a specific bit is used to determine the sign, e.g. if the sign bit is 1 the number is negative, if it’s 0 the number is positive. This bit is ignored by the rest of the number). The forth and fifth steps of the algorithm change the encoding away from twos complement if the value is negative.

Step four of the algorithm shifts the binary to the left, this allows room for the sign bit as the right most bit. We don’t lose the information from the bit shifted off the left of the number because this information is saved in the new sign bit on the right.

Step five of the algorithm inverts the number if the original was negative. This inversion flips the value of the right most bit to a 1 indicating we have a negative value. The inversion also flips all the bits on the left hand side. So small negative values get a lot shorter.

Now we need to encode these binary values using as few base64 values as possible. To do this we need a way of knowing when we have come to the end of our number (otherwise when decoding we won’t know where one number ends and the next begins). There are two ways to do this:

You can start your number with a length field (a fixed number of bits at the beginning which tells you how many base64 values make up the number). To guarantee that we can encode the whole number we need five base64 values, this means that a length field would have to be three bits long.

The other option is to set a continuation bit; if this bit is set, the base64 value we are reading is not the last value in the number.

The continuation bit is a more efficient encoding if we use less than three 64 bit values (as the length field takes three bits), and less efficient if we use more than three. As we are hoping our change in values is going to be small (i.e. less than or equal to three base64 values), a continuation bit should be more effiecient, so is used.

Now we will split the value up to encode it in base64. 64 is $2^6$, so base64 uses six bits. We need to keep a bit for the continuation bit, so we split the number up into five bit sections:

Now the algorithm reverses the orders of the chunks. The reason for this is that it is easier in code to read off the 5 bit chunks from the small end, and write the base64 bits from the large end. Our values now look like this:

Next, the algorithm adds the continuation bit at the left hand side if the chunk isn’t the last chunk of the number. To do this it bitwise ORs all but the last chunk with 0x20 (100000). This leaves our chunks like this:

Finally, we add 63 to each chunk, making that each chunk is a sensible ascii value. Each chunk is stored in its own byte, which can immediately be displayed as an ascii string. In our case after adding 63 we have:

Here is the code to encode the integer difference between the current location and the previous location (after each have been multiplied by 1e5 and rounded):

void encodedIntValue (int32_t val, char *result, unsigned *length)
{
  bool isNeg = val < 0;
  // Shift the value right by 1 to make room for the sign bit on the right 
  // hand side.
  val <<= 1;
 
  if (isNeg) {
    // As the value is stored as a twos compliment value, small values have a 
    // lot of bits set so binary not the value. This will also flip the value 
	// of the sign bit so when we come to decode the value we will know that 
	// it is negative.
    val = ~val;
  }
 
  unsigned count = 0;
 
  do {
    // get the smallest 5 bits from our value and add them to the charaters.
    result[count] = val & 0x1f;
 
    // We've saved the last 5 bits we can remove them from the value. We shift
    // the value by 5 meaning that the next 5 bits that we need to save will be
    // at the end of the value.
    val >>= 5;
 
    if (val) {
      // We have more bits to encode, so we need to set the continuation bit.
      result[count] |= 0x20;
    }
 
    result[count] += 63;
 
    ++count;
  } while (val);
 
  if (!length)
    printf ("required value `length` not set in `encodeIntValue`");
  else
    *length = count;
}

I have a C library for encoding and decoding Google polylines together with an iPad test app here.

When running the test app in the simulator make sure you go to the Debug menu and turn location services on (this will turn itself off on rebuilds).

When you stop recording locations the polyline is printed to the console, if you copy it to here you can see where the simulator has taken you.