Update on r.cost

[W. Fredrick Limp]

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.

_________________
Jim's comments follow:


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