[GRASS-user] r.watershed speed-up

[ivan marchesini]

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