Encoded Polyline Algorithm Format

polyline.js

const encodeNumber = (n, precision) => {
    // Multiple number by 10^precision to round the result
    n = Math.round(n * +`1e${precision}`);

    /**
     * Number is already in two's complement so just shift left
     * by 1-bit and negate if and only if number is negative
     */
    n = n < 0 ? ~(n << 1) : n << 1;

    let encoded = '';

    // break the number in chunks of 5-bit (0x20 is the maximum with 5-bit)
    while (n >= 0x20) {
        /**
         * for each chunk:
         * and the number with 0x1f to take only the first 5-bit
         * or with 0x20 and add 0x3f to ensure proper display of characters
         * append the corresponding char
         */
        encoded += String.fromCharCode(((n & 0x1f) | 0x20) + 0x3f);

        // right-shift by 5-bit to take next chunk
        n >>= 5;
    }
    /**
     * last chunk doesn't need to and with 0x1f because is already less than 0x20
     * last chunk is always less than 0x20 and is used to determine the end
     * of sequence
     */
    encoded += String.fromCharCode(n + 0x3f);

    return encoded;
};

/**
 * Transform an array of coordinates in an encoded string
 * @param path Polyline coords
 */
export const encode = (path, precision = 5) =>
    path.reduce(
        (encoded, point, i) =>
            encoded +
            // encode the coordinates and join them in a string
            point.reduce(
                (str, p, j) =>
                    str +
                    // encode the offset from previouse point
                    encodeNumber(p - (i > 0 ? path[i - 1][j] : 0), precision),
                ''
            ),
        ''
    );

/**
 * Decode a string to an array of coordinates
 * @param str Encoded path
 */
export const decode = (str, precision = 5) => {
    // initialize path array, size should be at most half of encoded string
    let path = Array(Math.floor(str.length / 2)),
        pathSize = 0;

    // compute the multipler used for rounding
    precision = +`1e-${precision}`;

    for (let i = 0, strLen = str.length, lat = 0, lng = 0; i < strLen; ) {
        let n = 1,
            bitShift = 0,
            chr;

        /**
         * loop through characters until code at position is greater
         * than or equal 0xif
         */
        do {
            /**
             * subtract 0x3f from char code (used to ensure char visibility).
             * because each chunk is formed by 6-bit (chunk >= 0x20), after right-shifting
             * by 5-bit the LSB corresponds to the MSB of the next chunk, so it should
             * be remove by subtracting 1. for that purpose, `n` is initialized to 1, in
             * this way the first chunk doesn't take care of it.
             */
            chr = str.charCodeAt(i++) - 0x3f - 1;
            /**
             * move bits in the correct position
             * eg: n = 11000, chr = 10101, bitShift = 5
             * n += chr << bitShift = 1010111000
             */
            n += chr << bitShift;
            bitShift += 5;
        } while (chr >= 0x1f);
        /**
         * because during encoding process number is shifted by 1-bit and
         * complemented if negative, last bit is 1 if original number is negative.
         * In that case, complement the number before right-shifting by 1-bit
         */
        lat += n & 1 ? ~(n >> 1) : n >> 1;

        // do the previouse stuff for longitude too
        n = 1;
        bitShift = 0;
        do {
            chr = str.charCodeAt(i++) - 0x3f - 1;
            n += chr << bitShift;
            bitShift += 5;
        } while (chr >= 0x1f);
        lng += n & 1 ? ~(n >> 1) : n >> 1;

        // insert LatLng to array
        path[pathSize++] = [lat * precision, lng * precision];
    }

    // set array correct size
    path.length = pathSize;

    return path;
};