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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Строим буфер вокруг дорожного узла с использованием метода 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 настроенные на соответствующие очереди. На архитектурной схеме выше указаны два потребителя — актуализаторы дорожных полотен и дорожной разметки. Они-то и вызывает всю ту логику, что была описана в двух предыдущих разделах.

Результаты

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

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

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

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

Что дальше?

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

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