Adakah yang tahu jenis algoritma apa yang digunakan dalam alat ArcGIS Watershed (dalam paket Spatial Analyst)?
Sangat sedikit informasi yang diberikan di situs web Esri ... tapi saya curiga ini mungkin semacam pencarian mendalam / luas.
Saya telah melihat halaman Bantuan Online ArcGIS ini:
Jadi ya, ia menggunakan aliran arah raster, tetapi algoritma apa yang digunakannya untuk melintasi raster?
Harap dicatat, saya tidak mencari jawaban di sepanjang baris 'itu menggunakan D8 ..' ... D8 sebenarnya bukan algoritma, tetapi model untuk membantu menentukan algoritma yang akan Anda gunakan. IE Anda bisa menerapkan skema D8 dalam algoritma pencarian kedalaman-pertama dan / atau algoritma pencarian luas-pertama
Jawaban:
Metode yang telah saya terapkan dalam beberapa bahasa dan percaya bahwa ESRI menggunakan (maaf, tidak ada referensi selain Jenson dan Domingue dikutip di tempat lain di halaman ini) adalah mulai pada sel "titik tuangkan" yang disediakan pengguna atau sel di tepi grid arah aliran (fdr), periksa delapan tetangganya untuk menemukan yang mana dari aliran langsung ke sel saat ini, dan menetapkan sel-sel tersebut ke arus "DAS" di grid output. Kemudian fungsi secara rekursif memanggil dirinya sendiri sekali untuk masing-masing tetangga yang masuk. Proses ini berulang sampai semua sel yang masuk habis untuk titik-tuangkan, dan kemudian akan diulang untuk semua titik-tuangkan.
Desain algoritma rekursif dapat menjadi sangat mahal karena akhirnya dapat mencoba untuk menyimpan banyak data dalam memori, harus menukar / halaman ke disk, dan karena itu umumnya menderita lambat lambat.
(lihat komentar whuber di bawah ini tentang berbagai metode rekursi, jika Anda akan RYO)
_____________ EDIT _____________
Gali kode C lama saya sebagai contoh (catatan: Meskipun sebagian besar pythoners mungkin ingin lari dari ruangan, seharusnya tidak terlalu buruk). Mungkin menarik untuk diilustrasikan. Walaupun saya baru sekarang akrab dengan rekursi mendalam-pertama vs kedalaman-pertama, saya berpikir bahwa rutinitas saya memang kedalaman-pertama (dan bahwa deskripsi bahasa alami saya di atas menyesatkan) berdasarkan posting stackoverflow ini (semoga @ whuber atau orang lain yang lebih pintar dari saya dapat konfirmasi / tolak).
Kode: penjelasan:
idir
adalah raster nilai arah aliran.offset
merujuk ke sel tengah yang saat ini sedang dianalisis, danoff
memeriksa masing-masing tetangga sel itu. Ini memanggil fungsi laindoes_it_flow_into_me
,, yang mengembalikan boolean, apakah flowdir sel tetangga menunjuk ke sel saat ini. Jika benar untuk tetangga, maka kembalilah ke lokasi itu.sumber
The ArcGIS bantuan mengatakan:
Arah Aliran dihitung dari DEM menggunakan metode D8 , Di mana aliran diabstraksi dengan menghitung untuk setiap sel, yang mana dari 8 tetangga, air dari sel ini akan mengalir ke.
Ada banyak alternatif untuk D8, seperti Rho8, Froh8 & Stream Tubes, tetapi sebagian besar Perangkat Lunak GIS termasuk ArcGIS cenderung menggunakan D8, karena lebih sederhana, dan kurang intensif secara komputasi daripada yang lain.
Beberapa tahun yang lalu, saya mengerjakan proyek Delineasi Daerah Aliran Sungai, dan kami menghadapi beberapa masalah karena ArcGIS menggunakan metode D8. Dua masalah utama adalah
Dari data kami, kami tahu bahwa dua masalah ini adalah masalah besar, jadi saya telah mengembangkan beberapa alat untuk menghasilkan arahan aliran menggunakan metode hybrid.
Salah satu tugas saya yang paling awal adalah merekayasa balik alat perhitungan Catchment. Saya menemukan bahwa itu secara logis cukup sederhana. Jika Anda ingin menemukan tangkapan untuk titik tertentu (juga disebut titik tuangkan), pertama-tama Anda menemukan sel tempat sel itu berada. Seringkali Anda akan mencoba untuk snap ke titik dengan akumulasi aliran tertinggi dalam toleransi yang diberikan.
Untuk sel ini, Anda akan menemukan semua sel di lingkungan yang berkontribusi padanya. Untuk setiap sel lingkungan ini, Anda menemukan sel yang berkontribusi padanya dan seterusnya. Anda melanjutkan proses berulang ini hingga Anda tidak menemukan sel baru. Saat itulah Anda telah mencapai garis punggungan atau batas daerah aliran sungai.
Saya menemukan bahwa kode sederhana saya yang melakukan ini untuk raster ASCII, memberikan output yang hampir sama jika dibandingkan dengan alat DAS ArcGIS. Kadang-kadang dulu ada perbedaan beberapa sel pada batas, jadi saya yakin bahwa ArcGIS mengikuti algoritma D8 yang tidak dimodifikasi.
sumber
Ini telah ditanyakan sebelumnya , meskipun mungkin dalam konteks yang sedikit berbeda. Semua alat geoproses dalam perangkat Hidrologi Analis Tata Ruang menggunakan model arah aliran D8 , seperti yang dinyatakan dalam halaman Cara Alir Arah Bekerja :
Salinan kertas Jenson dan Domingue (1988) tersedia di sini .
Semua alat yang menggunakan raster Arah Aliran sebagai input menggunakan model arah aliran ini dengan asosiasi. Ini termasuk DAS, Akumulasi Aliran, Panjang Aliran, Isi, dll.
sumber
Untuk lebih memikirkan pertanyaan ini, saya menjalankan analisis DAS dalam busur: Saya mengambil DEM (diisi), menghitung arah aliran dan menempatkan beberapa titik yang sesuai dengan lokasi pada jaringan aliran yang sebelumnya dihitung. Saya menjalankan alat 'daerah aliran sungai' dan memberi saya beberapa bak air bagus, cukup banyak menutupi sebagian besar daerah 'hulu' yang tersisa (seperti yang Anda harapkan):
Saya kemudian menyusun algoritma pencarian cepat dengan Python (seperti jawaban di atas), yang memeriksa grid arah aliran dan 'mengikuti' jalur aliran. Untuk setiap node, saya memeriksa 8 tetangga dan jika tetangga mengalir ke node saat ini, saya memanggil fungsi yang sama secara rekursif dengan simpul tetangga sebagai input.
Kode semu (ish):
Saya menjalankan fungsi itu menggunakan input grid arah aliran yang sama dan salah satu poin yang sama. Masalahnya adalah, di mana arc mengembalikan tangkapan sekitar 40000 sel untuk titik itu, algoritma saya hanya mengembalikan 72 sel.
Adakah yang tahu apa yang saya lakukan salah?
sumber