Как работают сервисы карт и маршрутизации
Заглавное изображение
В период моей жизни, когда я работал в Санкт-Петербурге, пришла мне интереснейшая задача — создать и интегрировать в один проект функционал карт. По ограничениям бизнес требований, карта должна работать в условиях отсутствия интернета, при этом удовлетворять требования визуального отображения и построения маршрутов. Значит не было возможности использовать готовый API Яндекса или Google, так что пришлось реализовывать механизмы самому.
В этой статье я не буду давать какой то инструкции по реализации такого проекта, а скорее в общем опишу как работаю карты, которым мы постоянно пользуемся.
Техническое задание:
Отображать карту в схематичном виде.
Реализовать функционал построение маршрутов для АВТО и Ж/д транспорта.
Если маршрутов несколько, сортировать по релевантности (по ситуации).
Интегрировать пользовательский интерфейс карты со сторонним приложением (средой функционирования), и реагировать на команды от него.
Из чего состоят карты?
Ситуация типичная, во-первых — это данные. Существуют конкретные базы данных, которые содержат местоположение почти каждого объекта на планете, где указаны его координаты, обширное описание: его тип, адрес, назначение, напряжение в сети и многое другое. Базы даных постоянно обновляются сообществом, либо силами ведущих компаний.
Второе — это представление данных карты для конечного пользователя, которое отображается в клиентском приложении как схематическая картинка. Схематическая картинка, на которой, например, нарисован светофор, парк, название улицы и пешеходный переход, была отрисована «cервером отрисовывания картинок», основываясь на исходных данных из базы. Картинка отрисовывается на UI в определенном месте, и ее положение соответствует ассоциируемым координатам, а группа этих картинок создает для пользователя бесшовную простыню территории.
Сам пользовательский интерфейс дает возможность наносить клиентские (динамические или временные) объекты на карту — метки, маршруты и указатели на следующем слое, поверх основных графических данных самой карты.
Третье — это маршрутизация и поиск. Построение маршрута от координаты до координаты, которое производится так же на основе данных предоставленных в БД карт. Одним из алгоритмов, работающих на графах, мы ищем актуальные для нас маршруты, от точки до точки, дополнительно учитывая данные о пробках или дорожных работах и прочее.
Как создаются данные карт?
Надо упомянуть тот факт, что реализаций карт, и компаний которые их разрабатывают большое количество. Я в своем проекте пользовался данными сервиса OpenStreetMap (далее OSM).
Сервис OSM создан сообществом картографов, которые добавляют и поддерживают данные о дорогах, тропах, кафе, вокзалах и о многих других объектах по всему миру.
Любой желающий может воспользоваться сайтом OSM и внести изменение в разметку местности. Прямо в пользовательском интерфейсе есть возможность нанести на карту точку, линию, полигон, и дооснастить разметку описанием. Изменения проходят валидацию и далее расшариваются между клиентами.
Саратовская обл. пос. Тополёвка
Как альтернатива интерфейса для разметки разметки территории используется приложение Java под названием JOSM. Однако, оно показалось мне менее удобным, но сама разметка выглядит впечатляюще.
Интерфейс JOSM
В итоге, разметка карты строится просто — пользователь наносить объект на карту, и описывает его тегами. Теги в разметке очень важны, так как участвуют в визуализации или построении маршрута.
Как хранятся данные карт?
Это одна из самых впечатливших меня частей исследования. Модель хранения данных оказалась очень простой и удобной!
В интерфейсе редактора OSM есть возможность выгрузки части карты в формате .osm (xml) для чтения в текстовом редакторе. Открыв документ для чтения в любом текстовом редакторе, мы увидим простыню xml разметки и сухих неудобочитаемых данных.
Анимация описывает обьем данных, используемыx в картографии
OSM использует топологическую структуру данных, состоящую из объектов:
node (точка) — точка с указанными координатами;
way (линия) — упорядоченный список точек, составляющих линию или полигон;
relation (отношение) — группы точек, линий и других отношений, которым назначаются некоторые свойства;
tag (тег) — пары «ключ — значение», могут назначаться точкам, линиям и отношениям.
Модель данных, описаная в формате .osm является графом. Для простоты примера по чтению данных карты, возьмем ненасыщенную разметку на карте и экспортируем ее.
Экспорт данных OSM в файл
Если приглядеться к тексту разметки, который доступен по ссылке, можно увидеть, что список объектов элементов типа «node» наделен атрибутами «lat», «lon», которые являются широтой и долготой.
По сути, node — это точка на карте. Теги, которые содержит node, являются описанием этой точки.
Структура данных карт
Перейдя к блоку way (линии), в теле элемента линии, вложены элементы «nd ref='…'» которые несут в себе ссылку по id на «node» (точка), которая будет принадлежать этой линии.
Структура данных карт
Ниже будет описан массив relation (отношение, связь) который будет описывать некоторые свойства, которым связаны резиденты этих отношений.
Структура данных карт
Я так и не понял, откуда на части карты Энгельса появились «Дороги Воронежской области»…
Именно таким образом, в сжатом виде хранятся карты OSM. Базу данных все России можно скачать в сервисе Geofabric Download Server. Размер у нее будет впечатляющий — 5.6 Gb.
Страничка загрузки базы данных карт
Представление карты в пользовательском интерфейсе
Для отображения местности в интерфейсе браузера или приложения, необходимо представить сухие данные из .osm файла в виде графики. В моем случае этим слоем функционала занимается OSM Tile Server.
Удобным способом скоростного отображения карты без великой нагрузки на сервер, является запрос отдельных маленьких кусочков карты, и совмещение их в простыню на UI, будто обои «стык в стык».
Представление одной области на карте в разных масштабах
Tile Server принимаем в качестве ресурса .osm файл. Результат отрисовки можно получить с помощью HTTP запроса к серверу, где нужно передать положение и масштаб, обрисовываемой области.
Например: 'https://{server-host}/tiles/{z}/{x}/{y}', где z — это zoom (масштаб) карты, а x и y — порядковый номер плитки по горизонтали и вертикали. При этом количество плиток для каждого масштаба разное!
Количество плиток по одной оси карты будет зависеть от выбора текущего масштаба как 2 в степени zoom. Сам же zoom варьируется от 0 до 18. То есть, при масштабе равном 3, количество плиток по оси x будет равно 8, а количество плиток всей карты 81. При масштабе равном 18, количество плиток по оси x будет равно 262 144 шт., а количество плиток всей карты 68 719 476 736 шт.!
Представить работу сервера можно так — серверное приложение запрашивает данные из базы, исходя из параметров некой области и масштаба в запросе, анализирует выдачу базы, и основываясь на результате рисует линии, области, и объекты в картинку программно, будто на Canvas. Стили отрисовки картинок могут быть настроены разработчиком для большего впечатления пользователей.
Загрузка частей карты относительно масштаба и координат просмотра
В случае моего приложения, есть некоторые ограничения по использованию Tile Server на клиентских серверах приложений. Клиентские сервера работают под управлением ограниченной операционной системы, и на ней не возможно официально развернуть Tile Server.
Решением этого вопроса стал пререндер. Идея пререндера простая — на мощностях, располагаемых в офисе, был поднят OSM Tile Server. Я написал небольшое Spring Boot приложение, которое в несколько потоков долбило OSM Tile Server запросами, а картинки, которые он возвращал, складывались в базу Postgres в виде бинарных файлов с метаданными о местоположении и зуме этого куска карты.
Как работают сервисы карт и маршрутизаций., изображение №8
Было отрендерено 14 слоев карты, которых было достаточно для реализации функционала отображения, объёмом в 8 Gb и заняв время 2х суток. Важно уточнить, что рендерилась карта России, а карта мира заняла бы в разы больше времени и пространства на диске.
И тут настало время для JavaScript!
Исследуя просторы интернета, я узнал что самый популярный вариант отображения карт в интерфейсе — Leaflet.
Leaflet — ведущая библиотека JavaScript с открытым исходным кодом для интерактивных карт с удобным для мобильных устройств. Весом всего около 39 КБ JS, она имеет все функции картографирования, которые когда-либо нуждались большинству разработчиков.
В двух словах — необходимо подключить библиотеку к HTML файлу, натравить ее на Canvas, в котором она будет рисовать карту, и скормить ей шаблон ссылки, по которой ей нужно ходить за тайлами. Запрашиваемые тайлы будут отдаваться из базы данных посредством Spring Boot приложения.
Пример использования приложения Leaflet
Пропустив описание шага интеграции карт в продуктовое приложение, можно видеть следующий результат — карта работает без интернета.
Отображение карты в результате интеграции (изображение намеренно заблюрено)
Отображение анимации притормаживает, так как изображение транслируется через TeamViewer.
Анализ путей
Часть, претендующая на звание волшебства, в этой разработке, для меня была маршрутизация.
Путь, отображаемый в интерфейсе, является массивом точек координат. Точки координат, по которым будет обрисовываться маршрут, фильтруются из данных базы, ориентируясь на значения тегов, заданных назначением маршрута. Выбираются только те пути, которые подходят для проложения маршрута для данного вида транспорта.
В своем приложении для построения маршрутов, я использовал библиотеку проекта GraphHopper. В качестве ресурса, библиотека принимает в себя базу данных OSM.
Перед началом маршрутизации, задаются некоторые настройки работы приложения. Далее, при инициализации, формируются некоторые «индексы», некоторые опорные точки для быстрого поиска маршрутов, основанные на данных карты, и настройках сервиса.
Файлы, которые формирует приложение при старте
Создание индексов
Немного кода для ценителей:
Передаем библиотеке расположение файла базы данных.
Описываем, какой FlagEncoder (фильтр нод) будет использовать библиотека для построения индексов, то есть для выделение только тех линий, которые мы будем использовать.
Описываем, в какое место на диске компьютера, библиотека сможет складывать индексы.
Во время первого запуска приложение стартует долго, так как создает файлы индексов. В моем случае создаются индексы для АВТО и Ж/д (исключая метро и трамвай) маршрутов.
Конфигурация приложения
Конфигурация приложения
Вызывает интерес простота реализации самого FlagEncoder (фильтра):
Конфигурация приложения
Конфигурация приложения
Данный код, по сути, занимается обычной фильтрацией way элементов базы, при составлении индексов. В конкретном примере, при создании индекса для Ж/д транспорта, во время вызова метода acceptWay, читаются теги описывающие тип пути, и если он подходит для этого транспорта, то он пропускается в индекс.
Маршрутизация
Как упоминалось выше, набор точек и путей, в библиотеке маршрутизации, рассматривается в виде графа.
Для построения маршрута, необходимы координаты точек A (начала) и B (конца) маршрута, тип транспорта и его эффективность (самый быстрый, самый короткий). Сервис принимает значения этих параметров через HTTP запрос.
Необходимо выбрать две ближайшие точки из индекса карты к точкам A и В соответсвенно, и отправить их в сервис, реализующий вычисления на основе одного из алгоритмов построения эффективнейшего маршрута.
Алгоритмов расчета пути достаточно много, и их описание можно найти на просторах сети.
Список реализаций алгоритмов рассчета эффективных маршрутов:
В своем приложении я использую алгоритм Дейкстры.
Алгоритм Дейкстры строит множество вершин, для которых кратчайшие пути от источника уже известны, на каждом шаге к множеству добавляется та, из оставшихся вершин, расстояние до которой от источника меньше, чем для других оставшихся вершин.
Сервисы, такие как Яндекс.Карты и Google Maps, при расчёте маршрута используют в качестве весов не только расстояние между нодами, но и текущую ситуацию на дороге — пробки, дорожные работы, наверняка и комментарии пользователей.
Анимированное представление работы алгоритма Дейкстры
Результатом расчёта маршрута, получается множество точек координат, и детализация маршрута, которые отправляются обратно на UI.
Leaflet отрисовывает линию по этим координатам, что для конечного пользователя является маршрутом.
В дальнейшем, хотелось бы построить геокодер (полнотекстовый поиск) по организациям, улицам, зданиям и т.д., но это уже совсем другая история.
Спасибо за внимание!
