[GRASS-user] r.watershed speed-up

[Moritz Lennert]

On 28/07/08 23:14, Markus Metz wrote:
> Hello list,
> 
> I'm not sure if this list is the right place or rather the developer list.
> For the A * Search algorithm in r.watershed (memory version without -m 
> flag set, r.watershed.ram), I implemented a binary min-heap instead of a 
> linear array to store points in ascending order relative to elevation. 
> This improves the speed of <SECTION 2: A * Search> considerably, the 
> larger the map, the larger the speed improvement. A region with about 
> 1,800,000 cells is processed about 37 times faster than with the 
> original routine. A region with about 11,000,000 cells is processed 
> about 170 times faster than with the original routine (46.7sec vs. 
> 2h12m9sec on my system). <SECTION 4: Watershed Determination> takes now 
> the longest.
> 
> Several tests (different region sizes, different DEMs) showed that the 
> results of the binary heap version are very similar but not 100% 
> identical to the original r.watershed, because of a slightly different 
> treatment of cells with equal elevation in a binary min-heap compared to 
> a linear array. Differences are found in difficult areas (equal 
> elevation of several neighbouring cells) where there are several 
> possible solutions for how water could flow. Still, compared with other 
> hydrology analysis methods, e.g. r.terraflow, the results can be 
> regarded as identical.
> 
> The original code was only altered where necessary, only the sorting 
> method is new, everything else is unchanged.
> Memory usage increases a bit, because a binary heap needs its own index 
> for each analysed point (in addition to the other indices already needed 
> by r.watershed.ram).
> 
> My question is if there is interest in this faster version of 
> r.watershed and if someone wants to test it.

I think there definitely is interest (see the number of mails about the 
long running time of r.watershed). The important issue will be the 
quality of results.

First test in North Carolina demo data set:

g.region rast=elevation

time r.watershed elevation=elevation at PERMANENT accumulation=old_accum 
drainage=old_dir basin=old_sheds stream=old_streams thresh=500

real    19m2.744s
user    18m41.318s
sys     0m1.884s

time r.watershed.fast elevation=elevation at PERMANENT 
accumulation=fast_accum drainage=fast_dir basin=fast_sheds 
stream=fast_streams thresh=500

real    0m18.034s
user    0m17.833s
sys     0m0.196s

Impressive !

Comparison of watersheds is a bit difficult because of different cat 
numbers and colors...but the two seem fairly similar.

Of the 2025000 cells in the map, 1991218 show the same direction, i.e. 
98%. Those which have different directions are overwhelmingly low slope 
cells.

1833907 cells have the same accumulation value, i.e. 90%, but I guess 
this is to be expected.

I'll look at the details of the differences later.

Moritz

Moritz