r.watershed: speed improvement
|Reported by:||mmetz||Owned by:|
I want to suggest a new sorting algorithm for <SECTION 2: A * Search> in r.watershed.
The A * Search is only interested in the cell with the lowest elevation within the list of candidates, in case of several cells with equal elevation, in the cell that was added earliest to the list. This can be done with a binary min-heap and would not change the A * algorithm, it would provide near identical results with a substantial increase in speed.
Using a binary min-heap, r.watershed is faster than r.terraflow. Compared to the currently used linear array, speed improvement with a binary heap as sorting method is not constant, but increases with the number of cells analysed.