Efficiently computing the drainage network on massive terrains using external memory flooding process.
No Thumbnail Available
Date
2015
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
We present EMFlow, a very efficient algorithm and its implementation, to compute
the drainage network (i.e. the flow direction and flow accumulation) on huge terrains
stored in external memory. Its utility lies in processing the large volume of high resolution
terrestrial data newly available, which internal memory algorithms cannot handle efficiently.
The flow direction is computed using an adaptation of our previous method RWFlood that
uses a flooding process to quickly remove internal depressions or basins. Flooding, proceeding
inward from the outside of the terrain, works oppositely to the common method of
computing downhill flow from the peaks. To reduce the number of I/O operations, EMFlow
adopts a new strategy to subdivide the terrain into islands that are processed separately. The
terrain cells are grouped into blocks that are stored in a special data structure managed as
a cache memory. EMFlow’s execution time was compared against the two most recent and
most efficient published methods: TerraFlow and r.watershed.seg. It was, on average, 25
and 110 times faster than TerraFlow and r.watershed.seg respectively. Also, EMFlow could
process larger datasets. Processing a 50000 × 50000 terrain on a machine with 2GB of
internal memory took about 4500 seconds, compared to 87000 seconds for TerraFlow while
r.watershed.seg failed on terrains larger than 15000×15000. On very small, say1000×1000
terrains, EMFlow takes under a second, compared to 6 and 20 seconds in r.watershed.seg
and TerraFlow respectively. So EMFlow could be a component of a future interactive system
where a user could modify terrain and immediately see the new hydrography
Description
Keywords
Terrain modeling, Hydrology, External memory
Citation
GOMES, T. L. et al. Efficiently computing the drainage network on massive terrains using external memory flooding process. Geoinformatica, Dordrecht, v. 19, p. 671-692, 2015. Disponível em: <https://link.springer.com/article/10.1007/s10707-015-0225-y>. Acesso em: 27 jul. 2017.