How do we decode step 5 of the encoding algorithm format in Google encoding?

Question

Good afternoon everyone

I have a line representing some polylines encoded using the Google Encoded Polyline Algorithm Format , and I need to decode them to get the latitude and longitude.

There are 11 steps in the encoding scheme, and I assume that for decoding I would work on them (I work with an example of the string ` ~oia@ ):

Step 11. Convert each char to its equivalent ASCII = 96 126 111 105 97 64

Step 10. Minus 63 to each value = 33 63 48 42 34 1

Step 9. Convert to bits 6 bits = 100001 111111 110000 101010 100010 000001

Step 8. Delete the sixth bit, counting from the right: 00001 11111 10000 01010 00010 00001

Step 7. Reverse order = 00001 00010 01010 10000 11111 00001

Step 6. Align them with the pieces 8 = 00000010 00100101 01000011 11100001

Step 5. If the original decimal value is negative, invert the bit ...

But without knowing the original decimal value, how do we know that the original decimal value is positive / negative?

Answer 1

When encoding, we left the shift of the binary value by one bit and invert the bits if the number is negative,

This means that when decoding, if the last bit is 0, the initial number is positive. If the last bit is 1, the starting number is negative:

 1 => 00000010 2 => 00000100 3 => 00000110 4 => 00001000 5 => 00001010 6 => 00001100 7 => 00001110 8 => 00010000 -1 => 00000001 -2 => 00000011 -3 => 00000101 -4 => 00000111 -5 => 00001001 -6 => 00001011 -7 => 00001101 -8 => 00001111 

The complete decoding solution posted here for anyone interested:

 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 2

Since this is a language agnostic question, I will add this PHP solution (since the >>> operator does not exist in PHP) from the Peter Chng 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 simple, to find the original value, you can calculate whether it is the positive or negative last bit for each value that you have already converted from your ASCII characters.

Example:

Step 5. If your value, broken into pieces (pieces 5), has the last bit "0x1f", then this is negative, and you should invert it as in: |= ($foo & 0x1f) << $shift;

00000010 00100101 01000011 11100001

4 Double-shift the binary value:

11111101 11011010 10111100 00011110

3 Convert the binary value to decimal, remember, if you understand that it is a negative number, then you must convert it from two additions, Two additions : if it was positive, just convert the binary file as usual:

11111110 11101101 01011110 00001111

11111110 11101101 01011110 00001110

00000001 00010010 10100001 11110001 <- our initial value is unsigned

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

1 Add the original value of your character (if necessary) -179.98321 (this is a bit of data loss, but its rather inappropriate)