Issues with the Encoded Polyline Algorithm Format

Question

I wrote an encoder in python based on the information about the Encoded Polyline Algorithm Format found here.

If I set the number to -179.9832104, like in the example, I get the expected result: "`~oia@". However if I try with one of the Latitudes/Longitudes provided at the bottom, the result I get is not 100% correct according to the table.

If I set the number to 38.5, the result I get is "_p~if?", but according to the text it's supposed to be "_p~iF". Also, if I set the number to -120.2, I get "~ps|u?", but it's supposed to be "~ps|U".

It looks like it's only the example that uses all six letters, and I don't get why there is no sixth letter in the table. My guess would be that if the last letter is 0 (+63 => '?'), that it's skipped, and the fifth letter is made uppercase. The description of the algorithm doesn't mention that, though.

Can anyone tell me if some information is missing from the documentation of the algorithm? If not, what am I doing wrong?

My implementation of the algorithm:

number=-120.2
current = (number*pow(10,5)).__round__()

current <<= 1
       
if number < 0:
    current = ~current

chunks = []

# break into 5 chunks

for shift in range(0,6):
    if (shift > 0):
        current >>= 5
       
    bits = current & 0x1f
       
    chunks.append(bits)

# we don't need reverse in our 'implementation'
#chunks.reverse()

for x in range(0,5):
    chunks[x] |= 0x20

for x in range(0,6):
    chunks[x] += 63

encoded = ""

for x in range(0,6):
    encoded += chr(chunks[x])


print ("encoded coord: ", encoded)

Answer 1

Your algorithm is failing sometimes because you are always assuming you will wind up with six 5-bit chunks after step 6 from https://developers.google.com/maps/documentation/utilities/polylinealgorithm.

This is true when encoding a number like -179.9832104, since by step 6 you have 00001 00010 01010 10000 11111 00001. But with the other two examples (38.5 and -120.2) that is not the case. They only have five 5-bit chunks. Your earliest assumption is at the line for shift in range(0,6): You can see this issue if you add a line print("bits: ", bits) immediately after your line bits = current & 0x1f.

If so you will see the "bits" (if number=38.5). From your algorithm will be bits: 0 17 31 10 7 0, when in actuality they should be bits: 0 17 31 10 7 only. Then you compound this when adding 32 (0x20) to each of the first five chunks (when you should only add to the first four, because the last shouldn't exist). This is why all of your incorrectly encoded points have the fifth character being 32 higher than they should and the sixth character is always ? (which is 63 in ASCII).