DESCRIPTION
r.terracost is a scalable approach for computing least-cost-path
surfaces on massive grid terrains. The module outperforms standard solutions
as dataset size increases relative to available memory.
NOTES
r.terracost computes a least-cost surface for a given cost grid and
set of start points using an approach that scales to large grids. For details,
see paper "TerraCost: A Versatile and Scalable Approach for Path
Computations on Massive Grid-Based Terrains" by Hazel, Toma, Vahrenhold
and Wickremesinghe (2006). The basic idea is to split the grid in tiles.
numtiles is the number of tiles. Run with -i to see the recommended
value for numtiles. When numtiles=1 it runs Dijkstra's algorithm in
memory. When numtiles > 1 it runs an external SP algorithm that consists
of 5 steps. For debugging purposes, it is possible to run the five steps separately.
When running in separate steps, an intermediate config file stores temporary information,
and other streams (see below) contain intermediate data.
- Step 0 (setup) inputs from GRASS; outputs are "S0OUT" and "S0BND"
- Step 1 (compute substitute graph: intra-tile Dijkstra) inputs are "S0OUT"
and "S0BND"; outputs are "S1OUT" and "S2BOUT"
- Step 2 (sorting) input is "S1OUT"; output is "S1OUT"
- Step 3 (inter-tile) inputs are "S0OUT", "S0BND", "S1OUT", and "S2BOUT";
output is "PHASE2BND"
- Step 4 (final-tile) inputs are "S0OUT" and "PHASE2BND"; output goes to
GRASS maps: Map names are specified relative to "VTMPDIR", or with absolute path
(name beginning with /).
IOLibrary temporary streams will be in STREAM_DIR.
REFERENCES
-
Hazel, T., Toma, L., Vahrenhold, J., and Wickremesinghe, R. 2006.
TerraCost: a versatile and scalable approach to computing least-cost-path
surfaces for massive grid-based terrains. In: Proceedings of the
2006 ACM Symposium on Applied Computing (Dijon, France, April 23-27, 2006).
SAC '06. ACM, New York, NY, 52-57.
[ PDF ]
- Toma, L., 2006. TerraCost: Scalable Computation of Least-Cost-Path Surfaces. Talk at
FOSS4G 2006, Lausanne, Switzerland.
[ Abstract and PDF ]
SEE ALSO
r.cost,
r.drain,
r.walk
AUTHOR
Laura I. Toma, http://www.bowdoin.edu/~ltoma/research.html
Last changed: $Date$