НовостиNews - ПоискSearch - ТекстыTexts - ФотоPhotos - КартыMaps - СнаряжениеEquipment - LTLT

Трассировка рек и хребтов по srtm-данным

В.Завьялов

Тут я попробую описать некоторые алгоритмы, которые были придуманы уже довольно давно (в 2006 году), но доведены до ума так и не были. Единственное реальное применение, которое было найдено -- схемы рек с уклонами и площадами водосбора, полезные для планирования водных походов.

Я опишу три алгоритма, немного разных, но основанных на одной идее. Найти их реализацию и примеры можно в пакете mapsoft (директории /core/srtm и /misc/srtm_riv).

Общая идея

Общим элементом всех алгоритмов является следующий способ спуска из данной точки вниз (или подъема наверх).

Рассматриваем границу некоторого множества точек. В начале множество состоит из одной исходной точки, а граница -- из 8 ее соседей. Последовательно ищем самую нижнюю точку границы, добавляем эту точку во множество.

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

Нахождение русла реки

• Идем вниз от начальной точки, запоминая последовательность всех пройденных точек.
• Критерием выхода из цикла могут служить следующие условия: счетчик бессточных территорий больше N (мы "затопили" N точек, а стока вниз не нашли); мы ушли за край карты; мы дошли до нужной точки, нужной высоты и т.п.
• После этого делаем обратный проход -- находим русло реки. Начиная от конечной точки, добавляем ту соседнюю точку из списка пройденных, которая была добавлена в него ранее других.

Алгоритм хорош для построения продольного профиля реки. Проблема алгоритма -- непонятно, как разбить его на шаги. Если дважды пройти из одной точки вниз на разное число шагов, то нет гарантии, что одно русло будет подмножеством другого. Это происходит из-за бессточных и плоских территорий, которые могут быть устроены довольно причудливо. Все различия, впрочем, сосредоточены где-то в самом конце.

Нахождение площади водосбора реки

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

Проверка того, что точка p1 сливается в соседнюю точку p2, состоит в следующем. Идем вниз от точки p1. Останавливаемся, либо дойдя до точки p2 (положительный результат) либо дойдя до ранее рассмотренной точки, либо опустившись ниже высоты p2 на некоторую величину (например, 200м), либо превысив некоторе число шагов.

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

Можно сохранить для каждой точки площадь ее водосбора и направление стока и рассортировать все реки.

Алгоритм обратим (как и предыдущий). Можно найти "площадь водосбора" горы, построить хребты. Результат выглядит довольно красиво, однако результат (и скорость) сильно зависит от ограничения на размер бессточных территорий: хребты разбиваются на "бессточные" куски, впрочем, довольно логичные. Большие бессточные куски обрабатываются очень долго.

(Время счета этих картинок: 25.5 с для реки, 7.2с для хребта. Здесь и далее черным цветом обозначены точки с площадью водосбора более 0.5 км^2.)

Построение хребтовки заданного прямоугольного района

• Определяем направление стока в каждой точке карты. Из каждой точки спускаемся методом трассировки русла, описанным в начале, останавливаемся при дохождении до уже обработанной точки, до края карты или до бессточной точки. В каждой точке запоминаем направление стока (например, -1 - не обработана, 0..7 направление, 8 - бессточная).
• Определяем площадь водосбора каждой точки: проходим вниз по направлению стока, начиная от каждой точки, добавляя площадь этой точки ко всем точкам пути.

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

Есть две существенные проблемы (примерно понятно, как их решать, но я этого пока не делал). Во-первых, не учитываются реки, втекающие в карту. Во-вторых, из-за того, что трассировка останавливается в произвольной точке (на границе карты), нет гарантии, что карта хорошо состыкуется с соседней.

(Время счета этих картинок: 6.7с для хребтов, 5.8с для рек)