[GRASS-user] r.watershed speed-up

[Markus Metz]

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.
The source code is available on http://markus.metz.giswork.googlepages.com/

Regards,

Markus