Welcher Algorithmus wird vom ArcGIS Watershed-Tool verwendet?

Weiß jemand, welche Art von Algorithmus im ArcGIS Watershed-Tool (im Spatial Analyst-Paket) verwendet wird?

Sehr wenig Informationen auf Esris Website ... aber ich vermute, dass es sich um eine Art Tiefen- / Breitensuche handelt.

Ich habe mir diese ArcGIS Online-Hilfeseiten angesehen:

• Wasserscheide (Spatial Analyst)
• Wie Watershed funktioniert

Ja, es wird das Raster für die Flussrichtung verwendet, aber mit welchem ​​Algorithmus wird das Raster durchlaufen?

Bitte beachten Sie, dass ich nicht nach Antworten im Sinne von "Es verwendet D8 ..." suche. D8 ist nicht wirklich ein Algorithmus, sondern ein Modell zur Definition des Algorithmus, den Sie verwenden würden. IE Sie könnten das D8-Schema in einem Tiefensuchalgorithmus und / oder einem Breitensuchalgorithmus implementieren

Die Methode, die ich in einigen Sprachen implementiert habe und die von ESRI verwendet wird (leider keine anderen Referenzen als Jenson und Domingue, die an anderer Stelle auf dieser Seite zitiert werden), besteht darin, an einer vom Benutzer bereitgestellten "Pour-Point" -Zelle oder einer Zelle zu beginnen Untersuchen Sie am Rand des Strömungsrichtungsgitters (fdr) seine acht Nachbarn, um herauszufinden, welche von diesen direkt in die aktuelle Zelle fließen, und ordnen Sie diese Zellen der aktuellen "Wasserscheide" im Ausgangsgitter zu. Dann ruft sich die Funktion rekursiv einmal für jeden der einströmenden Nachbarn auf. Dieser Vorgang wird wiederholt, bis alle einströmenden Zellen für einen Stockpunkt erschöpft sind, und wird dann für alle Stockpunkte wiederholt.

Das Design des rekursiven Algorithmus kann ziemlich teuer sein, da es möglicherweise versucht, viele Daten im Speicher zu halten, die Seite auf die Festplatte austauschen muss und daher im Allgemeinen unter I / O-Verlangsamungen leidet.

(Siehe Whubers Kommentar unten zu verschiedenen Rekursionsmethoden, wenn Sie RYO wollen.)

_____________ BEARBEITEN _____________

Als Beispiel habe ich meinen alten C-Code ausgegraben (Hinweis: Obwohl die meisten Python-Spieler möglicherweise aus dem Raum rennen möchten, sollte dies nicht schlecht sein). Ich dachte, es könnte interessant sein, dies zu veranschaulichen. Obwohl ich erst jetzt oberflächlich mit der Rekursion "Breite zuerst" und "Tiefe zuerst" vertraut bin, denke ich, dass meine Routine tatsächlich Tiefe zuerst ist (und dass meine obige Beschreibung der natürlichen Sprache irreführend war), basierend auf diesem Stackoverflow-Posting (hoffentlich @ whuber oder eine andere Person, die klüger als ich ist, kann dies bestätigen / ablehnen).

Code: Erklärung: idirist das Raster der Durchflussrichtungswerte. offsetbezieht sich auf die zentrale Zelle, die gerade analysiert wird, und offüberprüft jeden Nachbarn dieser Zelle. Dies ruft eine andere Funktion auf, does_it_flow_into_medie einen Booleschen Wert zurückgibt, um festzustellen, ob das Flussverzeichnis der benachbarten Zelle auf die aktuelle Zelle zeigt. Wenn dies für einen Nachbarn zutrifft, kehren Sie zu diesem Ort zurück.

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 */
}

In der ArcGIS-Hilfe heißt es:

Wassereinzugsgebiete können aus einem DEM abgegrenzt werden, indem die Flussrichtung berechnet und im Werkzeug Wassereinzugsgebiet verwendet wird. Um den beitragenden Bereich zu bestimmen, muss zuerst mit dem Werkzeug Flussrichtung ein Raster erstellt werden, das die Flussrichtung darstellt.

Die Strömungsrichtung wird aus dem DEM unter Verwendung der D8-Methode berechnet . Dabei wird die Strömung abstrahiert, indem für jede Zelle berechnet wird, zu welchem ​​ihrer 8 Nachbarn das Wasser aus dieser Zelle fließt.

Es gibt viele Alternativen zu D8, wie Rho8, Froh8 und Stream Tubes, aber die meisten GIS-Programme, einschließlich ArcGIS, verwenden D8, da es einfacher und weniger rechenintensiv ist als andere.

Vor einigen Jahren arbeitete ich an einem Watershed Delineation-Projekt, und wir hatten aufgrund von ArcGIS mit der D8-Methode mehrere Probleme. Die beiden Hauptprobleme waren

• D8 erlaubt nur Uni Directional Flow. Wasser kann aus einer Zelle nur in eine Richtung abfließen.
• Die erzeugten Stromflüsse hatten eine große Vorspannung entlang der diagonalen Achse. Dies führte zu seltsam aussehenden Strömen.

Aus unseren Daten wussten wir, dass diese beiden Probleme große Probleme waren, daher hatte ich einige Tools entwickelt, um Strömungsrichtungen mit Hybridmethoden zu generieren.

Eine meiner frühesten Aufgaben war das Reverse Engineering des Einzugsgebietsberechnungstools. Ich fand, dass es logisch ziemlich einfach war. Wenn Sie das Einzugsgebiet für einen bestimmten Punkt (auch als Stockpunkt bezeichnet) suchen möchten, finden Sie zuerst die Zelle, zu der es gehört. Oft werden Sie versuchen, es an den Punkt mit der höchsten Durchflussakkumulation in einer bestimmten Toleranz zu bringen.

Für diese Zelle finden Sie alle Zellen in der Nachbarschaft, die dazu beitragen. Für jede dieser Nachbarschaftszellen finden Sie die Zellen, die zu ihnen beitragen, und so weiter. Sie setzen diesen iterativen Prozess fort, bis Sie keine neuen Zellen mehr finden. Dann haben Sie die Gratlinien oder die Wasserscheidegrenze erreicht.

Ich stellte fest, dass mein einfacher Code, der dies für ASCII-Raster ausführte, im Vergleich zum Watershed-Tool von ArcGIS eine fast ähnliche Ausgabe lieferte. Manchmal gab es einen Unterschied zwischen einigen Zellen an der Grenze, daher bin ich überzeugt, dass ArcGIS einem unveränderten D8-Algorithmus folgt.

Dies wurde schon früher gefragt , wenn auch vielleicht in einem etwas anderen Kontext. Alle Geoverarbeitungswerkzeuge im hydrologischen Toolset von Spatial Analyst verwenden das D8-Flussrichtungsmodell , wie auf der Seite Funktionsweise der Flussrichtung angegeben :

Es gibt acht gültige Ausgangsrichtungen, die sich auf die acht benachbarten Zellen beziehen, in die der Fluss fließen könnte. Dieser Ansatz wird allgemein als Strömungsmodell mit acht Richtungen (D8) bezeichnet und folgt einem in Jenson und Domingue (1988) vorgestellten Ansatz.

Eine Kopie des Papiers von Jenson und Domingue (1988) finden Sie hier .

Alle Werkzeuge, die Flow Direction-Raster als Eingabe verwenden, verwenden dieses Flow Direction-Modell durch Zuordnung. Dies umfasst Wasserscheide, Durchflussakkumulation, Durchflusslänge, Füllung usw.

Um diese Frage genauer zu untersuchen, führte ich eine Wassereinzugsgebietsanalyse im Bogen durch: Ich nahm ein (gefülltes) DEM, berechnete die Strömungsrichtung und platzierte einige Punkte, die Positionen in einem zuvor berechneten Stromnetz entsprachen. Ich habe das Tool "Wasserscheide" ausgeführt und es hat mir ein paar schöne Becken gegeben, die den größten Teil des verbleibenden Bereichs "stromaufwärts" abdecken (wie zu erwarten):

Ich habe dann einen Schnellsuchalgorithmus in Python codiert (wie die obige Antwort), der das Flussrichtungsgitter überprüft und den Flusspfaden "folgt". Für jeden Knoten überprüfe ich die 8 Nachbarn und wenn ein Nachbar in den aktuellen Knoten fließt, rufe ich dieselbe Funktion rekursiv mit dem Nachbarknoten als Eingabe auf.

Pseudo (ish) Code:

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)

Ich habe diese Funktion mit demselben Eingangsraster für die Flussrichtung und einem der gleichen Punkte ausgeführt. Das Problem ist, dass mein Algorithmus nur 72 Zellen zurückgibt, wenn arc für diesen Punkt ein Einzugsgebiet von etwa 40000 Zellen zurückgibt.

Weiß jemand was ich falsch mache?