[GRASS-user] r.watershed speed-up

[Thomas Adams]

Markus,

Thank you very much! I have not tested it yet, but after I do I'll write 
you with my impressions. I think this could be a very valuable contribution.

Regards,
Tom

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.
> The source code is available on 
> http://markus.metz.giswork.googlepages.com/
>
> Regards,
>
> Markus
>
> _______________________________________________
> grass-user mailing list
> grass-user at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/grass-user


-- 
Thomas E Adams
National Weather Service
Ohio River Forecast Center
1901 South State Route 134
Wilmington, OH 45177

EMAIL:	thomas.adams at noaa.gov

VOICE:	937-383-0528
FAX:	937-383-0033