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
[email protected]
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: [EMAIL PROTECTED]
VOICE: 937-383-0528
FAX: 937-383-0033
_______________________________________________
grass-user mailing list
[email protected]
http://lists.osgeo.org/mailman/listinfo/grass-user
