Jakiego algorytmu używa narzędzie ArcGIS Watershed?

Czy ktoś wie, jakiego rodzaju algorytmu używa narzędzie ArcGIS Watershed (w pakiecie Spatial Analyst)?

Bardzo mało informacji podanych na stronie Esri ... ale podejrzewam, że może to być jakieś wyszukiwanie głębokości / szerokości.

Przejrzałem strony pomocy ArcGIS Online:

• Watershed (Analityk przestrzenny)
• Jak działa Watershed

Więc tak, wykorzystuje raster kierunku przepływu, ale jakiego algorytmu używa do przechodzenia przez raster?

Uwaga: nie szukam odpowiedzi w stylu „używa D8 ...”… D8 nie jest tak naprawdę algorytmem, ale modelem pomagającym zdefiniować algorytm, którego należy użyć. IE można zaimplementować schemat D8 w algorytmie przeszukiwania w pierwszej kolejności i / lub w algorytmie przeszukiwania w pierwszej kolejności

Metodą, którą wdrożyłem w kilku językach i uważam, że używa ESRI (przepraszam, brak odniesień innych niż Jenson i Domingue cytowane w innym miejscu na tej stronie) jest rozpoczęcie od dostarczonej przez użytkownika komórki lub komórki „punktu krzepnięcia” na krawędzi siatki kierunku przepływu (fdr), zbadaj jej ośmiu sąsiadów, aby dowiedzieć się, który z nich wpływa bezpośrednio do bieżącej komórki, i przypisz te komórki do bieżącego „zlewu” w siatce wyjściowej. Następnie funkcja rekurencyjnie wywołuje się raz dla każdego z napływających sąsiadów. Proces ten powtarza się, aż wszystkie napływające komórki zostaną wyczerpane dla punktu krzepnięcia, a następnie powtórzy się dla wszystkich punktów krzepnięcia.

Algorytm rekurencyjny może być dość kosztowny, ponieważ może skończyć się próbą przechowywania dużej ilości danych w pamięci, konieczności zamiany / stronicowania na dysk, a zatem generalnie występuje spowolnienie operacji we / wy.

(patrz komentarz Whubera poniżej na temat różnych metod rekurencji, jeśli zamierzasz RYO)

_____________ EDYCJA _____________

Odkopałem mój stary kod C jako przykład (uwaga: chociaż większość pythonerów może chcieć uruchomić z pokoju, nie powinno być tak źle). Pomyślałem, że warto to zilustrować. Chociaż dopiero teraz pozornie zaznajomiłem się z rekurencją w pierwszej kolejności w stosunku do głębokości pierwszej, myślę, że moja rutyna jest naprawdę w pierwszej kolejności (i że mój opis języka naturalnego powyżej wprowadzał w błąd) w oparciu o ten komunikat o przepełnieniu stosu (mam nadzieję, że @ whuber lub inna osoba mądrzejsza ode mnie może potwierdzić / odmówić).

Kod: wyjaśnienie: idirjest rastrem wartości kierunku przepływu. offsetodnosi się do komórki centralnej, która jest obecnie analizowana, i offsprawdza każdego z sąsiadów tej komórki. does_it_flow_into_meWywołuje to inną funkcję, która zwraca wartość logiczną określającą, czy katalog przepływu sąsiedniej komórki wskazuje na bieżącą komórkę. Jeśli to prawda dla sąsiada, wróć do tej lokalizacji.

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

Pomoc ArcGIS mówi:

Obszary wodne można wyznaczyć z DEM, obliczając kierunek przepływu i używając go w narzędziu Watershed. Aby określić obszar przyczyniający się, należy najpierw utworzyć raster reprezentujący kierunek przepływu za pomocą narzędzia Kierunek przepływu.

Kierunek przepływu jest obliczany z DEM przy użyciu metody D8 , gdzie przepływ jest pobierany poprzez obliczenie dla każdej komórki, do którego z 8 sąsiadów, woda z tej komórki przepłynie.

Istnieje wiele alternatyw dla D8, takich jak Rho8, Froh8 i Stream Tubes, ale większość oprogramowania GIS, w tym ArcGIS, zwykle używa D8, ponieważ jest prostsze i mniej intensywne obliczeniowo niż inne.

Kilka lat temu pracowałem nad projektem Watershed Delineation i napotkaliśmy kilka problemów związanych z ArcGIS przy użyciu metody D8. Dwa główne problemy to

• D8 pozwala tylko na przepływ jednokierunkowy. Woda może wypływać tylko w jednym kierunku z jednej komórki.
• Generowane przepływy strumieniowe miały ogromne odchylenie wzdłuż osi ukośnej. Dało to początek dziwnie wyglądającym strumieniom.

Na podstawie naszych danych wiedzieliśmy, że te dwa problemy były dużymi problemami, dlatego opracowałem narzędzia do generowania kierunków przepływu przy użyciu metod hybrydowych.

Jednym z moich najwcześniejszych zadań było odtworzenie narzędzia do obliczania Zlewni. Odkryłem, że było to logicznie proste. Jeśli chcesz znaleźć zlewnię dla danego punktu (zwaną także temperaturą krzepnięcia), najpierw znajdź komórkę, do której należy. Często będziesz próbował przyciągnąć go do punktu o największej akumulacji przepływu w danej tolerancji.

Dla tej komórki znajdziesz wszystkie komórki w sąsiedztwie, które się do niej przyczyniają. Dla każdej z tych sąsiednich komórek znajdziesz komórki, które się do nich przyczyniają i tak dalej. Kontynuujesz ten iteracyjny proces, dopóki nie znajdziesz żadnych nowych komórek. Wtedy osiągniesz linię grzbietu lub granicę zlewni.

Odkryłem, że mój prosty kod, który zrobił to dla rastrów ASCII, dał prawie podobny wynik w porównaniu do narzędzia Watershed ArcGIS. Czasami istniała różnica kilku komórek na granicy, więc jestem przekonany, że ArcGIS stosuje niezmodyfikowany algorytm D8.

Zostało to już wcześniej zadane , choć może w nieco innym kontekście. Wszystkie narzędzia geoprzetwarzania w zestawie narzędzi hydrologicznych programu Spatial Analyst korzystają z modelu kierunku przepływu D8 , jak podano na stronie Jak działa kierunek przepływu :

Istnieje osiem prawidłowych kierunków wyjściowych dotyczących ośmiu sąsiednich komórek, do których może przepływać przepływ. Takie podejście jest powszechnie określane jako ośmiokierunkowy (D8) model przepływu i jest zgodne z podejściem przedstawionym w Jenson i Domingue (1988).

Kopia pracy Jensona i Domingue (1988) jest dostępna tutaj .

Wszystkie narzędzia, które wykorzystują rastry kierunku przepływu jako dane wejściowe, wykorzystują ten model kierunku przepływu przez skojarzenie. Obejmuje to między innymi wododział, akumulację przepływu, długość przepływu, wypełnienie itp.

Aby zastanowić się więcej nad tym pytaniem, przeprowadziłem analizę łuku: wziąłem (wypełniony) DEM, obliczyłem kierunek przepływu i umieściłem kilka punktów odpowiadających lokalizacjom w poprzednio obliczonej sieci strumieniowej. Uruchomiłem narzędzie „zlewu” i dało mi to kilka fajnych basenów, pokrywających prawie całą pozostałą część „w górę rzeki” (jak można się spodziewać):

Następnie kodowałem algorytm szybkiego wyszukiwania w Pythonie (podobnie jak powyższa odpowiedź), który sprawdza siatkę kierunku przepływu i „podąża” ścieżkami przepływu. Dla każdego węzła sprawdzam 8 sąsiadów i jeśli sąsiad wpada do bieżącego węzła, wywołuję tę samą funkcję rekurencyjnie z sąsiednim węzłem jako wejściem.

Kod 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)

Uruchomiłem tę funkcję, używając tej samej siatki wejściowej kierunku przepływu i jednego z tych samych punktów. Problem polega na tym, że gdy łuk zwraca w tym punkcie zasięg około 40000 komórek, mój algorytm po prostu zwraca 72 komórki.

Czy ktoś wie, co robię źle?