mdbartos / pysheds

:earth_americas: Simple and fast watershed delineation in python.
GNU General Public License v3.0
710 stars 195 forks source link

Use Priority Flood algorithm to fill depressions #243

Closed groutr closed 7 months ago

groutr commented 8 months ago

Fixes #239

Runtime is about 7.5min on a (12150, 9622) float32 raster which is acceptable.

This variant of the algorithm (as presented in the paper linked in the issue) uses a plain queue to avoid some of the overhead of using the priority queue. Since numba doesn't have a plain queue, I use a list that gets flushed periodically. A critical part of making this fast was using numba's typedlist which still seems to be experimental according to the docs.

I'm open to feedback.

groutr commented 8 months ago

@mdbartos I've implemented most of the variants of the priority-flood algorithm described in this paper into a priority-flood module on my machine. There are methods for finding the basins, filling depressions, computing flow direction, and resolving flats (though I had to slightly deviate from the algorithm in the paper to make in work for test DEM). Do you want these other methods in pysheds too?

groutr commented 7 months ago

@mdbartos I don't think the nodata_out parameter is needed any longer in fill_depressions. How do you feel about deprecating it?

mdbartos commented 7 months ago

Thanks again and awesome work, MDB