# Update on r.cost

W. Fredrick Limp fred at cast.uark.edu
Fri Nov 5 14:46:48 EST 1993

```A few days ago I requested information on the revisions to r.cost in
4.1.  Jim Westervelt was the reviser and kindly forwarded details
to me with the suggestions that I summarize them and post.  So here
ae the details.  As you will se r.cost is improved and many thanks
to Jim for his efforts.

The major changes involves three things. Addition of a knight's move
so that more than just the four facing cells can be considered,
averaging the costs from the from and to cell rather than just
summing and adjusting (where necessary) when the cells are
rectangular rather than square.  Jim also introduced b-tree
processing which speeds the process.

_________________

The changes to r.cost for 4.1 were made by me in January 1991 while at
school in response to needs of some other folks in my student office.
As I recall, the changes were these:

1. Knights move
PROBLEM: There are significant distortions generated when the four
facing cells are considered only.  On a surface where the
cost is identical for every cell, the resulting surface has
a diamond shape to its contours.  Adding the 4 diagonal
neighbors improves this.
SOLUTION: Adding the knights move adds even more improvement.  However,
the processing time is nearly doubled.

2. Binary tree management of cell lists
PROBLEM: The biggest cost factor in r.cost is the management of the
list of cells that are to be considered for processing. These
cells have been assigned distance values; the trick is to
process the cell that has the lowest cost.
SOLUTION: I tried several approaches to decreasing the processing time
of this step and had no success at significant improvement
until implementing a binary tree.

3. Accommodating rectangular cells
PROBLEM: r.cost is run with a cost-of-traversal map as input.  I believe
that the r.cost in 4.0 presummed that the cells were square and
that the cost value is for traversing between the east and west
edges and the north and south edges.
SOLUTION: Presume that the cells are rectangular and that the cost value
represents travel cost between east and west.  r.cost adjusts
the north-south cost with respect to the |east-west|/|north-south|
ratio.   (I believe this was not documented in the user
manual.)

Finally, I don't recall if this was a change from 4.0 to 4.1, but the cost
of moving between two cells takes into account the length of the path
pieces in each associated cell.  That is, the cost of moving to an
adjacent (east) cell is:
.5 * cost-of-leaving-cell + .5 * cost-of-entering-cell
Movements in the N-S directions are adjusted as noted above in 3.
Movements in the knight's move directions are similarly considered.

I highly recommend that individuals experiment with each GIS program that
they use on a small, simple map so that the results of the operation can
be viscerally understood.  For r.cost I recommend that the user generate
a small (say 20x20) cost map with identical costs (say 1).  Run r.cost on
this map with different combinations of options (with and without -k).
Review the results for:
1) reasonableness (do the results match expectations)
2) correctness (how circular are the cost contours)
3) execution time

W. Fredrick Limp,   Director                     FAX: (501) 575-3846
CAST, Center for Advanced Spatial Technologies   TEL: (501) 575-6159
12 Ozark Hall, University of Arkansas
Fayetteville AR 72701                             fred at cast.uark.edu

```