Время прочтения: 5 минут
Версия QGIS: 3.40
Уровень владения QGIS: начинающий
Уровень владения QGIS: начинающий
В этой статье мы узнаем, как производить в QGIS расчет наименьшего стоимости пути между точками, что учитывать при подготовке данных для этого расчета и какой алгоритм можно использовать при решении практической задачи по поиску оптимального пути для Хоббита, чтобы скинуть кольцо в жерло вулкана.
Анализ наименьшей стоимости пути как практическая задача
Анализ наименьшей стоимости пути (least cost path) — это классическая геопространственная задача, в которой мы решаем, как в нашем неоднородном пространстве проложить путь между точками для какой либо цели, будь это просто передвижение на своих двоих или же строительство дороги или нефтепровода.
Так уж случается, что прямая линия между точками — часто не такой оптимальный путь, как это может показаться на плоском листе бумаги. Путь между двумя объектами может быть затруднен различными факторами: рельефом, неблагоприятными экономическими условиями, особенностями ландшафта или чем-то иным.
Базовая информация
Анализ наименьшей стоимости пути мы будем проводить в QGIS с помощью модуля «Least-cost path». Его можно установить стандартным способом через вкладку «Модуль» на панели инструментов, после чего выбираем «Управление модулями», ищем «Least-cost path» и устанавливаем его. Модуль рассчитывает наименьшую стоимость пути по алгоритму Дейкстры.
Для работы модуля, а значит и для решения задачи нам нужны следующие вещи:
- растровый слой стоимости пути (Cost raster band), в котором значение пикселей должно быть значением стоимости пути. Оно не обязательно должно быть вединицах времени, если вам нужно просто найти оптимальный путь из точки А в точку Б.
- слой со стартовой точкой (Start-point layer).
- слой с конечной точкой (End-point layer).
Необязательно, чтобы в слоях со стартовыми и конечными точками было по одной точке. Их может быть много, и при необходимости можно выделить нужные точки в слоях.
Пример решения задачи
Как работать с алгоритмом, покажу на примере нахождения пути между Широм и Мордором для Фродо с его задачей отнести кольцо. Этот инструмент ему явно мог бы помочь выполнить задачу быстрее и легче, в условиях, когда он не мог воспользоваться сервисом для покупки дешевых авиабилетов… Эх, такая интеграция могла быть.
Для примера я воспользуюсь датасетом «GIS and Middle earth», который можно скачать по ссылке. Этот датасет как раз был разработан для того, чтобы научить студентов работать с алгоритмом анализа наименьшей стоимости пути. В нем есть цифровая модель рельефа Средиземья, а также векторные слои с дорогами, населенными пунктами и иными объектами.
Начальная точка у нас будет Шир, конечная — Роковая гора. С этим все просто и понятно, а вот как создать растровый слой стоимости пути? Сейчас покажу на простом примере, где в качестве фактора, влияющего на стоимость пути, будет крутизна склона. Чем круче рельеф, тем больше стоимость пути, логическая связь между значениями уклона стоимости пути присутствует, но вам никто не мешает усложнять.
Подготовка растрового слоя стоимости пути
Важно! При создании растровых слоев и подготовки растрового слоя стоимости пути помните, что у вас не должно получиться отрицательных значений.
Как я уже говорил ранее, наша цифровая модель рельефа Средиземья весит много гигабайт, что заставит наш алгоритм расчета пути умереть, поэтому проведем ресэмплинг и сделаем так, чтобы один пиксель был не 50 метров, а, например, 5000.
Теперь можем вычислять крутизну склона, которая скрывается на панели инструментов по пути «растр» — «анализ» — «крутизна».
Строим крутизну склона и получаем вот такой слой. Настройки выставляем стандартные, никаких дополнительных галочек не нажимаем, чтобы получить крутизну в градусах. Стоит помнить, что слой после ресэмплинга, то есть реальные уклоны могут отличаться, причем существенно (в этом примере, например, они уменьшились в некоторых местах более чем в 4 раза), а также менее заметные артефакты в растровых данных в виде пропущенных значений могут увеличиваться в размерах.
Рассчитываем самый короткий путь
Теперь перейдем к расчету стоимости пути. Для начала в слое «Towns» я выберу Шир, место, откуда Фродо начал свое путешествие, а в слое «Buildings» — ту самую башню, в которую нужно было отнести кольцо. После этого на панели «Инструменты анализа» ищем наш модуль «Least-cost path».
Выбираем в «Cost raster band» наш слой с крутизной, в начальной точке выбираем слой «towns» и ставим галочку «Только выделенные объекты». С конечной точкой выполняем аналогичную операцию, после чего нажимаем «выполнить».
Как можно точнее рассчитать путь Хоббитов
Анализ наименьшей стоимости пути можно развить до мультифакторного варианта и дополнить его дополнительными критериями, что и сделали студенты, выполнявшие эту лабораторную работу в ArcGIS. Примеры выполнения задания можно найти по ссылке. Для анализа наименьшей стоимости они использовали, например, следующие факторы:
- фактор дорог. Гэндальф в самом начале произведения говорит Фродо держаться подальше от дорог;
- территории, которые видит око Саурона;
- большее использование информации об объектов Средиземья, которые влияют на передвижение: форты, реки, территории союзников и территории врагов.
Если вдруг займетесь этим, то обязательно поделитесь в комментариях!
Материал подготовил Александр Зуев