[GRASS-user] r.watershed speed-up

G. Allegri giohappy at gmail.com
Tue Jul 29 10:47:59 EDT 2008


Ivan anticipated me for a bit.
GREAT Markus! I could crunch Sardinia in one shot. I haven't measured
the time but it was less then 2 minutes, while with r.watershed I got
stalled.
Analyzing the differences between the r.watershed and r.watershed.fast
for a narrower region, there was some subtle, sparse differences
(1,-1,7) meaning 45° differences:

The following are the differences values (from r.mapcalc) statistics
(number of pixels for values)

 -7 76
-6 34
-5 30
-4 49
-3 43
-2 194
-1 1165
0 813894
1 1218
2 253
3 83
4 45
5 25
6 93
7 250
8 22
9 21
10 5
11 15
12 30
13 18
14 3
15 5
16 4
* 36917172

2008/7/29 ivan marchesini <marchesini at unipg.it>:
> First results of one test I did: excellent!!!
>
> 1392776 cells dem with steep slopes but also plain areas
>
> r.watershed.fast: 7 seconds
> r.watershed:  4 min and 14 seconds
>
> no difference at all between the two generated network paths...
>
> markus: many thanks..
>
>
> Ivan
>
>
> Il giorno lun, 28/07/2008 alle 23.14 +0200, Markus Metz ha scritto:
>> 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
>>
> --
> Ti prego di cercare di non inviarmi files .dwg, .doc, .xls, .ppt.
> Preferisco formati liberi.
> Please try to avoid to send me .dwg, .doc, .xls, .ppt files.
> I prefer free formats.
> http://it.wikipedia.org/wiki/Formato_aperto
> http://en.wikipedia.org/wiki/Open_format
>
> Ivan Marchesini
> Department of Civil and Environmental Engineering
> University of Perugia
> Via G. Duranti 93/a
> 06125
> Perugia (Italy)
> Socio fondatore GFOSS "Geospatial Free and Open Source Software" http://www.gfoss.it
> e-mail: marchesini at unipg.it
>        ivan.marchesini at gmail.com
> tel: +39(0)755853760
> fax (university): +39(0)755853756
> fax (home): +39(0)5782830887
> jabber: geoivan73 at jabber.org
>
> _______________________________________________
> grass-user mailing list
> grass-user at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/grass-user
>


More information about the grass-user mailing list