Формат алгоритма кодированной ломаной линии

Кодирование полилиний — это алгоритм сжатия с потерями, который позволяет хранить ряд координат в виде одной строки. Координаты точки кодируются с использованием значений со знаком. Если у вас всего несколько статических точек, вы также можете использовать утилиту интерактивного кодирования полилиний .

Процесс кодирования преобразует двоичное значение в серию кодов символов для символов ASCII с использованием знакомой схемы кодирования base64: чтобы обеспечить правильное отображение этих символов, закодированные значения суммируются с 63 (символ ASCII '?') перед преобразованием их в ASCII. . Алгоритм также проверяет наличие дополнительных кодов символов для данной точки, проверяя младший бит каждой группы байтов; если этот бит установлен в 1, точка еще не полностью сформирована и должны последовать дополнительные данные.

Кроме того, в целях экономии места точки включают только смещение от предыдущей точки (за исключением, конечно, первой точки). Все точки кодируются в Base64 как целые числа со знаком, поскольку широта и долгота являются значениями со знаком. Формат кодирования внутри ломаной линии должен представлять две координаты, представляющие широту и долготу, с разумной точностью. Учитывая максимальную долготу +/- 180 градусов с точностью до 5 десятичных знаков (от 180,00000 до -180,00000), это приводит к необходимости использования 32-битного двоичного целочисленного значения со знаком.

Обратите внимание, что обратная косая черта интерпретируется как escape-символ внутри строковых литералов. Любой вывод этой утилиты должен преобразовывать символы обратной косой черты в двойную обратную косую черту внутри строковых литералов.

Шаги по кодированию такого знакового значения указаны ниже.

1. Возьмите начальное значение со знаком:
   -179.9832104
2. Возьмите десятичное значение и умножьте его на 1e5, округлив результат:
   -17998321
3. Преобразуйте десятичное значение в двоичное. Обратите внимание, что отрицательное значение должно вычисляться с использованием дополнения до двух путем инвертирования двоичного значения и добавления единицы к результату:
   

   00000001 00010010 10100001 11110001
   11111110 11101101 01011110 00001110
   11111110 11101101 01011110 00001111
   

4. Сдвиньте двоичное значение влево на один бит:
   11111101 11011010 10111100 00011110
5. Если исходное десятичное значение отрицательное, инвертируйте эту кодировку:
   00000010 00100101 01000011 11100001
6. Разбейте двоичное значение на 5-битные фрагменты (начиная с правой стороны):
   00001 00010 01010 10000 11111 00001
7. Поместите 5-битные фрагменты в обратном порядке:
   00001 11111 10000 01010 00010 00001
8. ИЛИ каждое значение с 0x20, если за ним следует еще один битовый фрагмент:
   100001 111111 110000 101010 100010 000001
9. Преобразуйте каждое значение в десятичное:
   33 63 48 42 34 1
10. Добавьте 63 к каждому значению:
    96 126 111 105 97 64
11. Преобразуйте каждое значение в его эквивалент ASCII:
    `~oia@

В таблице ниже показаны некоторые примеры закодированных точек, показывающие кодировки как серию смещений от предыдущих точек.