Flood-risk analysis on terrains under the multiflow-direction model
© 2018 held by the owner/author(s). Publication rights licensed to ACM. An important problem in terrain analysis is modeling how water flows across a terrain and creates floods by filling up depressions. In this paper we study a number of flood-risk related problems: Given a terrain, represented as a triangulated x -monotone surface with n vertices, a rain distribution R and a volume of rain, determine which portions of are flooded. We develop efficient algorithms for flood-risk analysis under the multiflow-directions (MFD) model, in which water at a point can flow along multiple downslope edges to more accurately represent flooding events. We present three main results: First, we present an O(nm)-time algorithm to answer a terrain-flood query: if it rains a volume according to a rain distribution R, determine what regions of will be flooded; here m is the number of sinks in . Second, we present a O(n logn)-time algorithm for preprocessing into a linear-size data structure for answering point-flood queries: given a rain distribution R, a volume of rain falling according to R, and point q ∈, determine whether q will be flooded. A point-flood query can be answered in O(nk) time, where k is the number of maximal depressions in containing the query point q. Alternately, we can preprocess in O(n logn+nm) time into an O(nm)-size data structure so that a point-flood query can be answered inO(|R|k+k 2 ) time, where |R| is the number of vertices in R with positive rain fall. Finally, we present algorithms for answering a flood-time query: given a rain distribution R and a point q ∈, determine the volume of rain that must fall before q is flooded. Assuming that the product of two k × k matrices can be computed in O(k ω ) time, we show that a flood-time query can be answered in O(nk + k ω ) time. We also give an -approximation algorithm, for > 1, that runs in O(nk+k 2 (log(n+log α )))-time, where is a variable on the terrain which depends on the ratio between depression volumes. We implemented our terrain-flooding algorithm and tested its efficacy and efficiency on real terrains.
Gis: Proceedings of the Acm International Symposium on Advances in Geographic Information Systems
Start / End Page
International Standard Book Number 13 (ISBN-13)
Digital Object Identifier (DOI)