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

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

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

Кроме того, для экономии места точки содержат только величину смещения от предыдущей точки (разумеется, за исключением первой точки). Все точки кодируются в Base64 как целые числа со знаком, поскольку значения широты и долготы являются числами со знаком. Реализация формата кодирования в ломаной линии требует предоставления двух координат, отражающих широту и долготу с разумным уровнем точности. Поскольку максимальное значение долготы составляет +/- 180 градусов с точностью до 5 знаков после запятой (от 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@

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

Пример

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

Оставить отзыв о...

Текущей странице
Google Maps APIs
Google Maps APIs