Решение задачи построения маршрута движения по пересеченной местности предложили сотрудники факультета вычислительной математики и кибернетики (ВМК) МГУ, сообщает 8 декабря пресс-служба университета.

Ученые ВМК МГУ расширили существующие методики построения маршрутов на основе графа дорог разработанным методом построения маршрутов, проходящих вне дорог, и дискретизации географического ландшафта с помощью графа видимости.

В настоящее время существует множество различных электронных карт, в их числе Яндекс Карты, Google Карты, OpenStreetMap и другие, а также средства работы с ними, предусматривающие, в том числе, построение маршрутов.

При этом предлагаемые пользователю картографические и навигационные сервисы прокладывают путь между заданными точками по автодорогам и тротуарам или же по проселочным и грунтовым дорогам.

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

Для решения таких задач ученые факультета ВМК МГУ взяли за основу алгоритм аппроксимации многоугольников с помощью построения графа видимости для множества многоугольников, задающих природные объекты. Однако недостатком этого алгоритма является фиксированная структура данных при хранении многоугольника.

Демонстрируя этот недостаток, ученые предложили построить данным методом маршрут в несколько тысяч километров длиной.

«Граф дорог такой территории может содержать настолько большое количество вершин и ребер, что пользователю придется ждать результата вычислений не один час, в особенности, если вычисления производятся на локальной машине», — отметила доцент кафедры алгоритмических языков факультета ВМК МГУ Юлия Корухова.

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

Студент кафедры алгоритмических языков факультета ВМК МГУ Денис Козуб пояснил особенности построения маршрута для движения по пересеченной местности:

«В рассматриваемой нами задаче навигации по пересеченной местности количество вершин графа видимости будет в тысячи раз больше, а количество ребер — в миллионы, так как на указанной территории будут рассматриваться не только дороги, но и природные объекты».

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

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

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

Вышеописанные методы построения маршрутов на пересеченной местности ученые реализовали на языке программирования Python. Исходными географическими данными стали открытые данные OpenStreetMap.

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

Результаты исследования своего метода разработчики представили на Всероссийской конференции «Научный сервис в сети Интернет».