How to decode Google's Polyline Algorithm?

Question

Google's Encoded Polyline Algorithm Format:

How do you decode this?

Perhaps run the algorithm backwards; But I'm stuck at step 5: without the initial value, how do I know if it's positive/negative?

Answer 1

Here's my (tested, working) solution in C#:

public static List<Point<double>> DecodeGooglePolyline(string s)
{
    // Decode the sequence of integers
    var integers = new List<long>();

    for (int i = 0; i < s.Length;) {
        long zzInteger = 0;

        for (int shift = 0; i < s.Length; shift += 5) {
            int sixBits = s[i++] - 63;
            if ((uint)sixBits > 63)
                throw new FormatException("Invalid character in Google polyline");

            zzInteger |= ((uint)sixBits & 0b0001_1111) << shift;

            if (sixBits < 32)
                break;
        }

        integers.Add((zzInteger & 1) != 0 ? ~(zzInteger >> 1) : zzInteger >> 1);
    }

    Debug.Assert((integers.Count & 1) == 0);

    // Convert the sequence of integers to points
    var points = new List<Point<double>>();
    var point = new Point<double>(0, 0);
    for (int i = 0; i + 1 < integers.Count; i += 2) {
        point = new Point<double>(point.X + integers[i + 1] / 1e5, point.Y + integers[i] / 1e5);
        points.Add(point);
    }

    return points;
}

Note: C# lacks a "standard" point type, so replace with a type of your choice.

Answer 2

Its encoding leftshifts then inverts if negative, eg:

1: 0000_0001 =>0000_0010
2: 0000_0010 =>0000_0100
3: 0000_0011 =>0000_0110
4: 0000_0100 =>0000_1000
5: 0000_0101 =>0000_1010
6: 0000_0110 =>0000_1100
7: 0000_0111 =>0000_1110
8: 0000_1000 =>0001_0000

-1: 1111_1111 =>1111_1110 =>0000_0001
-2: 1111_1110 =>1111_1100 =>0000_0011
-3: 1111_1101 =>1111_1010 =>0000_0101
-4: 1111_1100 =>1111_1000 =>0000_0111
-5: 1111_1011 =>1111_0110 =>0000_1001
-6: 1111_1010 =>1111_0100 =>0000_1011
-7: 1111_1001 =>1111_0010 =>0000_1101
-8: 1111_1000 =>1111_0000 =>0000_1111

Thus, decoding has if last bit is 0, initial is positive, and if last bit is 1, initial is negative.

---

Appendix:

Full decoding demo:

public class Test {
 public static void main(String args[]) {
  for (int point : Decode("_p~iF~ps|U_ulLnnqC_mqNvxq`@",10)) {
   System.out.println(point); // Be aware that point is in E5
  }
 }

 private static java.util.List<java.lang.Integer> Decode(String encoded_polylines, int initial_capacity) {
  java.util.List<java.lang.Integer> trucks = new java.util.ArrayList<java.lang.Integer>(initial_capacity);
  int truck = 0;
  int carriage_q = 0;
  for (int x = 0, xx = encoded_polylines.length(); x < xx; ++x) {
   int i = encoded_polylines.charAt(x);
   i -= 63;
   int _5_bits = i << (32 - 5) >>> (32 - 5);
   truck |= _5_bits << carriage_q;
   carriage_q += 5;
   boolean is_last = (i & (1 << 5)) == 0;
   if (is_last) {
    boolean is_negative = (truck & 1) == 1;
    truck >>>= 1;
    if (is_negative) {
     truck = ~truck;
    }
    trucks.add(truck);
    carriage_q = 0;
    truck = 0;
   }
  }
  return trucks;
 }
}

Answer 3

Since this is a language-agnostic question, I will add this PHP solution (since the >>> operator does not exist in PHP) from Peter Chng's unitstep blog:

function decodePolylineToArray($encoded)
{
  $length = strlen($encoded);
  $index = 0;
  $points = array();
  $lat = 0;
  $lng = 0;

  while ($index < $length)
  {
    $b = 0;
    $shift = 0;
    $result = 0;
    do
    {
      $b = ord(substr($encoded, $index++)) - 63;
      $result |= ($b & 0x1f) << $shift;
      $shift += 5;
    }
    while ($b >= 0x20);
    $dlat = (($result & 1) ? ~($result >> 1) : ($result >> 1));
    $lat += $dlat;

    $shift = 0;
    $result = 0;
    do
    {
      $b = ord(substr($encoded, $index++)) - 63;
      $result |= ($b & 0x1f) << $shift;
      $shift += 5;
    }
    while ($b >= 0x20);

    $dlng = (($result & 1) ? ~($result >> 1) : ($result >> 1));
    $lng += $dlng;

    $points[] = array($lat * 1e-5, $lng * 1e-5);
  }
  return $points;
}

Additional instructions from Google developers

Update: The decoding instructions are almost straightforward, in order to find the original value, you can calculate if it is positive or negative by the last bit on each value you already transform from your ASCII characters.

ex:

Step 5. If your value chunked (chunks of 5) has a last bit '0x1f' then it is negative and you should invert it as in: |= ($foo & 0x1f) << $shift;

00000010 00100101 01000011 11100001

4 Right-shift the binary value one bit:

11111101 11011010 10111100 00011110

3 Convert the binary value to decimal, Remember if you realize this was a negative number, then you must transform it from two's complement,Two's complement: if it was positive then just convert the binary as usual:

11111110 11101101 01011110 00001111

11111110 11101101 01011110 00001110

00000001 00010010 10100001 11110001 <-- our original value unsigned

2 The decimal value was multiplied by 1e5, so divided it to get the initial value: 179.98321

1 Add the original value its sign (if it needs it) -179.98321 (the is a little bit of data loss, but its quite irrelevant)