Представьте, что вы решили прокатиться на электросамокате по Сан-Франциско, доверившись стандартному навигатору. Через пять минут вы прокнимаете всё на свете (примерно как при попытке разобраться в чужом легаси-коде без документации), пытаясь преодолеть вертикальную стену жилого квартала, хотя в двух кварталах правее шла пологая дорога. Обычные карты видят кратчайший путь, но упорно игнорируют законы физики и гравитацию. Прямо сейчас мы исправим этот баг городской инфраструктуры с помощью Python.

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

1. Источники данных: OSMnx и цифровые модели рельефа

Для построения графа города нам нужны два компонента: дорожная сеть и данные о высоте. Стандартом де-факто для работы с дорогами в Python является библиотека OSMnx, которая скачивает данные из OpenStreetMap (OSM) и конвертирует их в структуры NetworkX.

Поскольку стандартный OSM не всегда содержит точные высоты вершин, мы обогащаем граф данными о рельефе (DEM):

  • Данные SRTM (Shuttle Radar Topography Mission) или USGS 3DEP.
  • API геокодирования высот (например, Open-Elevation).
  • Локальные растровые GeoTIFF-файлы для быстрого оффлайн-обогащения.

В результате мы получаем трехмерный граф $G(V, E)$, где каждая вершина $v$ помимо координат обладает атрибутом высоты $z$.

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

2. Построение и кастомизация весов ребер графа

Обычный алгоритм Дейкстры или A* ищет путь с минимальной суммарной длиной. Чтобы заставить его искать «плоский» маршрут, нам нужно изменить функцию веса ребер. Учитывать только абсолютный подъем нельзя, иначе алгоритм выберет невероятно длинный обходной путь.

Формула веса ребра должна учитывать как физическое расстояние, так и градиент уклона (slope):

import networkx as nx
import osmnx as ox

# Загружаем граф пешеходной сети Сан-Франциско
G = ox.graph_from_place('San Francisco, California, USA', network_type='walk')

# Пример расчета кастомного веса с учетом уклона
for u, v, data in G.edges(data=True):
    length = data.get('length', 1.0)
    # Получаем высоты вершин (предполагаем, что они уже добавлены)
    z1 = G.nodes[u].get('elevation', 0.0)
    z2 = G.nodes[v].get('elevation', 0.0)
    
    grade = abs(z2 - z1) / length if length > 0 else 0
    
    # Штрафуем крутые подъемы (например, экспоненциально)
    penalty = 1.0 + (grade * 10) ** 2
    data['flat_weight'] = length * penalty

Когда математическая модель рельефа зафиксирована в весах ребер, остается лишь скормить эти данные проверенному поисковику (и надеяться, что он не упал с Out of Memory, как это часто бывает при попытке выгрузить весь город целиком).

3. Маршрутизация с помощью алгоритма A*

Когда веса ребер настроены, задача сводится к классическому поиску пути. Алгоритм A* (A-star) подходит для этого лучше всего благодаря эвристической оценке оставшегося расстояния.

orig_node = ox.nearest_nodes(G, X=-122.4194, Y=37.7749)
dest_node = ox.nearest_nodes(G, X=-122.4082, Y=37.7833)

# Ищем путь по нашему кастомному весу
route = nx.astar_path(G, orig_node, dest_node, weight='flat_weight')

Заключение

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

Откройте свой IDE, подтяните геоданные и попробуйте построить такой анти-холмовый навигатор для своего любимого района уже сегодня!