← Back to branch summary

~ubuntu-branches/ubuntu/vivid/grass/vivid-proposed

« back to all changes in this revision

Viewing changes to raster/r.terraflow/r.terraflow.html

  • Committer: Package Import Robot
  • Author(s): Bas Couwenberg
  • Date: 2015-02-20 23:12:08 UTC
  • mfrom: (8.2.6 experimental)
  • Revision ID: package-import@ubuntu.com-20150220231208-1u6qvqm84v430b10
Tags: 7.0.0-1~exp1
* New upstream release.
* Update python-ctypes-ternary.patch to use if/else instead of and/or.
* Drop check4dev patch, rely on upstream check.
* Add build dependency on libpq-dev to grass-dev for libpq-fe.h.
* Drop patches applied upstream, refresh remaining patches.
* Update symlinks for images switched from jpg to png.

Show diffs side-by-side

added added

removed removed

Lines of Context:
raster/r.terraflow/r.terraflow.html
 
1
<h2>DESCRIPTION</h2>
 
2
 
 
3
<p><em>r.terraflow</em> takes as input a raster digital elevation
 
4
model (DEM) and computes the flow direction raster and the flow
 
5
accumulation raster, as well as the flooded elevation raster,
 
6
sink-watershed raster (partition into watersheds around sinks) and TCI
 
7
(topographic convergence index) raster maps.
 
8
 
 
9
<p><em>r.terraflow</em> computes these rasters using well-known
 
10
approaches, with the difference that its emphasis is on the
 
11
computational complexity of the algorithms, rather than on modeling
 
12
realistic flow.  <em>r.terraflow</em> emerged from the necessity of
 
13
having scalable software able to process efficiently very large
 
14
terrains.  It is based on theoretically optimal algorithms developed
 
15
in the framework of I/O-efficient algorithms.  <em>r.terraflow</em>
 
16
was designed and optimized especially for massive grids and is able to
 
17
process terrains which were impractical with similar functions
 
18
existing in other GIS systems.
 
19
 
 
20
<p>Flow directions are computed using either the MFD (Multiple Flow
 
21
Direction) model or the SFD (Single Flow Direction, or D8) model,
 
22
illustrated below. Both methods compute downslope flow directions by
 
23
inspecting the 3-by-3 window around the current cell. The SFD method
 
24
assigns a unique flow direction towards the steepest downslope
 
25
neighbor. The MFD method assigns multiple flow directions towards all
 
26
downslope neighbors.
 
27
 
 
28
<p><table width="80%" align=center>
 
29
 <tr>
 
30
  <th><img src="rterraflow_dir2.png" alt="r.terraflow SFD"></th>
 
31
  <th><img src="rterraflow_dir3.png" alt="r.terraflow MFD"></th>
 
32
 </tr>
 
33
 <tr>
 
34
  <th>Flow direction to steepest<br> downslope neighbor (SFD).</th>
 
35
  <th>Flow direction to all<br> downslope neighbors (MFD).</th>
 
36
 </tr>
 
37
</table>
 
38
 
 
39
 
 
40
<p>The SFD and the MFD method cannot compute flow directions for
 
41
cells which have the same height as all their neighbors (flat areas)
 
42
or cells which do not have downslope neighbors (one-cell pits).
 
43
 
 
44
<ul>
 
45
  <li>On plateaus (flat areas that spill out) <em>r.terraflow</em>
 
46
routes flow so that globally the flow goes towards the spill cells of
 
47
the plateaus.
 
48
 
 
49
  <li>On sinks (flat areas that do not spill out, including one-cell
 
50
pits) <em>r.terraflow</em> assigns flow by flooding the terrain until
 
51
all the sinks are filled and assigning flow directions on the filled
 
52
terrain.
 
53
</ul>
 
54
 
 
55
<p>In order to flood the terrain, <em>r.terraflow</em> identifies all
 
56
sinks and partitions the terrain into sink-watersheds (a
 
57
sink-watershed contains all the cells that flow into that sink),
 
58
builds a graph representing the adjacency information of the
 
59
sink-watersheds, and uses this sink-watershed graph to merge
 
60
watersheds into each other along their lowest common boundary until
 
61
all watersheds have a flow path outside the terrain. Flooding produces
 
62
a sink-less terrain in which every cell has a downslope flow path
 
63
leading outside the terrain and therefore every cell in the terrain
 
64
can be assigned SFD/MFD flow directions as above.
 
65
 
 
66
<p>Once flow directions are computed for every cell in the terrain,
 
67
<em>r.terraflow</em> computes flow accumulation by routing water using
 
68
the flow directions and keeping track of how much water flows through
 
69
each cell.
 
70
 
 
71
<p>If flow accumulation of a cell is larger than the value given by the
 
72
<b>d8cut</b> option, then
 
73
the flow of this cell is routed to its neighbors using the SFD (D8)
 
74
model. This option affects only the flow accumulation raster and is
 
75
meaningful only for MFD flow (i.e. if the -s flag is not used); If
 
76
this option is used for SFD flow it is ignored. The default value of
 
77
<b>d8cut</b> is <i>infinity</i>.
 
78
 
 
79
<p><em>r.terraflow</em> also computes the tci raster (topographic convergence
 
80
index, defined as the logarithm of the ratio of flow accumulation and
 
81
local slope).
 
82
 
 
83
<p>For more details on the algorithms see [1,2,3] below.
 
84
 
 
85
 
 
86
<h2>NOTES</h2>
 
87
 
 
88
One of the techniques used by <em>r.terraflow</em> is the
 
89
space-time trade-off. In particular, in order to avoid searches, which
 
90
are I/O-expensive, <em>r.terraflow</em> computes and works with an
 
91
augmented elevation raster in which each cell stores relevant
 
92
information about its 8 neighbors, in total up to 80B per cell.  As a
 
93
result <em>r.terraflow</em> works with intermediate temporary files
 
94
that may be up to 80N bytes, where N is the number of cells (rows x
 
95
columns) in the elevation raster (more precisely, 80K bytes, where K
 
96
is the number of valid (not no-data) cells in the input elevation
 
97
raster).
 
98
<p>All these intermediate temporary files are stored in the path specified
 
99
by the <b>STREAM_DIR</b> option. Note: <b>STREAM_DIR</b> must contain
 
100
enough free disk space in order to store up to 2 x 80N bytes.
 
101
 
 
102
<p>The <b>memory</b> option can be used to set the maximum amount of main
 
103
memory (RAM) the module will use during processing. In practice its
 
104
<i>value</i> should be an underestimate of the amount of available
 
105
(free) main memory on the machine. <em>r.terraflow</em> will use at
 
106
all times at most this much memory, and the virtual memory system
 
107
(swap space) will never be used. The default value is 300 MB.
 
108
 
 
109
<p>The <b>stats</b> option defines the name of the file that contains the
 
110
statistics (stats) of the run.
 
111
 
 
112
<p><em>r.terraflow</em> has a limit on the number of rows and columns
 
113
(max 32,767 each).
 
114
 
 
115
<p>The internal type used by <em>r.terraflow</em> to store elevations
 
116
can be defined at compile-time. By default, <em>r.terraflow</em> is
 
117
compiled to store elevations internally as floats. Other versions can be
 
118
created by the user if needed.
 
119
 
 
120
<p>Hints concerning compilation with storage of elevations internally as
 
121
shorts:
 
122
<br>such a version uses less space (up to 60B per cell, up
 
123
to 60N intermediate file) and therefore is more space and time
 
124
efficient. <em>r.terraflow</em> is intended for use with floating
 
125
point raster data (FCELL), and <em>r.terraflow (short)</em> with integer
 
126
raster data (CELL) in which the maximum elevation does not exceed the
 
127
value of a short SHRT_MAX=32767 (this is not a constraint for any
 
128
terrain data of the Earth, if elevation is stored in meters).
 
129
Both <em>r.terraflow</em> and <em>r.terraflow (short)</em> work with
 
130
input elevation rasters which can be either integer, floating point or
 
131
double (CELL, FCELL, DCELL). If the input raster contains a value that
 
132
exceeds the allowed internal range (short for
 
133
<em>r.terraflow (short)</em>, float for <em>r.terraflow</em>), the
 
134
program exits with a warning message. Otherwise, if all values in the
 
135
input elevation raster are in range, they will be converted
 
136
(truncated) to the internal elevation type (short for
 
137
<em>r.terraflow (short)</em>, float for <em>r.terraflow</em>). In this
 
138
case precision may be lost and artificial flat areas may be created.
 
139
For instance, if <em>r.terraflow (short)</em> is used with floating
 
140
point raster data (FCELL or DCELL), the values of the elevation will
 
141
be truncated as shorts. This may create artificial flat areas, and the
 
142
output of <em>r.terraflow (short)</em> may be less realistic than those
 
143
of <em>r.terraflow</em> on floating point raster data.
 
144
The outputs of <em>r.terraflow (short)</em> and <em>r.terraflow</em> are
 
145
identical for integer raster data (CELL maps).
 
146
 
 
147
 
 
148
<h2>EXAMPLES</h2>
 
149
 
 
150
Example for small area in North Carolina sample dataset:
 
151
<div class="code"><pre>
 
152
g.region raster=elev_lid792_1m
 
153
r.terraflow elevation=elev_lid792_1m filled=elev_lid792_1m_filled \
 
154
    direction=elev_lid792_1m_direction swatershed=elev_lid792_1m_swatershed \
 
155
    accumulation=elev_lid792_1m_accumulation tci=elev_lid792_1m_tci
 
156
</pre></div>
 
157
 
 
158
<div align="center" style="margin: 10px">
 
159
<img src="rterraflow_accumulation.png" border=0><br>
 
160
<i>Flow accumulation</i>
 
161
</div>
 
162
<!--
 
163
image generated using
 
164
d.mon wx0
 
165
d.rast elev_lid792_1m
 
166
d.rast elev_lid792_1m_accumulation
 
167
save image to files
 
168
crop the background using Gimp or ImageMagic
 
169
mogrify -trim *.png
 
170
some bounding box problems noticed when opening mogrify result in Gimp
 
171
-->
 
172
 
 
173
<p>
 
174
Spearfish sample data set:
 
175
 
 
176
<div class="code"><pre>
 
177
g.region raster=elevation.10m -p
 
178
r.terraflow elev=elevation.10m filled=elevation10m.filled \
 
179
    dir=elevation10m.mfdir swatershed=elevation10m.watershed \
 
180
    accumulation=elevation10m.accu tci=elevation10m.tci
 
181
</pre></div>
 
182
 
 
183
<div class="code"><pre>
 
184
g.region raster=elevation.10m -p
 
185
r.terraflow elev=elevation.10m filled=elevation10m.filled \
 
186
    dir=elevation10m.mfdir swatershed=elevation10m.watershed \
 
187
    accumulation=elevation10m.accu tci=elevation10m.tci d8cut=500 memory=800 \
 
188
    stats=elevation10mstats.txt 
 
189
</pre></div>
 
190
 
 
191
 
 
192
 
 
193
<h2>SEE ALSO</h2>
 
194
 
 
195
<em>
 
196
<a href="r.flow.html">r.flow</a>,
 
197
<a href="r.basins.fill.html">r.basins.fill</a>,
 
198
<a href="r.drain.html">r.drain</a>,
 
199
<a href="r.topidx.html">r.topidx</a>,
 
200
<a href="r.topmodel.html">r.topmodel</a>,
 
201
<a href="r.water.outlet.html">r.water.outlet</a>,
 
202
<a href="r.watershed.html">r.watershed</a>
 
203
</em>
 
204
 
 
205
 
 
206
 
 
207
<h2>AUTHORS</h2>
 
208
 
 
209
<dl>
 
210
  <dt>Original version of program: The
 
211
        <a href="http://www.cs.duke.edu/geo*/terraflow/">TerraFlow</a> project,
 
212
        1999, Duke University.
 
213
        <dd><a href="http://www.daimi.au.dk/~large/">Lars Arge</a>,
 
214
                <a href="http://www.cs.duke.edu/~chase/">Jeff Chase</a>,
 
215
        <a href="http://www.env.duke.edu/faculty/bios/halpin.html">Pat Halpin</a>,
 
216
        <a href="http://www.bowdoin.edu/~ltoma/">Laura Toma</a>,
 
217
        <a href="http://www.env.duke.edu/faculty/bios/urban.html">Dean Urban</a>,
 
218
        <a href="http://www.science.purdue.edu/jsv/">Jeff Vitter</a>,
 
219
        Rajiv Wickremesinghe.
 
220
       
 
221
  <dt>Porting to GRASS GIS, 2002:
 
222
    <dd> <a href="http://www.daimi.au.dk/~large/">Lars Arge</a>,
 
223
             <a href="http://www4.ncsu.edu/~hmitaso/index.html">Helena Mitasova,</a>
 
224
                 <a href="http://www.bowdoin.edu/~ltoma/">Laura Toma</a>. 
 
225
           
 
226
        <dt>Contact: <a href="mailto:ltoma@bowdoin.edu "> Laura Toma</a></dt>
 
227
</dl>
 
228
 
 
229
 
 
230
<h2>REFERENCES</h2>
 
231
 
 
232
<ol>
 
233
  <li> The <a href="http://www.cs.duke.edu/geo*/terraflow/">TerraFlow</a> project at Duke University
 
234
  <li><A NAME="arge:drainage"
 
235
       HREF="http://www.cs.duke.edu/geo*/terraflow/papers/alenex00_drainage.ps.gz">
 
236
       I/O-efficient algorithms for problems on grid-based
 
237
       terrains</a>.  Lars Arge, Laura Toma, and Jeffrey S. Vitter. In
 
238
       <em>Proc. Workshop on Algorithm Engineering and Experimentation</em>,
 
239
       2000. To appear in <em>Journal of Experimental Algorithms</em>.
 
240
       
 
241
  <li><A NAME="terraflow:acmgis01"
 
242
       HREF="http://www.cs.duke.edu/geo*/terraflow/papers/acmgis01_terraflow.pdf">
 
243
       Flow computation on massive grids</a>.
 
244
       Lars Arge, Jeffrey S. Chase, Patrick N. Halpin, Laura Toma,
 
245
       Jeffrey S. Vitter, Dean Urban and Rajiv Wickremesinghe. In
 
246
       <em>Proc. ACM Symposium on Advances in Geographic Information
 
247
       Systems</em>, 2001.
 
248
       
 
249
  <li><A NAME="terraflow:geoinformatica"
 
250
       HREF="http://www.cs.duke.edu/geo*/terraflow/papers/journal_terraflow.pdf">
 
251
       Flow computation on massive grid terrains</a>.
 
252
       Lars Arge, Jeffrey S. Chase, Patrick N. Halpin, Laura Toma,
 
253
       Jeffrey S. Vitter, Dean Urban and Rajiv Wickremesinghe.
 
254
       In <em>GeoInformatica, International Journal on
 
255
       Advances of Computer Science for Geographic Information
 
256
       Systems</em>, 7(4):283-313, December 2003.
 
257
</ol>
 
258
 
 
259
<p><i>Last changed: $Date: 2015-01-14 09:26:47 +0100 (Wed, 14 Jan 2015) $</i>