#237: r.watershed: speed improvement
-------------------------------+--------------------------------------------
Reporter: mmetz | Owner: grass-dev@lists.osgeo.org
Type: enhancement | Status: new
Priority: minor | Milestone: 6.4.0
Component: Raster | Version: 6.3.0
Keywords: r.watershed speed | Platform: Unspecified
Cpu: Unspecified |
-------------------------------+--------------------------------------------
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.
--
Ticket URL: <http://trac.osgeo.org/grass/ticket/237>
GRASS GIS <http://grass.osgeo.org>
_______________________________________________
grass-dev mailing list
grass-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/grass-dev
