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:
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
Odpowiedzi:
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:
idir
jest rastrem wartości kierunku przepływu.offset
odnosi się do komórki centralnej, która jest obecnie analizowana, ioff
sprawdza każdego z sąsiadów tej komórki.does_it_flow_into_me
Wywoł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.źródło
Pomoc ArcGIS mówi:
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
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.
źródło
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 :
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.
źródło
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):
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?
źródło