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
