Мы добавили реалистичные дороги в навигатор 2ГИС. Теперь дорожное покрытие, разметка, объёмные развязки, съезды, островки безопасности и опоры на многоуровневых дорогах выглядят как в жизни. Под капотом — решение задачи по превращению «плоской» геометрии в объекты с реалистичными шириной и высотой. Чтобы не замедлять обновление дорожной сети, нам требовалась минимальная задержка между изменением дороги и обновлением её «объемного» представления.

Расскажу, как в одном сервисе формируем очереди в RabbitMQ, а в других — читаем и при помощи библиотеки NetTopologySuite превращаем плоские объекты в реалистичные. Выбранный нами подход с потоковой обработкой изменений универсален, поэтому статья может быть интересна всем, кто работает с геометрией и системами реального времени в целом.

От задачи – к поиску решений

У нас 977 000 километров дорог, 64 000 регулируемых перекрёстков и 480 000 знаков, из которых нужно создать дорожные полотна и разметку. К тому же эти данные постоянно обновляются нашими картографами, поэтому сгенерировать «объёмные» геообъекты один раз и забыть недостаточно, нужно их постоянно актуализировать, иначе то, что мы видим в реальной жизни и на карте перестанет быть сопоставимым.

Fiji — это центральная система 2ГИС для хранения всех геоданных, включая информацию о всех звеньях, дорожных знаках и перекрёстках. Звено в этом контексте — участок дорожной сети, являющийся линией и обладающий различными атрибутами, но отображаемый на карте без их учета. 

Мы начали стремиться к большей детальности в картах, к реалистичности. Так появилась новое понятие — иммерсивное звено, которое представляет эту же линию, но в виде полигона, воспроизводящего реальное дорожное пространство с учётом всех атрибутов, таких как направление движения, количество полос и других характеристик. Это позволяет создать на карте изображение, максимально приближенное к тому, что мы видим в реальной жизни. 

Покажу на примере. Нам нужно было превратить первое изображение во второе, чтобы пользователи увидели третье ↓

1 — скрин с Fiji без разметки и полотен, 2 — Fiji с разметкой и полотнами, а 3 — результат онлайн
1 — скрин с Fiji без разметки и полотен, 2 — Fiji с разметкой и полотнами, а 3 — результат онлайн

На первый взгляд казалось, что всё есть: дописать немного кода для расширения дорог и создания разметки, и готово (да-да, про наше приключение «туда-обратно» можно почитать ещё тут). Однако получилось сложнее. Чтобы больше погрузить в решение, к которому мы пришли, расскажу про то, с чем и как мы работаем. 

Какими данными мы располагаем

Для хранения данных мы используем EAV-модель. В упрощённом виде схема для объектов с геометрией выглядит так:

Сущности в БД делятся на две категории:

  1. Feature — каждый объект на карте, FeatureAttributeValue — значение атрибута объекта.

  2. FeatureClass — описание класса объектов, FeatureAttribute — описание атрибута объекта.

Таким образом у нас очень много объектов и значений атрибутов для них. Всё, что на скриншотах выше, а именно дороги, знаки и перекрестки — это Feature, геообъект. Также каждый геообъект имеет версию, и она обновляется при каждом его изменении, будь то обновление геометрии или значения атрибута. Что делать с этим дальше?

Расширяем дороги

Мы не храним всю дорогу целиком, а как бы разрезаем её на маленькие кусочки произвольного размера  — на звенья дорожной сети. Это необходимо для решения таких задач как: установка запрещенных маневров на перекрёстке, распространение зон действия дорожных знаков, установка уровня пробок и многих других. И каждый такой кусочек — отдельный геообъект со своими атрибутами.

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

Красная линия  — наше звено для генерации дорожного полотна
Красная линия — наше звено для генерации дорожного полотна

Как мы это делаем↓

  1. Мы ищем соседние звенья, потому что каждое из них по своему влияет на конечный результат. 

Это критически важно, так как неучтённые соседние звенья могут привести к тому, что дорожные полотна в результате будут накладываться друг на друга или не стыковаться должным образом. Для этого мы берём основное звено и все звенья в радиусе 40 метров и строим из них дорожный узел. Дорожный узел это начальный и конечный сегмент основной дороги, а также сегменты дорожных звеньев, примыкающих к основной дороге слева, справа и посередине в начальной и конечной точках. Схематично его можно изобразить так:

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

  1. Строим буфер вокруг дорожного узла с использованием метода Buffer(double distance, int quadrantSegments, EndCapStyle endCapStyle) из библиотеки NetTopologySuite. Получается такое: 

Буфер вокруг дорожного узла без скруглений
Буфер вокруг дорожного узла без скруглений

В реальности дорога так не выглядит, особенно это заметно, если обратить внимание на прямой угол A.

3. Поэтому следующий шаг скругление. Для этого определяем, какие углы являются внутренними (A), а какие внешними (B,C), чтобы избежать лишней работы, поскольку внешние углы скругляются на этапе построения буфера дорожного узла. 

А вот с каждым внутренним углом поступаем так:

  1. Строим окружность, вписанную в угол.

  2. Рассчитываем сектор окружности и извлекаем из него дугу.

  3. В качестве скругленного угла используем извлечённую дугу.

И в завершении обрезаем буфер со скругленными углами по краям обрабатываемого звена. Для этого выполним несколько шагов:

  1. Ограничиваем построенный буфер основной дорогой.

  2. На основе геометрии соседних звеньев и углов между ними, мы получим линии разреза.

  3. При помощи метода Difference(Geometry other) из библиотеки NetTopologySuite вычитаем из буфера линии разреза и берём самый большой по площади полигон.

В итоге рассчитав буферы, скруглив углы и обрезав получившие полигоны для каждого звена, входящего в перекрёсток, получаем такой результат:

Выделенный участок красным — кусочек дорожного полотна для основного звена из примера
Выделенный участок красным — кусочек дорожного полотна для основного звена из примера

Рисуем разметку

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

  1. Дорожные звенья (сплошная, прерывистая и другая продольная разметки).

  2. Знаки «стоп-линия» и «движение без остановки запрещено» (разметка стоп-линии).

  3. Знак направления движения по полосам (разметка движения по полосам).

  4. Знак «искусственная неровность» (разметка «искусственная неровность»)

  5. Знаки «полоса для маршрутных транспортных средств» и «дорога с полосой для маршрутных транспортных средств» (линейная и точечная разметки для обозначения полосы маршрутных транспортных средств).

  6. Остановка общественного транспорта (разметка остановки общественного транспорта).

Все вышеперечисленные объекты могут быть созданы как вручную, так и автоматически (об этом в следующем разделе). Но на дорогах мы встречаем и другие типы разметок, например, те же островки безопасности. Их мы создаём полуавтоматически, то есть картограф рисует контур, а штриховка заполняется автоматически.

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

Метод Generate() класса RoadMarkingGenerator возвращает нам коллекцию разметок, сгенерированных при вызове каждого подходящего генератора.

Если возьмём звено из примера с дорожном полотном, то получим следующее:

Так у нас появилась одна разметка «стоп-линия», созданная из соответствующего знака, и три разметки, разделяющие полосы движения, созданные из дорожного звена.

А что делать с актуализацией?

Получили дорожные звенья, нарисовали разметку — всё? Неа, всё хорошо только до того момента, пока мы не вспоминаем, что звенья, знаки и прочие геообъекты постоянно меняются. Получается нам нужен сервис для непрерывного наблюдения и сбора изменений геообъектов и их отправки в актуализатор дорожных полотен и разметки.

Этим сервисом стал ChangesRefresher. Ниже схема пайплайна получения и обработки данных:

Схему можно разделить на четыре условные части — база данных, отправитель, шина данных и потребители. Немного про то, как устроено хранение, я уже писал, поэтому сейчас фокус на оставшихся трёх составляющих.

Отправитель (ChangesRefresher)

Этот сервис раз в N секунд опрашивает БД на наличие новых версий геообъектов при помощи ChangesProcessor, используя ChangesProvider для доступа непосредственно к БД. И при появлении новых изменений отдаёт их в ProducerMediator, где внутри специализированные обработчики изменений такие как RoadbedProducer, RoadMarkingProducer и другие фильтруют, подготавливают и отправляют в RabbitMQ полученные из БД изменения под каждого получателя. Каждый такой обработчик работает с собственной копией коллекции изменений геообъектов, поэтому вносимые изменения отдельно взятого обработчика не влияют на остальных.

Маршрутизация сообщений (RabbitMQ)

Отправитель и потребитель ничего не знают друг о друге напрямую. Это позволяет гибко добавлять новых потребителей и при этом не мешать уже существующим. Для конфигурации нового потребителя достаточно задать его имя и приоритет обработки изменений. Делается это один раз при старте сервиса отправителя. А уже потребитель, зная своё имя очереди, периодически опрашивает шину данных на предмет получения уже подготовленных для обработки данных. На схеме видно, что в брокере сообщений как раз имеются несколько очередей — road_marking_changes и roadbed_changes под каждого потребителя отдельно.

Потребители (RoadbedRefresher, RoadMarkingRefresher)

Потребители отвечают непосредственно за обновление, создание и удаление геообъектов. Для получения изменений используются MessageReceiver настроенные на соответствующие очереди. На архитектурной схеме выше указаны два потребителя — актуализаторы дорожных полотен и дорожной разметки. Они-то и вызывает всю ту логику, что была описана в двух предыдущих разделах.

Результаты

К настоящему моменту мы с картографами создали уже вот столько данных (в скобках указаны номера разметок из ПДД):

Тип геообъекта

Актуализируется автоматически

Актуализируется вручную

Дорожные полотна

7500 км²

300 км²

Линейная разметка

379510 км

23290 км

Прерывистая (1.5)

297000 км

15300 км

Сплошная (1.1)

63000 км

4400 км

Двойная сплошная (1.3)

12800 км

2100 км

Места остановки общественного транспорта (1.17.1)

4500 км

710 км

Искусственная неровность (1.25)

1250 км

10 км

Стоп-линия (1.12)

540 км

160 км

Штрих-сплошная (1.11)

420 км

610 км

Точечная разметка

450000 шт

71700 шт

Направление движения по полосам (1.18)

368000 шт

58000 шт

Специальная полоса для общественного транспорта (1.23.1)

82000 шт

13700 шт

Площадная разметка

-

3.25 км²

Вафельная (1.26)

-

0.15 км²

Островки безопасности (1.16.1-1.16.3)

-

3.1 км²

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

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

Сегмент карты, которую увидят пользователи
Сегмент карты, которую увидят пользователи

По предварительной оценке наличие автоматической актуализации дорожной разметки и полотен сократит объём ручной работы на 20-30%.

Что дальше?

Текущая система автоматической генерации реалистичных объектов — по сути MVP. Она хорошо справляется с большинством тривиальных кейсов, но сталкивается с проблемами при обработке сложных развязок с большим количеством стыкующихся звеньев, что требует последующей ручной доработки. Постепенно будем усовершенствовать алгоритмы генерации, чтобы уменьшить объём необходимой ручной работы.

Если у вас остались вопросы, буду рад ответить в комментариях. А если захотите работать с нами — в команде Fiji открыта вакансия разработчика.

Комментарии (11)


  1. CitizenOfDreams
    07.05.2024 09:16

    Мы добавили реалистичные дороги в навигатор 2ГИС.

    Чтобы что? Реалистичную дорогу с реалистичными машинами я и так вижу за лобовым стеклом. А на карте навигатора я хочу видеть схематичное изображение дороги - по той же причине, по которой на дорожном знаке "обгон запрещен" рисуют схематичные плоские силуэты автомобилей, а не их реалистичное изображение в 3D.


    1. Termeh Автор
      07.05.2024 09:16
      +4

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


      1. pewpew
        07.05.2024 09:16

        Тогда почему автомобиль размером с трёхэтажный дом и занимает на дороге четыре полосы?


        1. Termeh Автор
          07.05.2024 09:16

          Сейчас это просто замена стандартного курсора. Пользователь может сменить синий треугольник на модельку, которая ему кажется более интересной. По ссылке из начала статьи можно посмотреть примеры как это может выглядеть.


  1. SpiderEkb
    07.05.2024 09:16
    +3

    Подобный сервис видел в гарминовских автонавигаторах еще в 2014-м году. Касалось это разного рода развязок - подъезжаешь к развязке и на полэкрана она рисуется в "реалистичном виде" - так, как ее видно через лобовое. С всеми знаками движения по полосам и в какой полосе тебе ехать нужно. Очень наглядно и удобно.

    Работало, естсетсвенно, только с официальными картами от гармина. Если делать самому из OSM, то там такого не было.


  1. piton_nsk
    07.05.2024 09:16

    Для хранения данных мы используем EAV-модель.

    Но зачем?


    1. Termeh Автор
      07.05.2024 09:16
      +1

      Честный ответ - так исторически сложилось. И это очень удобно с точки зрения добавления новых поддерживаемых геообъектов. Но сейчас с этим есть ряд проблем от производительности до сложности запросов.

      У нас в бэклоге есть задачи по переводу сущностей в реляционную структуру, думаю в обозримом будущем займемся этим.


      1. Ivan22
        07.05.2024 09:16

        а почему в модели кольцевая связь? ну то есть 2 пути от value до feature ??? И по какому ходить?


  1. OptimumOption
    07.05.2024 09:16

    А ямы и колдобины на дорогах тоже будут отображаться, или где? :-D


    1. Termeh Автор
      07.05.2024 09:16

      Это был один из первых вопросов на внутренней презентации фичи :)

      У нас есть наработки по распознаванию качества дорожного покрытия, работает на основе того, о чем мы писали тут https://habr.com/ru/amp/publications/457342/. Так что кто знает..


  1. OlegCh4elovek
    07.05.2024 09:16

    Интересная статья, спасибо!