How intelligent is r.cost?
westerve at zorro.cecer.army.mil
Mon Jan 18 10:07:24 EST 1993
Conn V Copas, Loughborough University of Technology, asks questions of
r.cost. Involves finding least cost path to a lake.
# Can I simply use a map which contains 2 categories: lake and land?
Yes, the lake would be given category 1 and the rest of the map 0.
# Or, do I need to create a map which defines the perimeter of the
# lake only?
That would work too. Perhaps the easiest however would be to give
a travel time of zero to cells in the lake. Then, give any starting
point in the middle of the lake.
# I can vaguely see that this latter step requires one to perform a
# neighbourhood analysis in which one inspects the attributes of cells on
# each 'side' of a given cell, but exactly how would one do this in
# practice? Once I have my map of multiple coordinates in a suitable
# form, can I be sure that r.cost will select the 'cheapest' cell from
# that list when computing cumulative cost for a given cell?
The r.cost algorithm runs as follows:
1) Sort all of the potential starting points in order of travel time
across the cell.
2) If there are any cells on the list, pick that with the shortest
travel time. (else, quit)
3) For that cell, compute potential travel time to all surrounding
cells. If the potential time is less than that already assigned
to the cell (they start out at effectively infinite), update the
time to the cell.
4) Add all neighboring cells to the sorted list.
5) Go to 2.
By the way, there is a new and improved r.cost on moon.cecer.army.mil
which has two advantages over the r.cost of 4.0
1) Faster sorting of the cells on the list (b-tree)
2) Knight's move option. This changes step (3) above by considering
not only the 8 surrounding cells, but the 8 cells that are in the
position where a chess knight could move to.
3) Better management of swap space
The first and third upgrades significantly improves execution speed.
The second generates a more correct solution at a cost in speed.
More information about the grass-user