Всем привет, я Максим, последнее время работаю на MAPS.ME, а конкретно в части ядра С++, обработки и подготовки данных. Хотелось бы поделиться своими наработками и похвастаться тем как приложение становится чуточку лучше.

Сокращения использованные мной:

• ОСМ — OpenStreetMap.org,

• ОТ — общественный транспорт,

• Автобус — на самом деле так называю любой тип ОТ, просто слова не нашел более подходящего по простоте.

Исходные данные об общественном транспорте мы берем с ОСМ, равно как и всю остальную базовую картографическую информацию. Рассказывать про представление данных на ОСМ я сильно не буду, для этого у них есть прекрасные статьи на их вики. Но все‑таки в качестве базы хотелось бы упомянуть что на ОСМ есть 3 типа объектов: точка, линия, объединение (в оригинальном именовании это Node, Way, Relation). Применительно к описанию общественного транспорта, каждый маршрут в каждую сторону — это объединение следующих объектов: сегментов дорог, точек остановки и платформ (это тоже термин из ОСМ, если по‑русски, то платформа — это как раз зачастую то, что мы называем остановкой в русском языке — место где люди ждут автобус).

Давайте сначала проследим за потоком преобразования данных который происходит у нас каждый раз при формировании карт. МАПС — приложение оффлайн, соответственно все базовые данные мы упаковываем в карты которые разбивают весь мир на 1200 регионов, они скачиваются в приложении пользователем для дальнейшего оффлайн использования. Объем упакованных бинарных данных с ОСМ на весь мир сейчас приблизительно 80ГБ. Это не какие‑то сырые бинарные данные, они ужаты всеми правдами и неправдами до сингулярности. Не скажу что прям big‑data, но для его разбора пришлось применять некоторые типовые ухищрения чтобы по памяти поместиться.

Первым делом был написан свой велосипед для вычленения необходимых данных, разбиения по регионам, преобразования в читаемый глазами формат (для верификации и дальнейшего разбора на питоне). Берем все линии ОТ, для них берем все сегменты дорог, остановки, далее для всех них собираем точки, сохраняем для каждого региона в отдельный файл.

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

• Сегменты дорог перечислены не в том порядке. Мы пытаемся восстановить их последовательность. Для нас это не проблема, идем дальше.

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

• Есть много маршрутов на ОСМ где отсутствуют точки остановки ОТ, только платформы. Эти точки по сути выступают только лишь в качестве проекции платформы на траекторию движения, мы не используем точки остановки, тем более что они тоже могут быть перепутаны относительно траектории и платформ. Более того, точки остановки не несут хоть сколько‑нибудь значимой информации, вся информация хранится либо в маршруте либо в платформе.

• Платформы могут быть перечислены не по порядку следования по траектории, мы пытаемся восстановить их последовательность. Это оказалось не самой логически простой задачей в общем случае. Ведь надо учитывать что маршруты могут проходить по одному и тому же сегменту в двух направлениях, проекции на полилинию траектории может не быть вовсе. Для сегмента проходимого в двух направлениях остановка в одну сторону должна подходить, а в другую сторону логично что нет. Из‑за задачи восстановления последовательности мы выкидываем остановки если они находятся не с правильной стороны по ходу прохождения траектории (да, учитываем лево‑/право‑ стороннее движение в регионе).

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

Это совсем не все проблемы.

• Почти тотально отсутствует информация о расписании, времени в пути, режиме работы. К примеру портят складывающуюся картину так называемые «ночные» автобусы, их надо если и предоставлять пользователям то под правильным соусом. Отсутствие расписания заставляет делать очень грубые допущения на данный момент, все автобусы становятся эквивалентны, что на самом деле абсолютно неприемлемо но мы пока что осознанно пошли на такое по простой причине: «лучше показать пользователю хоть какую‑то возможность чем не иметь никакой». В первом случае мы можем дальше развиваться и прийти к идеалу, второй вариант тупиковый.

• Портят картину автобусы которые не разбиты на прямой и обратный маршрут.

• Не решены проблемы когда в качестве платформы записана не точка а целый площадной объект‑платформа (не ясно что выбирать в качестве точки привязки. Мы же смело отказались от точек остановки:)) или вообще вообще объект‑релэйшн.

Сначала из‑за отсутствия хоть какой‑нибудь информации о движении мы выставляли на всех участках скорость взятую у сферического коня в вакууме. Она даже была настолько хороша что результаты получались аналогичными тем, что давали передовые навигационные приложения. Но была оговорка: это только в пределах города, без существенных пробок, за пределами города мы безбожно врали. Поэтому внедрена модель физического ускорения для расчета длительности, чутка картина выправилась. Отсутствие расписания также ставит перед фактом отсутствия понимания времени ожидания автобуса. Мы также пока что возлагаем выбор на пользователя но стараемся максимально помочь: предлагаются к примеру все эквивалентные способы добраться на ОТ. Эквивалентные в нашей терминологии — это идущие по той же траектории, не путайте с альтернативными.

Обработанные данные о линиях, остановках и траектории сохраняются в промежуточном формате для дальнейшей их записи в файл карты. Здесь никаких ноу‑хау, спасибо всем замечательным разработчикам приложения которые обкатали процесс загрузки информации о метро для дальнейшей маршрутизации и отрисовки. С точки зрения маршрутизации мы на данном этапе ничего не придумали нового, алгоритм на графе остался прежний (а‑стар), схема простая: в существующий граф дорог добавляются ребра от ОТ и связываются они ребрами‑проекциями на остановках.

Пред‑подготовка данных ОТ на данный момент выявила множество проблем с данными на ОСМ, мы подготовили отчет с ошибками, который будем обновлять при сборке новых карт (получается раз в несколько месяцев). Работа по улучшению диагностик еще впереди. Надеемся на взаимодействие с ОСМ коммьюнити с целью взаимовыгодного улучшения качества данных.

На данный момент даже не все возможности использования данных ОТ реализованы в приложении, мы в процессе. Что уже есть по ОТ:

• данные по всему миру по метро, автобусам, троллейбусам, трамваям, маршрутным такси

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

Уже на подходе функционал:

• поиск маршрута ОТ по названию и детальное отображение выбранного

• просмотр и выбор среди маршрутов проходящих по выбранной дороге или через выбранную остановку

• отображение сети ОТ для интересующих видов транспорта

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