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

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

В процессе кодирования двоичное значение преобразуется в серию кодов символов для символов 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:
    `~ойя@

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

Пример

Очки: (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`@