Alguém sabe que tipo de algoritmo é usado na ferramenta ArcGIS Watershed (no pacote Spatial Analyst)?
Muito pouca informação é fornecida no site da Esri ... mas suspeito que possa ser algum tipo de pesquisa de profundidade / amplitude.
Eu olhei para estas páginas de Ajuda do ArcGIS Online:
Então, sim, ele usa a varredura da direção do fluxo, mas que algoritmo está sendo usado para atravessar a varredura?
Observe que não estou procurando respostas ao longo das linhas de 'ele usa D8 ..' ... D8 não é realmente um algoritmo, mas um modelo para ajudar a definir o algoritmo que você usaria. IE, você pode implementar o esquema D8 dentro de um algoritmo de busca em profundidade e / ou em algoritmo de busca em profundidade
Respostas:
O método que eu implementei em alguns idiomas e acredito que o ESRI usa (desculpe, nenhuma referência além de Jenson e Domingue citadas em outras partes desta página) é começar em uma célula ou célula de "ponto de fluidez" fornecida pelo usuário na borda da grade de direção do fluxo (fdr), examine seus oito vizinhos para descobrir qual fluxo direto entra na célula atual e atribua essas células à "bacia hidrográfica" atual na grade de saída. Então a função se chama recursivamente uma vez para cada um dos vizinhos que estão entrando. Esse processo se repete até que todas as células de entrada estejam esgotadas para um ponto de fluidez e, em seguida, se repete para todos os pontos de fluidez.
O design do algoritmo recursivo pode ser bastante caro, pois pode acabar tentando armazenar muitos dados na memória, tendo que trocar / paginar no disco e, portanto, geralmente sofrer lentidão de E / S.
(veja o comentário do whuber abaixo sobre os diferentes métodos de recursão, se você quiser RYO)
_____________ EDITAR _____________
Desenterrei meu código C antigo como exemplo (observação: embora a maioria dos pythoners deseje correr da sala, não deve ser muito ruim). Pensei que poderia ser interessante ilustrar. Embora só agora eu esteja superficialmente familiar com recursão de amplitude versus profundidade, estou pensando que minha rotina é realmente profunda (e que minha descrição de linguagem natural acima foi enganosa) com base nessa postagem de stackoverflow (espero que @ whuber ou outra pessoa mais inteligente que eu possa confirmar / negar).
Código: explicação:
idir
é a varredura dos valores da direção do fluxo.offset
refere-se à célula central que está sendo analisada no momento eoff
verifica cada um dos vizinhos dessa célula. Isso chama outra função,does_it_flow_into_me
que retorna um valor booleano para determinar se o flowdir da célula vizinha aponta para a célula atual. Se verdadeiro para um vizinho, retorne para esse local.fonte
A ajuda do ArcGIS diz:
A direção do fluxo é calculada a partir do DEM usando o método D8 , onde o fluxo é abstraído calculando para cada célula, em qual de seus 8 vizinhos, a água dessa célula fluirá para.
Existem muitas alternativas ao D8, como Rho8, Froh8 e Stream Tubes, mas a maioria dos softwares GIS, incluindo o ArcGIS, tendem a usar o D8, pois é mais simples e menos computacionalmente do que outros.
Alguns anos atrás, eu estava trabalhando em um projeto de Delimitação de Bacias Hidrográficas e estávamos enfrentando vários problemas devido ao ArcGIS usando o método D8. Os dois principais problemas foram
A partir de Nossos dados, sabíamos que esses dois problemas eram grandes problemas, então eu desenvolvi algumas ferramentas para gerar direções de fluxo usando métodos híbridos.
Uma das minhas primeiras tarefas foi fazer engenharia reversa da ferramenta de cálculo de Captação. Eu achei que era logicamente bastante simples. Se você deseja encontrar a captação para um determinado ponto (também chamado de ponto de fluidez), primeiro você encontra a célula à qual ela pertence. Frequentemente, você tentará ajustá-lo ao ponto com o maior acúmulo de fluxo em uma determinada tolerância.
Nesta célula, você encontrará todas as células da vizinhança que contribuem para ela. Para cada uma dessas células da vizinhança, você encontra as células que contribuem para elas e assim por diante. Você continua esse processo iterativo até não encontrar novas células. É quando você alcança as cordilheiras ou o limite da bacia hidrográfica.
Eu descobri que meu código simples que fazia isso para rasters ASCII, produzia resultados quase semelhantes quando comparado à ferramenta Watershed do ArcGIS. Às vezes, costumava haver uma diferença de algumas células na fronteira, então estou convencido de que o ArcGIS segue um algoritmo D8 não modificado.
fonte
Isso já foi perguntado antes , embora talvez em um contexto ligeiramente diferente. Todas as ferramentas de geoprocessamento no conjunto de ferramentas Hidrológicas do Spatial Analyst usam o modelo de direção de fluxo D8 , conforme indicado na página Como a direção de fluxo funciona :
Uma cópia do artigo de Jenson e Domingue (1988) está disponível aqui .
Todas as ferramentas que usam rasters de direção de fluxo como entrada utilizam esse modelo de direção de fluxo por associação. Isso inclui a bacia hidrográfica, a acumulação de fluxo, o comprimento do fluxo, o preenchimento, etc.
fonte
Para refletir mais sobre essa questão, fiz uma análise de bacias hidrográficas em arco: fiz um DEM (preenchido), calculei a direção do fluxo e coloquei alguns pontos que correspondiam aos locais em uma rede de fluxos previamente calculada. Eu executei a ferramenta 'bacia hidrográfica' e ela me deu algumas bacias agradáveis, cobrindo praticamente a maior parte da área restante 'a montante' (como seria de esperar):
Codifiquei um algoritmo de pesquisa rápida em Python (como a resposta acima), que inspeciona a grade de direção do fluxo e 'segue' os caminhos do fluxo. Para cada nó, inspeciono os 8 vizinhos e, se um vizinho fluir para o nó atual, chamo a mesma função recursivamente com o nó vizinho que a entrada.
Código pseudo (ish):
Eu executei essa função usando a mesma grade de entrada de direção de fluxo e um dos mesmos pontos. O problema é que, quando o arco retorna uma captação de cerca de 40000 células para esse ponto, meu algoritmo retorna apenas 72 células.
Alguém sabe o que estou fazendo de errado?
fonte