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
[email protected]
http://lists.osgeo.org/mailman/listinfo/grass-user
