The Python equivalent of Bing Maps decompression algorithm

bing_maps_decompress.md

Bing Maps Decompression Algorithm - Python

Description

• Bing Maps compresses their polygon information.
• Their example decompression algorithm is unfortunately only available in C# (go figure): https://docs.microsoft.com/en-us/bingmaps/spatial-data-services/geodata-api#decompression-algorithm
• This is the working python equivalent.
• To use it, you send only the compressed data and not the number of polygons with comma.

bing_maps_decompress.py

import math

def decompress(value: str):
    safe_characters = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_-";

    index = 0
    xsum = 0
    ysum = 0

    polygon = []

    # While we have more data
    while index < len(value):
        # initialize the accumulator
        n = 0

        # initialize the count of bits
        k = 0

        while True:
            if index >= len(value):
                # If we ran out of data mid-number
                raise Exception("Compressed data out-of-bounds error")
            subject_character = value[index]
            index += 1

            if subject_character not in safe_characters:
                # If the character wasn't on the valid list
                raise Exception(f"Invalid character: {subject_character}")

            b = safe_characters.index(subject_character)
            # mask off the top bit and append the rest to the accumulator
            n |= (b & 31) << k
            # move to the next position
            k += 5
            if b < 32:
                # If the top bit was not set, we're done with this number.
                break

        # determine which diagonal it's on
        diagonal = int(((math.sqrt(8 * n + 5) - 1) / 2))

        # subtract the total number of points from lower diagonals
        n -= diagonal * (diagonal + 1) / 2

        # get the X and Y from what's left over
        ny = int(n)
        nx = diagonal - ny

        # undo the sign encoding
        nx = (nx >> 1) ^ -(nx & 1)
        ny = (ny >> 1) ^ -(ny & 1)

        # undo the delta encoding
        xsum += nx
        ysum += ny

        polygon.append([ysum * 0.00001, xsum * 0.00001])

    return polygon