[GRASS-user] r.watershed speed-up

[G. Allegri]

A correction: as you can see from the stats, the differences are not
only  (1,-1,7) as I was saying...  Now I have to check how much these
differences affect the results. Anyway, above 99.5 % of values are
equal.

2008/7/29 G. Allegri <giohappy at gmail.com>:
> 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
>>
>