[GRASS-user] r.watershed speed-up

[Charles Ehlschlaeger]

Dear Markus and other r.watershed enthusiasts,
I've thought of a way to make your faster version of r.watershed give
identical results as the older r.watershed. r.watershed.old uses a breadth
first search in section 2. r.watershed.fast is breadth first <when the DEM
values are different>. The trick would be to slightly adjust DEM values by
when they were added to the heap. Here is some pseudo-code
cellsAddedToHeap = 0
minCellIncrement = Double.MIN_VALUE # (java) This constant represents 
                                    # the smallest increment a CELL 
                                    # can be, if the CELLs are doubles.
# At the time a cell is added to heap, the DEM value placed 
# in the heap would be:
DemOfCellToHeap = DEM + (minCellIncrement * cellsAddedToHeap++))

Sincerely, chuck

-----Original Message-----
From: grass-user-bounces at lists.osgeo.org
[mailto:grass-user-bounces at lists.osgeo.org] On Behalf Of Markus Metz
Sent: Tuesday, July 29, 2008 10:44 AM
To: G. Allegri
Cc: grass-user at lists.osgeo.org
Subject: Re: [GRASS-user] r.watershed speed-up

Yes, there are some differences. Please look at where these differences 
are located and if they are significantly changing the results. In flat 
areas, there will be several possibilities about how water could flow. 
This might also affect the flowpath further upstream. Both the original 
version and the fast version have a certain degree of randomness on how 
to find a path through flat terrain, but it's a different type 
randomness, so to speak. The fast version can not exactly replicate the 
results, but it is pretty close. If there are only slight shifts in the 
flowpath and these differences can be justified by comparing them to the 
input DEM, the results could be useful. I think of particular interest 
are larger differences in flow accumulation, because they have a big 
influence on other output like basins and flow direction.

Thanks for testing!


G. Allegri wrote:
> 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
>>
>>     
_______________________________________________
grass-user mailing list
grass-user at lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/grass-user