Мы начинаем этот пост с определения из Википедии того, что такое ломаная линия, также известная как многоугольная линия:

В геометрии многоугольная цепь - это связная серия отрезков прямой. Более формально, полигональная цепь P - это кривая, заданная последовательностью точек, называемых ее вершинами. Сама кривая состоит из отрезков прямых, соединяющих последовательные вершины.

Итак, с изображением мы теперь говорим о многоугольных линиях, заданных координатами GPS.

Полилинии Google - это немного больше, чем просто многоугольные линии. Это многоугольный путь GPS, закодированный в виде строки символов, состоящей только из символов ASCII, которые можно передавать как есть через URL-адреса, что позволяет использовать их в REST API. Вот пример результирующей кодировки: _p~iF~ps|U_ulLnnqC_mqNvxq`@.

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

Поскольку наши серверы разработаны на языке ruby, мы сначала использовали драгоценный камень ruby ​​polylines. Но этот гем оказался довольно медленным, и команда переписала его на гем с открытым исходным кодом fast-polylines. Как вы, более технологичные наркоманы, могли убедиться, посмотрев на исходный код из google-map-services gem d ocumentation, наша реализация довольно близка к реализации Google, хотя мы допускаем произвольную точность в качестве параметра.

В оставшихся абзацах этой статьи я хотел бы немного углубиться в полилинии, объясняя простыми словами идею алгоритма и то, как мы можем настроить его для обработки пространственно-временных полилиний ², что - это полилинии из временных координат GPS.

Алгоритм ломаной линии должен согласовывать две цели:

  • Мы хотим, чтобы наш многоугольный путь можно было использовать в URL-адресе в виде простой строки без дальнейшего кодирования.
  • Нам нужно сжать нашу многоугольную линию, чтобы количество байтов, необходимых для ее хранения, оставалось небольшим.

Как объясняют сами Google, алгоритм состоит из следующих шагов:

  • Возьмите список GPS-координат [(Широта, Долгота)], где Широта и Долгота - плавающие значения.
  • Преобразуйте каждое число в целое, умножив на 10⁵ (это желаемая точность координат) и округлив его³.
  • Для каждого числа выполните некоторую магию сдвига и перемешивания битов, затем разделите эту длинную строку из 0 и 1 на куски.
  • Преобразуйте каждый кусок в десятичное число и добавьте к нему код ASCII ?. В итоге вы получите строковое представление вашего числа.
  • Соедините всю эту маленькую строку вместе в порядке Lat1, Lng1, Lat2, Lng2, ... LatN,LngN, чтобы получить уникальную строку.

Есть еще одна деталь, которую я опустил для упрощения. Хотя предыдущий алгоритм может работать, вы получите действительно длинные строки, поскольку чем больше целое число (представьте 48,12345, представленное как 4812345, а 0,00000 представлено только символом 0), тем больше символов потребуется для его записи в ломаную линию. Есть простой прием, решающий нашу проблему. Вместо записи списка координат Lat1, Lng1, Lat2, Lng2, Lat3, Lng3… мы записываем разницу между предыдущей координатой (что-то вроде Lat3-Lat2, Lng3-Lng2) и текущей. Позволь мне привести пример:

Вместо того, чтобы кодировать 3 координаты [48.101, 27.103, 48.123, 27.143, 48.120, 27.125, 48.117, 27.129] напрямую, мы будем кодировать[48.101, 27.203, 0.012, 0.040, -0.003, -0.018, -0.003, 0.004], который намного меньше.

Теперь, когда вы можете закодировать список GPS-координат в ломаную линию, вы можете спросить, как их декодировать и восстановить данные. Благодаря магии битового сдвига, все символы, кроме последнего, в строке кодирования, исходящей из одного числа, будут иметь значение ASCII строго ниже _. Это позволяет нам снова разбить струну на маленькие струны и полностью изменить процесс. Вот код, который разбивает строку на более мелкие части:

Мы сделали это! Знайте, что вы знаете все, что вам нужно для понимания алгоритма на высоком уровне. Вы можете преобразовать список координат (Lat, Lng) в полилинию и вернуть полилинию обратно к этому списку чисел.

Но что, если мы хотим закодировать список из триплетов (Lat, Lng, Timestamp)?

Теперь у нас есть все инструменты, чтобы ответить на этот вопрос. Помните, что мы кодируем пару (Lat, Lng) путем преобразования Lat и Lng в целые числа. Но Timestamp уже целое число. Так что все мы можем в принципе пропустить этот шаг. 🙂

Затем мы можем просто закодировать в строку Lat1, Lng1 и Timestamp1. На следующем этапе мы вычисляем Lat2-Lat1, Lng2-Lng1 и Timestamp2-Timestamp1. Мы кодируем каждое из этих трех чисел и повторяем этот процесс. После того, как мы обработали все триплеты, мы склеиваем все эти строки вместе в указанном порядке. В итоге получаем свободные размерные полилинии. Мы могли бы обобщить этот процесс до четырех измерений (4-вершины) или даже n (n-вершины).

В заключение, вот код для кодирования пространственно-временных полилиний. Я оставляю вам расшифровку в качестве упражнения. Повеселись!

¹ Вы можете получить доступ к коду, щелкнув ссылку View Source.
² Мне нравится, как это имя звучит как из научно-фантастической книги. Пожалуйста, простите меня за название.
³ Это означает, что у нас есть местоположение с точностью до 5 цифр после точки, чего достаточно, чтобы две точки различались на расстоянии одного метра.
⁴ Это часть OR 0x20 алгоритм, описанный google.