Сотрудники факультета ВМК МГУ имени М.В. Ломоносова представили подход к решению задачи построения маршрутов на пересеченной местности и дискретизации географического ландшафта с помощью графа видимости. Традиционно системы построения маршрутов находят путь по графу дорог, однако задача поиска маршрутов, проходящих вне дорог, также актуальна.
В настоящее время значительное количество информации хранится в электронном виде: существуют различные электронные карты (Яндекс Карты, Google Карты, OpenStreetMap) и средства работы с ними. Одна из актуальных задач – это построение маршрутов. Однако существующие картографические и навигационные сервисы предоставляют возможность прокладывать путь между заданными точками либо по автодорогам и тротуарам, либо по проселочным и грунтовым проездам. В то же время часто возникает необходимость навигации по бездорожью. Например, это нужно при планировании туристических маршрутов и спасательных операций, строительстве автомобильных и железных дорог, прокладке коммуникаций для эффективного использования территориальных и природных ресурсов.
Учёные факультета ВМК МГУ предложили алгоритм аппроксимации многоугольников при решении задачи навигации на пересеченной местности с помощью построения графа видимости для множества многоугольников, задающих природные объекты. Недостаток данного алгоритма – фиксированная структура данных для хранения многоугольника.
В качестве наглядного примера исследователи предложили построить маршрут длиной в несколько тысяч километров. «Граф дорог такой территории может содержать настолько большое количество вершин и ребер, что пользователю придется ждать результата вычислений не один час, в особенности, если вычисления производятся на локальной машине. Для решения данной проблемы на графе дорог обычно применяется иерархический подход», – рассказала доцент кафедры алгоритмических языков факультета ВМК МГУ Юлия Корухова.
Для построения такого маршрута участок будет предварительно разбит на три части: путь от начальной точки до автомагистрали, путь по автомагистралям, путь от автомагистрали до конечной точки. Стоит отметить, что этот путь не всегда будет кратчайшим.
«В рассматриваемой нами задаче навигации по пересеченной местности количество вершин графа видимости будет в тысячи раз больше, а количество ребер – в миллионы, так как на указанной территории будут рассматриваться не только дороги, но и природные объекты», – добавил студент кафедры алгоритмических языков факультета ВМК МГУ Денис Козуб.
Здесь также будет применяться иерархический подход: отдельными кластерами будут выступать графы видимости на территориях между начальными и конечными точками и графом дорог. Именно на этих участках задача навигации по пересеченной местности стоит наиболее остро. При этом в построении всего графа видимости по словам учёных нет необходимости: будет рассматриваться лишь геометрия на указанных участках. Упомянутые два кластера, в свою очередь, также могут быть в дальнейшем разбиты на локальные кластеры меньшего размера – в местах, где сконцентрировано наибольшее количество природных объектов.
В представленном выше подходе иерархический метод будет полезен и в работе с геометрией природных объектов. В зависимости от размера территории, где проводится поиск кратчайших путей, или в зависимости от размера кластеров, на которые разбивается граф видимости, геометрия объектов может быть упрощена.
Указанные подходы к построению маршрутов на пересеченной местности были программно реализованы на языке Python. В качестве географических данных использовались открытые данные OpenStreetMap. Программный интерфейс позволяет скачивать, обрабатывать и сохранять географические данные, строить граф видимости, производить построение маршрутов на пересеченной местности, экспортировать и визуализировать результаты.
Результаты исследования были представлены на Всероссийской конференции «Научный сервис в сети Интернет».