1r.cost(1) GRASS GIS User's Manual r.cost(1)
2
3
4
6 r.cost - Creates a raster map showing the cumulative cost of moving
7 between different geographic locations on an input raster map whose
8 cell category values represent cost.
9
11 raster, cost surface, cumulative costs, cost allocation
12
14 r.cost
15 r.cost --help
16 r.cost [-knrib] input=name output=name [solver=name] [nearest=name]
17 [outdir=name] [start_points=name] [stop_points=name]
18 [start_raster=name] [start_coordinates=east,north[,east,north,...]]
19 [stop_coordinates=east,north[,east,north,...]] [max_cost=value]
20 [null_cost=value] [memory=memory in MB] [--overwrite] [--help]
21 [--verbose] [--quiet] [--ui]
22
23 Flags:
24 -k
25 Use the ’Knight’s move’; slower, but more accurate
26
27 -n
28 Keep null values in output raster map
29
30 -r
31 Start with values in raster map
32
33 -i
34 Print info about disk space and memory requirements and exit
35
36 -b
37 Create bitmask encoded directions
38
39 --overwrite
40 Allow output files to overwrite existing files
41
42 --help
43 Print usage summary
44
45 --verbose
46 Verbose module output
47
48 --quiet
49 Quiet module output
50
51 --ui
52 Force launching GUI dialog
53
54 Parameters:
55 input=name [required]
56 Name of input raster map containing grid cell cost information
57
58 output=name [required]
59 Name for output raster map
60
61 solver=name
62 Name of input raster map solving equal costs
63 Helper variable to pick a direction if two directions have equal
64 cumulative costs (smaller is better)
65
66 nearest=name
67 Name for output raster map with nearest start point
68
69 outdir=name
70 Name for output raster map to contain movement directions
71
72 start_points=name
73 Name of starting vector points map
74 Or data source for direct OGR access
75
76 stop_points=name
77 Name of stopping vector points map
78 Or data source for direct OGR access
79
80 start_raster=name
81 Name of starting raster points map
82
83 start_coordinates=east,north[,east,north,...]
84 Coordinates of starting point(s) (E,N)
85
86 stop_coordinates=east,north[,east,north,...]
87 Coordinates of stopping point(s) (E,N)
88
89 max_cost=value
90 Maximum cumulative cost
91 Default: 0
92
93 null_cost=value
94 Cost assigned to null cells. By default, null cells are excluded
95
96 memory=memory in MB
97 Maximum memory to be used (in MB)
98 Cache size for raster rows
99 Default: 300
100
102 r.cost determines the cumulative cost of moving to each cell on a cost
103 surface (the input raster map) from other user-specified cell(s) whose
104 locations are specified by their geographic coordinate(s). Each cell in
105 the original cost surface map will contain a category value which rep‐
106 resents the cost of traversing that cell. r.cost will produce 1) an
107 output raster map in which each cell contains the lowest total cost of
108 traversing the space between each cell and the user-specified points
109 (diagonal costs are multiplied by a factor that depends on the dimen‐
110 sions of the cell) and 2) a second raster map layer showing the move‐
111 ment direction to the next cell on the path back to the start point
112 (see Movement Direction). This module uses the current geographic
113 region settings. The output map will be of the same data format as the
114 input map, integer or floating point.
115
117 The input name is the name of a raster map whose category values repre‐
118 sent the surface cost. The output name is the name of the resultant
119 raster map of cumulative cost. The outdir name is the name of the
120 resultant raster map of movement directions (see Movement Direction).
121
122 r.cost can be run with three different methods of identifying the
123 starting point(s). One or more points (geographic coordinate pairs) can
124 be provided as specified start_coordinates on the command line, from a
125 vector points file, or from a raster map. All non-NULL cells are con‐
126 sidered to be starting points.
127
128 Each x,y start_coordinates pair gives the geographic location of a
129 point from which the transportation cost should be figured. As many
130 points as desired can be entered by the user. These starting points can
131 also be read from a vector points file through the start_points option
132 or from a raster map through the start_raster option.
133
134 r.cost will stop cumulating costs when either max_cost is reached, or
135 one of the stop points given with stop_coordinates is reached. Alter‐
136 natively, the stop points can be read from a vector points file with
137 the stop_points option. During execution, once the cumulative cost to
138 all stopping points has been determined, processing stops.
139 Both sites read from a vector points file and those given on the com‐
140 mand line will be processed.
141
142 The null cells in the input map can be assigned a (positive floating
143 point) cost with the null_cost option.
144 When input map null cells are given a cost with the null_cost option,
145 the corresponding cells in the output map are no longer null cells. By
146 using the -n flag, the null cells of the input map are retained as null
147 cells in the output map.
148
149 As r.cost can run for a very long time, it can be useful to use the --v
150 verbose flag to track progress.
151
152 The Knight’s move (-k flag) may be used to improve the accuracy of the
153 output. In the diagram below, the center location (O) represents a grid
154 cell from which cumulative distances are calculated. Those neighbors
155 marked with an X are always considered for cumulative cost updates.
156 With the -k option, the neighbors marked with a K are also considered.
157 . . . . . . . . . . . . . . .
158 . . . K . . K . . .
159 . . . . . . . . . . . . . . .
160 . . K . X . X . X . K . .
161 . . . . . . . . . . . . . . .
162 . . . X . O . X . . .
163 . . . . . . . . . . . . . . .
164 . . K . X . X . X . K . .
165 . . . . . . . . . . . . . . .
166 . . . K . . K . . .
167 . . . . . . . . . . . . . . .
168
169 Knight’s move example:
170
171 Flat cost surface without (left pane) and with the knight’s
172 move (right pane). The default is to grow the cost outwards
173 in 8 directions. Using the knight’s move grows it outwards
174 in 16 directions.
175
176
177 If the nearest output parameter is specified, the module will calculate
178 for each cell its nearest starting point based on the minimized accumu‐
179 lative cost while moving over the cost map.
180
181 The solver option helps to select a particular direction in case of
182 multiple directions with equal costs. Sometimes fields with equal cumu‐
183 lative costs exist and multiple paths with equal costs would lead from
184 a start point to a stop point. By default, a path along the edge of
185 such a field would be produced or multiple paths of equal costs with
186 the -b flag. An additional variable can be supplied with the solver
187 option to help the algorithm pick a particular direction.
188
189 Example for solving multiple directions:
190
191 A field of equal cumulative costs with multiple paths
192 (black). By default a path along the edge will be selected
193 (red). Path selection can be controlled with the solver
194 option (blue).
195
196
197 Multiple directions can be solved as in the above example with the fol‐
198 lowing steps:
199
200 1 Create multiple directions with r.cost/r.walk using the -b flag
201
202 2 Extract paths using r.path format=bitmask
203
204 3 Calculate the distance from NULL cells to paths using
205 r.grow.distance -n input=<paths from r.path>
206
207 4 Invert the sign of the distances with r.mapcalc because for the
208 solver smaller is better, and here we want to get the center of
209 an area with multiple directions
210
211 5 Use thise negative distances as solver for a second pass of
212 r.cost
213
214 6 Extract paths again with r.path to get a geometrically optimized
215 solution
216
218 By default null cells in the input raster map are excluded from the
219 algorithm, and thus retained in the output map.
220
221 If one wants r.cost to transparently cross any region of null cells,
222 the null_cost=0.0 option should be used. Then null cells just propagate
223 the adjacent costs. These cells can be retained as null cells in the
224 output map by using the -n flag.
225
227 Paths from any point to the nearest starting point of r.cost can be
228 extracted with r.path by using the direction output map of r.cost.
229
230 Algorithm notes
231 The fundamental approach to calculating minimum travel cost is as fol‐
232 lows:
233
234 The user generates a raster map indicating the cost of traversing each
235 cell in the north-south and east-west directions. This map, along with
236 a set of starting points are submitted to r.cost. The starting points
237 are put into a heap of cells from which costs to the adjacent cells are
238 to be calculated. The cell on the heap with the lowest cumulative cost
239 is selected for computing costs to the neighboring cells. Costs are
240 computed and those cells are put on the heap and the originating cell
241 is finalized. This process of selecting the lowest cumulative cost
242 cell, computing costs to the neighbors, putting the neighbors on the
243 heap and removing the originating cell from the heap continues until
244 the heap is empty.
245
246 The most time consuming aspect of this algorithm is the management of
247 the heap of cells for which cumulative costs have been at least ini‐
248 tially computed. r.cost uses a minimum heap for efficiently tracking
249 the next cell with the lowest cumulative costs.
250
251 r.cost, like most all GRASS raster programs, is also made to be run on
252 maps larger that can fit in available computer memory. As the algorithm
253 works through the dynamic heap of cells it can move almost randomly
254 around the entire area. r.cost divides the entire area into a number of
255 pieces and swaps these pieces in and out of memory (to and from disk)
256 as needed. This provides a virtual memory approach optimally designed
257 for 2-D raster maps. The amount of memory to be used by r.cost can be
258 controlled with the memory option, default is 300 MB. For systems with
259 less memory this value will have to be set to a lower value.
260
262 Consider the following example:
263 Input:
264 COST SURFACE
265 . . . . . . . . . . . . . . .
266 . 2 . 2 . 1 . 1 . 5 . 5 . 5 .
267 . . . . . . . . . . . . . . .
268 . 2 . 2 . 8 . 8 . 5 . 2 . 1 .
269 . . . . . . . . . . . . . . .
270 . 7 . 1 . 1 . 8 . 2 . 2 . 2 .
271 . . . . . . . . . . . . . . .
272 . 8 . 7 . 8 . 8 . 8 . 8 . 5 .
273 . . . . . . . . . . _____ . .
274 . 8 . 8 . 1 . 1 . 5 | 3 | 9 .
275 . . . . . . . . . . |___| . .
276 . 8 . 1 . 1 . 2 . 5 . 3 . 9 .
277 . . . . . . . . . . . . . . .
278 Output (using -k): Output (not using -k):
279 CUMULATIVE COST SURFACE CUMULATIVE COST SURFACE
280 . . . . . . . . . . . . . . . . . . . * * * * * . . . . . .
281 . 21. 21. 20. 19. 17. 15. 14. . 22. 21* 21* 20* 17. 15. 14.
282 . . . . . . . . . . . . . . . . . . . * * * * * . . . . . .
283 . 20. 19. 22. 19. 15. 12. 11. . 20. 19. 22* 20* 15. 12. 11.
284 . . . . . . . . . . . . . . . . . . . . . * * * * * . . . .
285 . 22. 18. 17. 17. 12. 11. 9. . 22. 18. 17* 18* 13* 11. 9.
286 . . . . . . . . . . . . . . . . . . . . . * * * * * . . . .
287 . 21. 14. 13. 12. 8. 6. 6. . 21. 14. 13. 12. 8. 6. 6.
288 . . . . . . . . . . _____. . . . . . . . . . . . . . . . .
289 . 16. 13. 8. 7. 4 | 0 | 6. . 16. 13. 8. 7 . 4. 0. 6.
290 . . . . . . . . . . |___|. . . . . . . . . . . . . . . . .
291 . 14. 9. 8. 9. 6. 3. 8. . 14. 9. 8. 9 . 6. 3. 8.
292 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
293
294 The user-provided starting location in the above example is the boxed 3
295 in the above input map. The costs in the output map represent the total
296 cost of moving from each box ("cell") to one or more (here, only one)
297 starting location(s). Cells surrounded by asterisks are those that are
298 different between operations using and not using the Knight’s move (-k)
299 option.
300
301 Output analysis
302 The output map can be viewed, for example, as an elevation model in
303 which the starting location(s) is/are the lowest point(s). Outputs from
304 r.cost can be used as inputs to r.path , in order to trace the
305 least-cost path given by this model between any given cell and the
306 r.cost starting location(s). The two programs, when used together, gen‐
307 erate least-cost paths or corridors between any two map locations
308 (cells).
309
310 Shortest distance surfaces
311 The r.cost module allows for computing the shortest distance of each
312 pixel from raster lines, such as determining the shortest distances of
313 households to the nearby road. For this cost surfaces with cost value 1
314 are used. The calculation is done with r.cost as follows (example for
315 Spearfish region):
316 g.region raster=roads -p
317 r.mapcalc "area.one = 1"
318 r.cost -k input=area.one output=distance start_raster=roads
319 d.rast distance
320 d.rast.num distance
321 #transform to metric distance from cell distance using the raster resolution:
322 r.mapcalc "dist_meters = distance * (ewres()+nsres())/2."
323 d.rast dist_meters
324
326 The movement direction surface is created to record the sequence of
327 movements that created the cost accumulation surface. This movement
328 direction surface can be used by r.path to recover a path from an end
329 point back to the start point. The direction of each cell points
330 towards the next cell. The directions are recorded as degrees CCW from
331 East:
332 112.5 67.5 i.e. a cell with the value 135
333 157.5 135 90 45 22.5 means the next cell is to the north-west
334 180 x 360
335 202.5 225 270 315 337.5
336 247.5 292.5
337
338 Cost allocation
339 Example: calculation of the cost allocation map "costalloc" and the
340 cumulative cost map "costsurf" for given starting points (map
341 "sources") and given cost raster map "costs":
342 r.cost input=costs start_raster=sources output=costsurf nearest=costalloc
343
344 Find the minimum cost path
345 Once r.cost computes the cumulative cost map and an associated movement
346 direction map, r.path can be used to find the minimum cost path.
347
349 r.walk, r.path, r.in.ascii, r.mapcalc, r.out.ascii
350
352 Antony Awaida, Intelligent Engineering Systems Laboratory, M.I.T.
353 James Westervelt, U.S.Army Construction Engineering Research Laboratory
354 Updated for Grass 5 by Pierre de Mouveaux (pmx@audiovu.com)
355 Markus Metz
356 Multiple path directions sponsored by mundialis
357
359 Available at: r.cost source code (history)
360
361 Main index | Raster index | Topics index | Keywords index | Graphical
362 index | Full index
363
364 © 2003-2020 GRASS Development Team, GRASS GIS 7.8.5 Reference Manual
365
366
367
368GRASS 7.8.5 r.cost(1)