¿Qué algoritmo utiliza la herramienta ArcGIS Watershed?

10

¿Alguien sabe qué tipo de algoritmo se utiliza en la herramienta ArcGIS Watershed (en el paquete Spatial Analyst)?

Muy poca información dada en el sitio web de Esri ... pero sospecho que puede ser algún tipo de búsqueda de profundidad / amplitud.

He visto estas páginas de ayuda en línea de ArcGIS:

Entonces, sí, usa el ráster de dirección de flujo, pero ¿qué algoritmo está usando para atravesar el ráster?

Tenga en cuenta que no estoy buscando respuestas en la línea de 'usa D8 ...' ... D8 no es realmente un algoritmo, sino un modelo para ayudar a definir el algoritmo que usaría. Es decir, podría implementar el esquema D8 dentro de un algoritmo de búsqueda de profundidad primero y / o un algoritmo de búsqueda de amplitud

James
fuente
James, estoy tratando de hacer lo mismo, es decir, crear una aplicación que tome una coordenada determinada y nos dé una delimitación de cuencas hidrográficas. Estoy usando python Hablemos de nuestro progreso.
También estoy usando Python. Estoy comenzando con el problema más simple de calcular una cuadrícula de dirección de flujo y seguir desde allí.
James

Respuestas:

6

El método que he implementado en un par de idiomas y creo que utiliza ESRI (lo siento, no hay referencias aparte de Jenson y Domingue citadas en otra parte de esta página) es comenzar en una celda o celda de "punto de fluidez" suministrada por el usuario en el borde de la cuadrícula de dirección del flujo (fdr), examine sus ocho vecinos para encontrar cuál de esos flujos directos en la celda actual y asigne esas celdas a la "cuenca" actual en la cuadrícula de salida. Luego, la función se llama recursivamente una vez para cada uno de los vecinos entrantes. Este proceso se repite hasta que se agoten todas las celdas de entrada para un punto de fluidez, y luego se repetirá para todos los puntos de fluidez.

El diseño del algoritmo recursivo puede ser bastante costoso porque puede terminar tratando de mantener una gran cantidad de datos en la memoria, tener que intercambiar / paginar en el disco y, por lo tanto, generalmente se ralentiza la E / S.

(vea el comentario de whuber a continuación sobre los diferentes métodos de recursión, si va a RYO)

_____________ EDITAR _____________

Saqué mi viejo código C como ejemplo (nota: aunque la mayoría de los pitones pueden querer correr desde la habitación, no debería ser tan malo). Pensé que podría ser de interés ilustrar. Aunque solo ahora soy superficialmente familiar con la recursividad primero en amplitud versus en profundidad, creo que mi rutina es realmente profunda (y que la descripción de mi lenguaje natural anterior fue engañosa) en base a esta publicación de stackoverflow (con suerte @ Whuber u otra persona más inteligente que yo puede confirmar / negar).

Código: explicación: idires la trama de los valores de dirección del flujo. offsetse refiere a la celda central que se está analizando actualmente y offverifica cada uno de los vecinos de esa celda. Esto llama a otra función, does_it_flow_into_meque devuelve un valor booleano en cuanto a si el flowdir de la celda vecina apunta a la celda actual. Si es cierto para un vecino, entonces recurrir a esa ubicación.

void shed(int init_x, int init_y, int basin_id){

int i, j, offset, off, flow_dir;

offset = ((init_y - 1) * nc) + (init_x - 1);
*(basin + offset) = basin_id;


/* kernel analysis */
for (i = -1; i <  2; i++) {
    for (j = -1; j <  2; j++) {
        if ((i) || (j)) {

            off = offset + (j * nc +  i);
            flow_dir = *(idir + off);


            if (does_it_flow_into_me(i,j,flow_dir)){
                shed(init_x+i, init_y+j,basin_id);
            }
        } /*not center */
    } /* do - j */
} /* do - i */
}
Roland
fuente
Describe la recursividad de amplitud primero. Mediante una pequeña pila, puede implementar una recursión eficiente de profundidad primero, que requiere poca memoria. El principal problema de rendimiento se referiría a las grandes cuencas hidrográficas donde los azulejos de la red podrían tener que intercambiarse dentro y fuera de la RAM repetidamente. Sin embargo, como se discutió en los comentarios a otras respuestas, el problema real se refiere a hacer frente a las celdas donde no hay una dirección D8 determinada de manera única, especialmente las celdas ubicadas dentro de parches horizontales planos extensos (como los creados por rutinas preliminares de llenado de sumideros).
whuber
Definitivamente un problema de basura en la basura. ¡Lo que yo y la mayoría de GIss hacemos no limpiará la entrada! Parece que tengo que ir a buscar primero la recursión en profundidad para poner algo de brillo en mi truco.
Roland
No creo que esto sea basura; recuerde, independientemente de cómo se descomponga la implementación, la entrada original es el DEM en sí mismo en lugar de la codificación D8 de alguien, pero definitivamente es un desafío. El mundo real tiene muchos lugares que son tan planos que la dirección del flujo es difícil de determinar: cualquier cuerpo de agua estático es un buen ejemplo. En efecto, necesita encontrar salidas de lagos y otras áreas planas y debe hacer frente a áreas planas que tienen múltiples salidas. Esto requiere búsquedas no locales , que son difíciles de hacer.
whuber
Probablemente estoy confundido entonces. Estoy pensando que estamos discutiendo help.arcgis.com/en/arcgisdesktop/10.0/help../index.html#//… , que toma flowdir como entrada. ¡No quiero meternos en la maleza si no he leído el resto lo suficiente!
Roland
No, creo que tiene razón: al releer la pregunta, veo que se enfoca específicamente en procesar el ráster de dirección del flujo como entrada, en lugar de en la situación más general que estaba imaginando. Entonces haga +1 en su respuesta para abordarlo directamente y con información y consejos útiles.
whuber
4

La ayuda de ArcGIS dice:

Las cuencas hidrográficas se pueden delinear desde un DEM calculando la dirección del flujo y usándola en la herramienta Cuencas hidrográficas. Para determinar el área contribuyente, primero se debe crear un ráster que represente la dirección del flujo con la herramienta Dirección del flujo.

La dirección del flujo se calcula a partir del DEM utilizando el método D8 , donde el flujo se abstrae calculando para cada celda, a cuál de sus 8 vecinos, fluirá el agua de esta celda.

Hay muchas alternativas a D8, como Rho8, Froh8 y Stream Tubes, pero la mayoría del software GIS, incluido ArcGIS, tiende a usar D8, ya que es más simple y menos computacionalmente intensivo que otros.


Hace unos años, estaba trabajando en un proyecto de delineación de cuencas hidrográficas, y nos enfrentamos a varios problemas debido a ArcGIS que utiliza el método D8. Los dos problemas principales fueron

  • D8 solo permite flujo unidireccional. El agua puede fluir solo en una dirección desde una celda.
  • Los flujos de corriente generados tenían un gran sesgo a lo largo del eje diagonal. Esto dio lugar a corrientes de aspecto extraño.

A partir de nuestros datos, sabíamos que estos dos problemas eran grandes, por lo que había desarrollado algunas herramientas para generar direcciones de flujo utilizando métodos híbridos.

Una de mis primeras tareas fue realizar ingeniería inversa en la herramienta de cálculo de captación. Descubrí que era lógicamente bastante simple. Si desea encontrar la cuenca para un punto dado (también llamado punto de fluidez), primero encuentre la celda a la que pertenece. A menudo intentará ajustarlo al punto con la acumulación de flujo más alta en una tolerancia dada.

Para esta celda, encontrará todas las celdas en el vecindario que contribuyen a ella. Para cada una de estas celdas vecinas, encontrará las celdas que contribuyen a ellas, etc. Continúa este proceso iterativo hasta que no encuentres nuevas celdas. Ahí es cuando has llegado a las líneas de la cresta o al límite de la cuenca.

Encontré que mi código simple que hizo esto para los rásteres ASCII, dio un resultado casi similar en comparación con la herramienta Watershed de ArcGIS. A veces solía haber una diferencia de algunas celdas en el límite, por lo que estoy convencido de que ArcGIS sigue un algoritmo D8 no modificado.

Devdatta Tengshe
fuente
Gracias por la elaboracion. Pero, ¿cuál es el algoritmo para usar las direcciones D8 para encontrar cuencas? Por favor, vea los comentarios después de la respuesta de dmahr .
whuber
Hola, gracias, pero esto realmente no responde la pregunta. Lo golpeas con la frase "Para esta celda encontrarás todas las celdas del vecindario que contribuyen a ella. Para cada una de estas celdas de vecindario, encuentras las celdas que contribuyen a ellas y así sucesivamente". Hay muchos algoritmos diferentes para implementar esa búsqueda. La pregunta es cuál
James
4

Esto se ha preguntado antes , aunque quizás en un contexto ligeramente diferente. Todas las herramientas de geoprocesamiento en el conjunto de herramientas hidrológicas de Spatial Analyst usan el modelo de dirección de flujo D8 , como se indica en la página Cómo funciona la dirección de flujo :

Hay ocho direcciones de salida válidas relacionadas con las ocho celdas adyacentes a las que podría viajar el flujo. Este enfoque se conoce comúnmente como un modelo de flujo de ocho direcciones (D8) y sigue un enfoque presentado en Jenson y Domingue (1988).

Una copia del artículo de Jenson y Domingue (1988) está disponible aquí .

Todas las herramientas que usan rásteres de dirección de flujo como entrada utilizan este modelo de dirección de flujo por asociación. Esto incluye la cuenca, la acumulación de flujo, la longitud del flujo, el llenado, etc.

dmahr
fuente
Entonces, supongo que una pregunta de seguimiento sería, ¿cómo se modifica ese algoritmo para devolver la cuenca?
James
La herramienta Cuenca hidrográfica navega por el ráster de dirección del flujo desde los puntos de vertido. Es el reverso de la herramienta de acumulación de flujo, excepto que en lugar del ráster de salida que describe el número de celdas, informa la ID del punto de fluidez.
dmahr
1
Ok, supongo que necesito ser un poco más específico. Sé el concepto de lo que hace. No sé qué algoritmo se implementa. Es decir, supongo que es algún tipo de algoritmo de búsqueda, pero aún podría serlo; amplitud primero, profundidad primero, profundización iterativa profundidad primero, etc ...
James
1
gracias dmahr. @whuber: Hasta donde yo sé, diferentes algoritmos de búsqueda podrían dar resultados ligeramente diferentes. Y sí, encontrar un algoritmo genérico no es un problema, pero es útil aprender cómo ESRI maneja áreas específicas de cuenca (como partes planas de un DTM).
James
1
James Por favor, edite su pregunta para aclarar ese último punto, de modo que este hilo deje de recopilar respuestas inútiles "es D8". (Lo que es útil sobre los comentarios de D8 es que si acepta que D8 conduce a un gráfico de dirección de flujo único, entonces hay una solución única y correcta para el problema de delineación de cuencas hidrográficas, porque las cuencas hidrográficas son propiedades del gráfico en sí. Por lo tanto, si hay cualquier ambigüedad en la que deben estar (a) la definición de "cuenca hidrográfica", (b) cómo se calculan las direcciones D8, o (c) cómo se manejan las celdas horizontales (es decir, sin una dirección D8 única).
whuber
0

Para reflexionar más sobre esta pregunta, realicé un análisis de cuenca en arco: tomé un DEM (lleno), calculé la dirección del flujo y coloqué algunos puntos que correspondían a ubicaciones en una red de flujo previamente calculada. Ejecuté la herramienta 'cuenca hidrográfica' y me dio algunas cuencas agradables, que cubren la mayor parte del área restante 'aguas arriba' (como era de esperar):

imagen de la cuenca

Luego codifiqué un algoritmo de búsqueda rápida en Python (como la respuesta anterior), que inspecciona la cuadrícula de dirección del flujo y 'sigue' las rutas de flujo. Para cada nodo, inspecciono los 8 vecinos y si un vecino fluye hacia el nodo actual, invoco la misma función recursivamente con el nodo vecino como entrada.

Código pseudo (ish):

class d8():
    def __init__(self, arr):
       self.catchment = set()
       self.arr = arr

    def search(self, node):
        """ Searches all neighbouring nodes to find flow paths """ 

        # add the current node to the catchment
        self.catchment.add(node)

        # search the neighbours, ignore ones we already visited
        for each_neighbour:
            if neighbour is in self.catchment:
               do nothing

            # if the neighbour flows into the current node, visit that neighbour
            elif neighbour_flows_into_me:
               self.search(neighbour)

Ejecuté esa función usando la misma cuadrícula de entrada de dirección de flujo y uno de los mismos puntos. El problema es que, cuando el arco devuelve una captación de unas 40000 celdas para ese punto, mi algoritmo solo devuelve 72 celdas.

Alguien sabe lo que estoy haciendo mal?

James
fuente