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 <[EMAIL PROTECTED]>: > 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 >> [email protected] >> 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: [EMAIL PROTECTED] > [EMAIL PROTECTED] > tel: +39(0)755853760 > fax (university): +39(0)755853756 > fax (home): +39(0)5782830887 > jabber: [EMAIL PROTECTED] > > _______________________________________________ > grass-user mailing list > [email protected] > http://lists.osgeo.org/mailman/listinfo/grass-user > _______________________________________________ grass-user mailing list [email protected] http://lists.osgeo.org/mailman/listinfo/grass-user
