# Best flow routing algorithm for determining location where spill enters stream?

What would be the best flow routing algorithm for determining the quickest (and by this I suppose I mean shortest) path that a spill would take when traveling to a stream?

My best educated guess would be that the D8 would provide the quickest path for a spill traveling from land to the stream. It minimizes dispersion (which would most likely slow the spill down) and maximizes velocity (ignoring surface friction due to different landcover types - if this can be ignored) by choosing the steepest path.

The end application would be in determining the overland flow path from a spill site to a stream/river reach that provides the earliest possible time for entry of the spill into the stream/river. There are different assumptions or starting datasets that could change the answer. For instance, a 30m digital elevation model (DEM) cold prove useful in a forested or agricultural area, but a 1m or sub-1m DEM might be necessary for sorting out the true flow path (and therefore the true shortest path) in a highly urbanized area. In either of these cases, however, once one has a DEM that he/she feels represents the terrain well enough for an analysis, which algorithm should they choose?

This query is borne out of trying to avoid calculating the distance from the spill to the stream/river reach using simple straight line geometry in a GIS tool, such as the proximity toolset in ArcMap.

Does anyone have any experience with this?

EDIT: Based on the responses so far, it seems that using a routing algorithm that allows for dispersion, and then calculating the shortest path out of the possible paths predicted by the algorithm, might be the solution I want. In the answer suggesting the use of TauDEM, the journal article that is linked to contains this image:

(image from Tesfa et al., 2011 - http://www.neng.usu.edu/cee/faculty/dtarb/Tesfa_EMS2011.pdf)

Examining the predicted flow path of the D-Inf algorithm, we see that several different paths are possible. Using such an algorithm, I suppose on could calculate the shortest path, the longest path, and a range of other statistics on the predicted pathways. If similar or near identical ground cover is found across the different pathways, then some combination of steepness and path length may dictate the quickest path? Which might be different from the shortest path? I'm starting to think I have to review my question and/or thought process - it may be necessary to incorporate equations/models governing the speed of overland flow along side the algorithms that examine possible flow pathways. I need to keep reading and ingesting the article, but I think that the answer lies within the ideas presented in the article - so for now I will mark the suggesting answer as correct.

• Notice I am not asking about the timing, which can be calculated using approximations based on the Saint Venant Equations (Kinematic wave, Diffusion wave, etc.) Dec 30, 2014 at 22:26
• Are you asking if a D8-based process is best or how to solve the problem using a D8 flow direction calculation? If you have a sufficiently detailed DEM then that should work well enough. I think that when you get to urbanised and very flat areas then you may need to start to look at how the problem is solved flood-routing models, depending on the size of the spill. Small features can have big effects in those situations as the liquid backs up against them. Jan 4, 2015 at 5:43
• More along the lines of whether a D8 process is best. Jan 4, 2015 at 5:49
• Unfortunately, no. The problem persists regardless of the projection because D8 discretizes directions into eight categories. This loses information. It allows water to flow only in directions that are multiples of 45 degrees. The best you can hope for is that on average, as you follow a computed flow path, it will tend to follow the direction of steepest descent. D8 exists because it is computationally simple and fast, not because it is such a great algorithm. Jan 5, 2015 at 16:06
• @whuber see Tarboton (1997) for good discussion of the limitations of the D8 technique (introduced in 1984) and use of newer methods (i.e. D∞ in TauDEM) to get around these limitations. Jan 5, 2015 at 20:21

Some good software for this purpose is TauDEM (Terrain Analysis Using Digital Elevation Models).

The software uses both D8 and so-called D-infinity (D∞) flow models, which is best illustrated on Fig. 1 of Tesfa et al. (2011). You can test which flow path method is quicker or more accurate for your area. Furthermore, both serial and parallel processing with any number of CPUs is supported. Section 2.2 of Tesfa et al. (2011) linked previously covers much of your questions of flow routing distances down to a stream (end point cells).

• Is one of the outputs of this model/software the total path length? Looking at one of the tables in the paper it appears it might be? Jan 5, 2015 at 5:29
• It's a raster of downstream distances at each grid point, I think. Jan 5, 2015 at 5:45

I have solved a similar problem for a municipality where if a water main breaks they wanted to know where the water goes and what infrastructure, streams, etc. are going to get impacted. If you are using ArcMap then you can use the Cost Path geoprocessing tool. Tool parameters:

• Input raster or feature destination data - a point representing your spill location
• Cost distance raster - a hydrologically corrected DEM
• Cost backlink raster - a flow direction raster generated from the above DEM using the Flow Direction geoprocessing tool.

Some notes:

• Cost path will calculate the shortest route between two points. In your case the route chosen will represent the path that the spill would travel along the surface of the DEM to its lowest elevation. In practice what happens is that the spill will travel along the surface until it hits a stream and then travel down that stream.
• You will need to convert the output raster from cost path to a line and then overlay it with your streams to determine the exact spot it hits the stream.
• The hydrologically corrected DEM is critical. Hydrologically corrected means that there are no unintended "sinks" where one pixel has an elevation value that is lower than all 8 surrounding pixels (i.e. there is no outlet). This is key because you are trying to create a surface that shows how water will flow from any pixel to the next. There is some reading material on the subject and some examples of tools to use to create such a surface in this pdf. The workshop from the pdf refers to tools from ArcHydro which can be freely downloaded here.
• Once you have a hydrologically corrected DEM you can then do things like watershed delineation and "predict" where streams should be located and make educated guess on how big that stream might be. This was useful in my project because if the water from the broken main goes into a stream I needed to get a sense of how big that stream was to know if it could handle the extra water.
• If your spill is a point source make sure to set the snap raster environment setting to your DEM raster otherwise you may not get correct results.
• What comparisons did you make between the CostPath output and calculations performed using other least-cost path algorithms? What field checks did you make to assess the accuracy of the CostPath output? These are the kinds of information that a request for a "best" procedure would be asking for. Jan 4, 2015 at 5:52
• Oli, thanks for walking me through the steps in ArcMap. I would more likely perform this calculation in a different piece of software, and most likely code it up on my own in Python. Focusing on ArcMap limits the flow path algorithm choices to D8 only. @whuber, perhaps this question is too broad? Jan 4, 2015 at 5:53
• It seems reasonably well-focused to me. Answers can add considerable value by sharing information about alternative algorithms or methods and documenting comparisons between them. How else could anyone justify a claim of "best"? Jan 4, 2015 at 5:56