Кто-нибудь знает, какой тип алгоритма используется в инструменте ArcGIS Watershed (в пакете Spatial Analyst)?
На сайте Esri очень мало информации ... но я подозреваю, что это может быть какой-то поиск по глубине / ширине.
Я посмотрел на следующих страницах справки ArcGIS Online:
Так что да, он использует растр направления потока, но какой алгоритм он использует для обхода растра?
Обратите внимание, я не ищу ответы в духе «он использует D8 ..». D8 на самом деле не алгоритм, а модель, помогающая определить алгоритм, который вы бы использовали. То есть вы могли бы реализовать схему D8 в алгоритме поиска в глубину и / или в алгоритм поиска в ширину
Ответы:
Метод, который я реализовал на нескольких языках и считаю, что ESRI использует (извините, никаких ссылок, кроме Дженсона и Доминге, процитированных в другом месте на этой странице), состоит в том, чтобы начать с предоставленной пользователем ячейки "точки застывания" или ячейки на краю сетки направления потока (fdr), исследуйте ее восемь соседей, чтобы найти, какой из этих прямых течет в текущую ячейку, и назначьте эти ячейки текущему «водоразделу» в выходной сетке. Затем функция рекурсивно вызывает себя один раз для каждого из входящих соседей. Этот процесс повторяется до тех пор, пока все входящие клетки не будут исчерпаны для точки застывания, а затем будет повторяться для всех точек застывания.
Проектирование рекурсивного алгоритма может быть довольно дорогим, потому что в конечном итоге он может пытаться удержать много данных в памяти, вынужден перенести страницу на диск и, как правило, испытывать замедление ввода-вывода.
(см. ниже комментарий Вубера о различных методах рекурсии, если вы собираетесь RYO)
_____________ РЕДАКТИРОВАТЬ _____________
В качестве примера выкопали мой старый C-код (примечание: хотя большинство питонеров могут захотеть бежать из комнаты, это не должно быть слишком плохо). Думаю, это может быть интересно проиллюстрировать. Несмотря на то, что я только сейчас поверхностно знаком с рекурсией в ширину и глубиной, я думаю, что моя рутина действительно в глубину (и что мое описание на естественном языке выше вводит в заблуждение), основываясь на этой публикации в стеке (надеюсь, @) whuber или другой человек умнее меня может подтвердить / опровергнуть).
Код: объяснение:
idir
это растр значений направления потока.offset
относится к центральной ячейке, которая в настоящее время анализируется, иoff
проверяет каждого из соседей этой ячейки. Это вызывает другую функцию,does_it_flow_into_me
которая возвращает логическое значение относительно того, указывает ли flowdir соседней ячейки на текущую ячейку. Если верно для соседа, вернитесь в это место.источник
ArcGIS помощь говорит:
Направление потока вычисляется из матрицы высот, используя метод D8 , где поток отводится путем расчета для каждой ячейки, в которую из 8 соседей будет течь вода из этой ячейки.
Существует много альтернатив D8, таких как Rho8, Froh8 и Stream Tubes, но большинство программ ГИС, включая ArcGIS, склонны использовать D8, поскольку он проще и менее требователен к вычислениям, чем другие.
Несколько лет назад я работал над проектом разграничения водоразделов, и мы столкнулись с несколькими проблемами из-за того, что ArcGIS использовал метод D8. Две основные проблемы были
Из наших данных мы знали, что эти две проблемы были большими проблемами, поэтому я разработал некоторые инструменты для генерации направлений потока с использованием гибридных методов.
Одной из моих самых ранних задач была реинжиниринг инструмента расчета водосбора. Я обнаружил, что это было логически довольно просто. Если вы хотите найти водосбор для данной точки (также называемой точкой застывания), вы сначала находите ячейку, в которой он находится. Часто вы пытаетесь привязать его к точке с наибольшим накоплением потока в заданном допуске.
Для этой клетки вы найдете все клетки в окрестности, которые способствуют этому. Для каждой из этих соседних ячеек вы найдете ячейки, которые способствуют им, и так далее. Вы продолжаете этот итеративный процесс, пока не найдете новые ячейки. Вот когда вы достигли линий хребта или границы водораздела.
Я обнаружил, что мой простой код, который делал это для растров ASCII, выдает почти аналогичный результат по сравнению с инструментом ArcGIS Watershed. Иногда раньше было несколько ячеек на границе, поэтому я убежден, что ArcGIS следует неизменному алгоритму D8.
источник
Об этом уже спрашивали , хотя, возможно, в несколько ином контексте. Все инструменты геообработки в наборе инструментов гидрологии Spatial Analyst используют модель направления потока D8 , как указано на странице Как работает направление потока :
Копия статьи Дженсона и Доминге (1988) доступна здесь .
Все инструменты, которые используют растры направления потока в качестве входных данных, используют эту модель направления потока по ассоциации. Это включает в себя водосбор, накопление потока, длину потока, заполнение и т. Д.
источник
Чтобы больше обдумать этот вопрос, я провел анализ водораздела по дуге: я взял (заполненную) матрицу высот, рассчитал направление потока и поместил несколько точек, которые соответствуют местоположениям в ранее рассчитанной сети потоков. Я запустил инструмент «водораздел», и он дал мне несколько хороших бассейнов, в значительной степени покрывающих большую часть оставшейся области «вверх по течению» (как и следовало ожидать):
Затем я запрограммировал алгоритм быстрого поиска в Python (как ответ выше), который проверяет сетку направления потока и «следит» за путями потока. Для каждого узла я проверяю 8 соседей и, если соседний поток входит в текущий узел, я рекурсивно вызываю ту же функцию с соседним узлом в качестве входного.
Псевдо (ish) код:
Я запустил эту функцию, используя ту же сетку ввода направления потока и одну и ту же точку. Проблема в том, что когда дуга возвращает 40000 ячеек для этой точки, мой алгоритм просто возвращает 72 ячейки.
Кто-нибудь знает, что я делаю не так?
источник