Що таке дорожній граф і як будуються маршрути на Яндекс.Картах

команда Яндекс.Карт розповіла , Як працює маршрутизація на Яндекс.Картах.

Нагадуємо, вчора було оголошено масштабне оновлення Яндекс.Карт - на них з'явилися докладні схеми більшості країн світу:

За цим проектом стоїть не просто нанесення на карту нових об'єктів, але перш за все технологічна основа, яка дозволяє зберігати, швидко обробляти і оновлювати картографічні дані. Технологія побудови маршрутів - одна з найцікавіших, використовуваних сервісом Яндекс.Карти. Головні складові маршрутизації - це дорожній граф і алгоритм, який розраховує маршрут.

Дорожній граф - це сітка доріг. Вона складається з безлічі фрагментів, які зістиковано між собою. Кожен з них несе інформацію про свою ділянку дороги: географічні координати, напрямок руху, середня швидкість, з якою машини зазвичай їдуть на цій ділянці, і інші параметри. Кожен фрагмент містить також дані про те, як він стикується з сусідніми ділянками - чи є в цьому місці поворот направо або наліво, чи можна там розвернутися у зворотний бік або дозволяється їхати тільки прямо.

Само собою, дорожній граф можна зробити раз і назавжди. Транспортна система міста має звичай змінюватися, тому, щоб не відставати від життя, Яндекс регулярно оновлює дані.

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

Маршрут Яндекс.Карти розраховують по алгоритму Дейкстри . З його допомогою система обчислює найшвидший варіант проїзду - виходячи з довжини кожного відрізка графа і швидкості руху на цій ділянці. Якщо користувач будує маршрут проїзду без урахування пробок, то алгоритм використовує середню швидкість руху на ділянці. А якщо користувач хоче знати, як найшвидше дістатися до місця з урахуванням ситуації на дорозі, то алгоритм задіє дані про поточну ситуацію на дорозі.

Детальніше про побудову маршрутів читайте в блозі Яндекса