Кодирование ломаных линий – это алгоритм сжатия с потерями, который позволяет хранить последовательность координат в виде одной строки. Координаты точек кодируются с использованием подписанных значений. Если у вас всего несколько статических точек, вы также можете использовать интерактивную программу кодировки ломаных линий.
В процессе кодирования двоичное значение преобразуется в последовательность кодов символов ASCII с помощью известной схемы кодирования base64. Чтобы обеспечить правильное отображение этих символов, закодированные значения суммируются с 63 (символ ASCII "?") перед преобразованием в ASCII. Алгоритм также проверяет дополнительные коды символов для определенной точки, анализируя младший бит каждой группы байтов. Если этот бит равен 1, точка ещё не сформирована полностью и за ней должны следовать дополнительные данные.
Кроме того, чтобы сэкономить место, точки содержат только смещение относительно предыдущей точки (кроме первой точки). Все точки кодируются в Base64 как целые числа со знаком, поскольку широта и долгота являются значениями со знаком. Формат кодирования в ломаной линии должен представлять две координаты (широту и долготу) с достаточной точностью. Учитывая, что максимальная долгота составляет +/- 180 градусов с точностью до пяти знаков после запятой (от 180,00000 до -180,00000), для ее хранения требуется 32-битное целое число со знаком.
Обратите внимание, что обратная косая черта интерпретируется как экранирующий символ в строковых литералах. Любые выходные данные этой утилиты должны преобразовывать символы обратной косой черты в двойные обратные косые черты в строковых литералах.
Ниже перечислены шаги кодирования такого значения со знаком.
- Возьмите исходное подписанное значение:
-179.9832104 - Возьмите десятичное значение и умножьте его на 1e5, округлив результат:
-17998321 - Полученное десятичное значение конвертируется в двоичное. Обратите внимание, что отрицательное значение должно быть рассчитано с использованием
дополнительного кода путем инвертирования двоичного значения и добавления единицы к результату:
00000001 00010010 10100001 11110001 11111110 11101101 01011110 00001110 11111110 11101101 01011110 00001111
- Сдвиньте двоичное значение влево на один бит:
11111101 11011010 10111100 00011110 - Если исходное десятичное значение отрицательное, инвертируйте кодировку:
00000010 00100101 01000011 11100001 - Разбейте двоичное значение на 5-битные фрагменты (начиная справа):
00001 00010 01010 10000 11111 00001 - Расположите 5-битные фрагменты в обратном порядке:
00001 11111 10000 01010 00010 00001 - ИЛИ каждое значение с 0x20, если за ним следует другой фрагмент битов:
100001 111111 110000 101010 100010 000001 - Преобразуйте каждое значение в десятичное:
33 63 48 42 34 1 - Добавьте к каждому значению число 63:
96 126 111 105 97 64 - Преобразуйте каждое значение в эквивалент ASCII:
`~oia@
В таблице ниже приведены примеры закодированных точек, где кодировка представлена в виде последовательности смещений относительно предыдущих точек.
Пример
Точки: (38.5, -120.2), (40.7, -120.95), (43.252, -126.453)
| Широта | Долгота | Широта x E5 | Долгота x E5 | Изменение широты | Изменение долготы | Закодированная широта | Закодированная долгота | Закодированная точка |
| 38.5 | -120.2 | 3850000 | -12020000 | +3850000 | -12020000 | _p~iF |
~ps|U |
_p~iF~ps|U |
| 40.7 | -120.95 | 4070000 | -12095000 | +220000 | -75000 | _ulL |
nnqC |
_ulLnnqC |
| 43.252 | -126.453 | 4325200 | -12645300 | +255200 | -550300 | _mqN |
vxq`@ |
_mqNvxq`@ |
Закодированная ломаная линия: _p~iF~ps|U_ulLnnqC_mqNvxq`@