Flow Routing on Flat TerrainsTaylor HamiltonDepartment of Computer ScienceSwarthmore [email protected] ThronDepartment of Computer ScienceSwarthmore [email protected] current flow routing algorithms usedigital elevation models (DEMs) to con-struct flow models. In order to success-fully use current techniques for flow rout-ing, they flood local minima and then finda way of routing the flow across the flatsurfaces. In this paper, we examine an al-ternative method for computing flow rout-ing on these flooded surfaces that takesinto account the original elevation data.Our approach is based upon Dijkstra’s sin-gle source shortest path algorithm. We setthe distance between two adjacent cells tobe the elevation of one of the cells. Whileour results are not yet ideal, altering ourdistance formula shows promise for im-provement.1 IntroductionA current problem in geographic information sys-tems is the automatic extraction of river networksfrom a set of elevation data using the method of flowaccumulation. Calculating river networks is usefulin determining flood insurance zones.The basic idea for solving this problem is rela-tively simple: for each elevation point, route flow tothe neighbor with the steepest downhill slope. Thismethod is effective as long as there are no local min-ima. Local minima will be pits or valleys in whichthe water will get trapped. Ideally, all water shouldflow to some outlet point at the edge of the grid.Current algorithms (Jenson and Domingue, 1988;Garbrecht and Martz, 1997; Soille and Colombo,2003) tend to deal with this problem by flooding theminima until they are all removed. This approach isjustified by the assumption that minima are the ac-cidental result of poor sampling in the original data.However, this is not always the case. Many minimaare caused by large-scale terrain features, such as abridge over a river. When these minima get flooded,useful information about the underlying river is lost,as can be seen in Figure 1.These flooding algorithms create large flat sur-faces, which cause a new problem in flow rout-ing. Without a steepest downslope neighbor it isnot immediately obvious in which direction the wa-ter should flow across the surface.Several algorithms have been developed that at-tempt to solve the problem of flow routing over flatterrain. A side effect common to all these algorithmsis that they fail to use information about the originalterrain with their flat terrain flow routing algorithms.We have developed an algorithm to route flow acrossflat surfaces that takes into account the original ter-rain. This provides river networks that more accu-rately match reality.2 Related WorkCurrent algorithms for solving this problem do notproduce ideal results. Jenson and Domingue (1988)focussed mainly on flooding and their method forflow routing on flat surfaces was not very involved.For each point on a flat surface, they assigned theflow to be in the direction directly towards the out-let. This resulted in artificial looking river networksFigure 1: Original and flooded elevation databecause of long stretches of parallel lines.Garbrecht and Martz (1997) improved upon thisalgorithm by not only routing flow towards the out-let, but also away from the bordering high terrain.This provided more natural looking river networks.However, as these river networks do not take into ac-count the underlying elevations, they do not alwaysaccurately model the true flow of water in the region.Soille et al. (2003) proposed the method of carv-ing as opposed to flooding for removing minima,which reduces the number of flat areas. They alsoproposed a flat terrain flow routing algorithm that isan improvement on Garbrecht and Martz’s method.Although Soille’s algorithm is an improvement, ithas the same fundamental issues as that of Garbrechtand Martz.3 MethodsOur algorithm focuses on improving flow routingover flat terrains. To accomplish this, we use boththe flooded terrain information and the original el-evation data. The flooded terrain indicates the ar-eas on which to concentrate, and the original terrainprovides the elevation data needed for our method.We use Dijkstra’s algorithm to calculate the short-est path to the spill points. We vary the metric forcomputing the distance between two adjacent cells.We begin with digital elevation models in theGRASS ASCII format: one of the original terrainand one with the local minima flooded. We find thespill points, cells adjacent to the flooded terrain withlower elevations.We used a single source shortest path algorithmto calculate flow directions for flat areas. This al-gorithm treats our grid as a connected graph whereeach cell is connected to its eight neighbors. Theweights of the edges can be chosen independentlyof the algorithm, and we experiment with several op-tions.To compute the single source shortest path, weused Dijkstra’s algorithm. The algorithm begins byinitializing all the path lengths of any cell to the spillpoint to infinity. We create a priority queue that con-tains the spill points, and set their path lengths tozero. We continue extracting the point from the pri-ority queue with the minimum path length until thequeue is empty. Each time we remove a point, welook at each of its neighbors and update their pathsif the path through the current point is shorter thanthe stored path. We then add each updated neighborto the priority queue.When the algorithm is finished, the result is a for-est that spans the area of interest, where each tree isrooted at a spill point. The leaves of the trees are thepoints farthest away from the spill points. The pathfrom a node to the root of a tree is the shortest pathto a spill point.We can use these trees to calculate flow accumula-tion. We imagine that a unit of water falls onto eachcell in the grid. Using the flow directions of eachcell, we can determine the amount of water that ac-cumulates in each cell. Let p be any cell and F (p)Figure 2: River networks and flow directions using the Euclidean distance metricFigure 3: River networks and flow directions using Soille’s algorithmbe the set of cells flowing into p.acc(p) = 1 +Xq∈F (p)acc(q)We calculate the flow accumulations of a node inthe forest as the sum of the flows of each of its chil-dren plus one. A grid showing cells whose flow ac-cumulations are greater than some threshold shouldshow the locations of the rivers of the terrain.Our algorithm outputs GRASS ASCII files