Yandex.Maps Polyline encoder & decoder

readme.md

Decoding and encoding of Yandex.Maps Polyline format

Sometimes Yandex introduced a small and interesting format for encoding polylines of geographic points into string that can be delivered in GET-parameters of an URL or in URL path.

Detailed reading: https://tech.yandex.ru/maps/doc/jsapi/1.x/dg/tasks/how-to-add-polyline-docpage/

Sample

This sample introduces encoding of the way from subway station "Park Pobedi" to the Yandex's office.

https://static-maps.yandex.ru/1.x/?l=map&pl=6qE9AjZzUgN1-v__v_X__x_1__-dBgAA&spn=0.008,0.008&plc=8822DDC0&plw=5&key=AKGZNkkBAAAAH_M8CgQA7FLplKkfFDhFFzy7nkwJqkdcyHAAAAAAAAAAAADDnUutMak9ItrhKofGJfwzooVHbQ==

Step 1

Writing coords of the polyline

37.593578 55.735094
37.592159 55.732469
37.589374 55.734162

Step 2

Multiplexing each coordinate by 1 000 000 to get unit32

37593578 55735094
37592159 55732469
37589374 55734162

Step 3

Calculating bias of points from the second one to previsious

37593578 55735094
-1419 -2625
-2785 1693

Step 4

Convert each number to the binary representation with zeros to get the length of 32 bits (4bytes)

00000010001111011010000111101010
00000011010100100111001100110110
11111111111111111111101001110101
11111111111111111111010110111111
11111111111111111111010100011111
00000000000000000000011010011101

Step 5

Split each by 1 byte (8 bits)

00000010 00111101 10100001 11101010

Inverse the order of bytes

11101010 10100001 00111101 00000010

Step 6

Convert bytes with urlsafe base64 encoder.

In urlsafe base64 encoder +/ are replaced by _=

Step 7

Profit!

example.py

base = 'NTA9AtcdVAMYiQIABuT-__pO___OP_7_ziv9_yGx__9dq_7_PwYBAMhNAADwFwEAN18AAOJb__8MtQAApLz___bfAAAkYwAAAFP__xNjAAA='

assert yandex_to_human_decoder(yandex_to_human_encoder(yandex_to_human_decoder(base))) == yandex_to_human_decoder(base)
assert yandex_to_human_encoder(yandex_to_human_decoder(base)).decode() == base

assert yandex_to_human_decoder(base) == [(37564469, 55844311),(37730637, 55771613),(37685319, 55656875),(37499925, 55636684),(37412722, 55703819),(37432634, 55775483),(37457009, 55733469),(37503357, 55716225),(37560691, 55741605),(37516403, 55766968)]

lib.py

import binascii
import base64
import numpy as np

def num2bytes(n):
    bb = []
    for i in range(4): bb.append(int(('{0:032b}'.format(n))[i*8:i*8+8], 2))
    bb.reverse()
    return bb

def yandex_to_human_decoder(encoded_string):
    data = base64.urlsafe_b64decode(encoded_string)
    coords = []
    for i in range(len(data) // 8):
        coord = tuple(map(lambda x: np.int32(int(binascii.b2a_hex(x[::-1]), 16)), (data[i*8:i*8+4], data[i*8+4:i*8+8])))
        coords.append((coord[0]+coords[~0][0],coord[1]+coords[~0][1]) if len(coords) else coord)
    return coords

def yandex_to_human_encoder(coords_tuple):
    data = []
    last_coord = None
    for pair in coords_tuple:
        data.extend(map(num2bytes, pair if not last_coord else (np.uint32(pair[0] - last_coord[0]),np.uint32(pair[1] - last_coord[1]))))
        last_coord = pair
    return base64.urlsafe_b64encode(b''.join(map(bytes,data)))