Кодирование полилинии — это алгоритм сжатия с потерями, который позволяет хранить последовательность координат в виде одной строки. Координаты точки кодируются с использованием значений со знаком. Если у вас есть только несколько статических точек, вы также можете использовать интерактивную утилиту кодирования полилиний .
В процессе кодирования двоичное значение преобразуется в серию кодов символов для символов ASCII с использованием знакомой схемы кодирования base64: чтобы обеспечить правильное отображение этих символов, закодированные значения суммируются с 63 (символ ASCII '?') перед преобразованием их в ASCII. . Алгоритм также проверяет наличие дополнительных кодов символов для данной точки, проверяя младший значащий бит каждой группы байтов; если этот бит установлен в 1, точка еще не полностью сформирована и должны последовать дополнительные данные.
Кроме того, для экономии места точки включают только смещение от предыдущей точки (за исключением, конечно, первой точки). Все точки закодированы в Base64 как целые числа со знаком, так как широта и долгота являются значениями со знаком. Формат кодирования внутри полилинии должен представлять две координаты, представляющие широту и долготу, с разумной точностью. Учитывая максимальную долготу +/- 180 градусов с точностью до 5 знаков после запятой (от 180,00000 до -180,00000), это приводит к необходимости 32-битного двоичного целого числа со знаком.
Обратите внимание, что обратная косая черта интерпретируется как escape-символ внутри строковых литералов. Любой вывод этой утилиты должен преобразовывать символы обратной косой черты в двойные обратные косые черты внутри строковых литералов.
Шаги для кодирования такого знакового значения указаны ниже.
- Возьмите начальное значение со знаком:
-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:
`~ойя@
В приведенной ниже таблице показаны некоторые примеры закодированных точек, показывающие кодировки как серию смещений от предыдущих точек.
Пример
Очки: (38,5, -120,2), (40,7, -120,95), (43,252, -126,453)
Широта | Долгота | Широта в E5 | Долгота в 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`@