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

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

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

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

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

Ниже перечислены шаги кодирования такого значения со знаком.

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@

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