论文标题
1d和2d流程在地形上
1D and 2D Flow Routing on a Terrain
论文作者
论文摘要
地形分析中的一个重要问题是建模水如何通过形成通道和填充凹陷来造成洪水的水流如何造成洪水。在本文中，我们研究了许多相关问题：给定的地形$σ$，表示为带有$ n $ vertices的三角形$ xy $ - 单酮表面，降雨分布$ r $可能会随着时间而变化，可以随时间变化，确定多少水在给定的边缘上流动于给定的范围。我们开发了用于流量查询的内存以及I/O高效算法。 本文包含四个主要结果： (i) We present an internal-memory algorithm that preprocesses $Σ$ into a linear-size data structure that for a (possibly time varying) rain distribution $R$ can return the flow-rate functions of all edges of $Σ$ in $O(ρk+|ϕ| \log n)$ time, where $ρ$ is the number of sinks in $Σ$, $k$ is the number of times the rain distribution changes, and $ | ϕ | $是具有非零值的流量率函数的总复杂性； （ii）我们还提供了一种I/O高效算法，用于将$σ$预处理到线性大小的数据结构中，以便对于降雨分布$ r $，它可以使用$ O（\ text {stort {stort}（stort {stort}（| ϕ | ϕ |））和$ i/os和$ o（| \ o（| \ fog | \ fog | flog | ϕ | ϕ | ϕ）。 （iii）$σ$可以预处理到线性大小的数据结构中，以便在给定的降雨分布$ r $，在单流方向（SFD）模型下，边缘$（q，r）\σ$的流量率函数可以更有效地计算。 （iv）我们提出了一种用于计算二维通道的算法，使用曼宁方程式水流；一个广泛使用的经验方程将开放通道中的水流量与通道的几何形状以及通道中的水高。
An important problem in terrain analysis is modeling how water flows across a terrain creating floods by forming channels and filling depressions. In this paper we study a number of \emph{flow-query} related problems: Given a terrain $Σ$, represented as a triangulated $xy$-monotone surface with $n$ vertices, a rain distribution $R$ which may vary over time, determine how much water is flowing over a given edge as a function of time. We develop internal-memory as well as I/O-efficient algorithms for flow queries. This paper contains four main results: (i) We present an internal-memory algorithm that preprocesses $Σ$ into a linear-size data structure that for a (possibly time varying) rain distribution $R$ can return the flow-rate functions of all edges of $Σ$ in $O(ρk+|ϕ| \log n)$ time, where $ρ$ is the number of sinks in $Σ$, $k$ is the number of times the rain distribution changes, and $|ϕ|$ is the total complexity of the flow-rate functions that have non-zero values; (ii) We also present an I/O-efficient algorithm for preprocessing $Σ$ into a linear-size data structure so that for a rain distribution $R$, it can compute the flow-rate function of all edges using $O(\text{Sort}(|ϕ|))$ I/Os and $O(|ϕ| \log |ϕ|)$ internal computation time. (iii) $Σ$ can be preprocessed into a linear-size data structure so that for a given rain distribution $R$, the flow-rate function of an edge $(q,r) \in Σ$ under the single-flow direction (SFD) model can be computed more efficiently. (iv) We present an algorithm for computing the two-dimensional channel along which water flows using Manning's equation; a widely used empirical equation that relates the flow-rate of water in an open channel to the geometry of the channel along with the height of water in the channel.
