Как посмотреть пробки на дорогах в 2 гис

Использование квадродеревьев при расчёте пробок 2ГИС

Даже не являясь навигатором, 2ГИС собирает и показывает информацию о пробках. Во-первых, это необходимо для построения оптимальных маршрутов, а во-вторых — такие данные очень нужны пользователям в больших городах.

В 2ГИС сервис пробок появился в сентябре 2011 года и сегодня работает в пяти городах (Новосибирск, Санкт-Петербург, Красноярск, Уфа, Казань). В планах на ближайшее будущее — запустить пробки во всех городах-миллионниках.

идентификатор проекта(города);
время регистрации;
координаты;
моментальная скорость;
направление движения в момент регистрации.

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

Таким образом, притяжка точек — процесс соотнесения каждой точке участка дороги, на котором она была зарегистрирована, с учётом её скорости и направления движения.

Давайте возьмём одну точку (рисунок a), и попробуем определить, на каком участке дороги она была зарегистрирована.

Понятно, что нужный участок дороги где-то рядом с точкой, поэтому сразу встаёт задача поиска ближайшего сегмента дорожной сети в некотором радиусе (например, 20 метров).

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

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

Что было раньше

Изначально, не было задачи считать онлайн-пробки, а была задача обработать данные за месяц с тем, чтобы в наших офлайн-продуктах выставить среднемесячные скорости по дорогам и более реалистично показывать время проезда.
Данные от поставщиков агрегировались в центральном хранилище.

На этапе подготовки вокруг всех ребер графа строились полигоны (функция ST_Buffer), ширина (разная для разных классов дорог) которых определяла допустимое отклонение.
Точка проверялись на попадание в эти полигоны и выбирались допустимые ребра.
На все допустимые ребра строилась проекция точки (функция ST_ClosestPoint) и мы получали сортировку допустимых ребер по расстоянию.
Используя сортировку по расстоянию, проверяя азимут точки и азимут сегмента ребра, класс и ширину дороги и предыдущие притянутые точки от данного устройства мы определяли вероятное ребро графа и проекцию точки на это ребро считали притянутой точкой и записывали в базу.

На среднем сервере, скорость получалась около 2 000 точек в секунду.

C появлением режима «Онлайн» этого решения стало недостаточно: данные обновляются каждые пять минут, так что полный цикл обработки данных должен укладываться в это время. С увеличением объёма данных этот этап стал выполняться настолько долго, что вписать в пять минут весь цикл было затруднительно даже на весьма мощном «железе».

Пришло время реализовать уже давно назревавшую идею — реализация расчётов на C++.

Поиск быстрых решений

Параллельно мы начали разрабатывать 2 решения — одно на основе библиотеки GEOS, а второе на полностью с нуля на основании квадродеревьев.

О GEOS

Это решение появилось первым, так как использовало готовую библиотеку GEOS, которую, кстати, использует и PostGIS.

Для поиска ближайших сегментов использовались Quadtree индексы из этой библиотеки.

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

Собственная реализация квадродеревьев

Эта реализация появилась второй, но (немного забегая вперед) получилась немного более удачной.

Сначала несколько общих определений, чтобы добавить ясности.

Квадродерево — это дерево, в котором каждый внутренний узел имеет четыре потомка.
Квадродерево позволяет рекурсивно разбить двухмерное пространство на четыре квадранта (области).

Квадродеревья способны хранить информацию о разных типах данных, однако нас интересует хранение сегментов(отрезков), поскольку дорожную сеть можно просто представить именно с помощью сегментов.

Для этого мы использовали оптимизированную для хранения сегментов версию PM Quadtree — Polygonal Map Random Quadtree.

Использует вероятностное правило разбиения;
Каждый узел содержит переменное количество сегментов;
Каждый сегмент вставляется во все узлы, которые пересекает;
Если узел содержит количество сегментов, превышающее ограничение, то происходит разбиение(только однажды) на 4 дочерних узла;
Хорошо подходит для задачи поиска ближайшего сегмента.

Возможна разбалансировка дерева.

Глубину;
Координаты области;
Четыре потомка, если узел внутренний;
Сегменты, если узел внешний.

Построение

Построение структуры данных представляет собой процесс последовательной вставки сегментов в дерево. Изначально дерево пустое.
Аналогично алгоритмам построения многих других иерархических структур данных, алгоритм построения PMR Quadtree основан на обходе сверху-вниз (top-down traversal). Другими словами, начиная с корневого узла мы посещаем все дочерние узлы, пересекающиеся с сегментом, и добавляем этот сегмент во все встретившиеся внешние узлы.

Ключевой аспект PMR Quadtree — правило разбиения, то есть условие, при котором узел делится. Для этой цели используется некоторый параметр t, ограничивающий количество сегментов, которое может содержаться в узле.
Если количество сегментов, которое пересекается с областью, превышает t и если не достигнут максимальный уровень глубины, то эта область делится на четыре дочерних, а все сегменты, которые с ним пересекались, вставляются в новые дочерние узлы. Стоить заметить, что сразу после разбиения дочерние узлы не разбиваются снова, даже если количество сегментов в узле превышает t. Это позволяет избежать чрезмерного разбиения и приводит к вероятностному поведению в том смысле, что порядок, в котором объекты вставляются, влияет на структуру полученного дерева.

Визуализация

Поиск в дереве

внутренние узлы;
внешние узлы;
сегменты.

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

Сравнение

Сравнив реализацию на GEOS и собственную, мы были приятно удивлены:
На одном и том же железе для 300 000 сегментов:

GEOS	PMR Quadtree
Построение дерева	2 секунды	0,2 секунды
Потребление памяти	200 Мб	50 Мб
Притяжка точек	35 500 точек в секунду	383 500 точек в секунду

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

Заключение

В итоге, перейдя от PostGIS к узкоспециализированному решению на C++, мы получили ускорение с 2к до 380к (в 190 раз).

Пишите узкоспециализированные велосипеды!

Как работает сервис пробок, можно посмотреть прямо сейчас, или установив 2ГИС на iOS, или Android.

Как смотреть пробки в 2ГИС

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

Как проверять загруженность дорог в Google Maps

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

Также в Google Maps можно добавить точки на карте, чтобы узнать о пробках на разных участках маршрута.

Как проверять пробки по времени в 2ГИС

В правом верхнем углу карточки города в 2ГИС нажмите кнопку с цифрой.
На карте отобразится степень загруженности дорог, а слева откроется боковое меню.
В строке «Дорожная ситуация» выберите временной промежуток: «Сейчас» — на карте отобразится актуальная дорожная ситуация и значки с прогнозом загруженности дорог на ближайшие часы.

Как на картах отображаются пробки

Google Maps использует цвет для отображения степени загруженности дорог. Зеленый цвет означает безопасную скорость движения, желтый — ограниченную скорость движения, а красный — значительное замедление или наземная пробка.

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

Как работают пробки в 2ГИС

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

Полезные советы и выводы

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

Как посмотреть в 2ГИС пробки

Если вы хотите узнать уровень загруженности дорог в 2ГИС, то нужно обратить внимание на круглую кнопку в правом верхнем углу карты. Если сервис «Пробки» доступен в вашем городе, то на кнопке будет отображаться цифра, которая показывает уровень пробок на данном участке. Если нажать на кнопку, то цвет кнопки изменится в зависимости от уровня загруженности, а также дороги на карте будут подсвечиваться красным, жёлтым или зелёным цветом, что также позволит оценить уровень пробок на дорогах. Благодаря данной функции пользователи могут выбирать оптимальный маршрут, чтобы добраться до места назначения быстро и без проблем.

Как включить слои в 2ГИС

Для того чтобы включить слои в приложении 2ГИС, нужно нажать на кнопку «Параметры», расположенную в правом верхнем углу экрана программы. После этого выберите в появившемся меню пункт «Дополнительные модули». Откроется окно со списком всех подключенных модулей. Если вы хотите настроить какой-то модуль, щелкните на кнопке «Настроить». Там вы сможете изменить настройки подключенного модуля. Если вы хотите включить или выключить какой-то модуль, найдите необходимый модуль в списке и переключите переключатель на вкладке «Состояние». Теперь вы можете настроить отображение карты в 2ГИС при помощи доступных слоев.

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

Как посмотреть пробки на дорогах

Информация о пробках доступна пока не во всех городах присутствия 2ГИС, но мы всё время работаем над тем, чтобы таких городов стало больше.

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

Если такой кнопки нет, значит сейчас открыт участок карты, где данными о пробках мы пока не располагаем.

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

Сервис «Пробки» 2ГИС в Алматы

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

По каждому проблемному участку можно получить дополнительную информацию о скорости потока машин. Данные обновляются каждые 5 минут.

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

Информация о дорожном движении в Алматы доступна в мобильной и онлайн-версии 2ГИС.

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