# Given a terrain, how to draw the stream flow path?

Assuming I have a terrain, as usual the terrain has ridges, creeks and all the characteristics that you can find on a real life map. Water flows from the top of the mountain into lower area, the path that water flows is termed stream flow path.

The terrain is given in terms of triangular irregular network ( TIN), which each point $p(x,y)$ has a $z$ value. How to use this information to construct the stream flow path? What is the physics behind this?

Edit: Just wonder is there any papers on this?

-
This is a very complex problem, also depending on boundary and initial conditions, gravity, terrain type, forcings... You would need to do a full CFD simulation. –  mbq Sep 14 '11 at 10:49
It depends. You can come up with very complicated terrain where fast flow means that the water may not take the most direct route to the bottom. You can even make water jump a gap (think urination, sorry for the crude example). However, if you can work in the limit of low slow flow then you can essentially take the steepest descent, with local minima being exited be the lowest gap (i.e. they fill up until they can't fill up any more). This is much simpler to calculate. It is also easy to verify that your assumption of slow flow was valid once you do have the path. –  Joe Fitzsimons Sep 14 '11 at 11:22
@Joe, can you expand your comment into full answer? More specifically, I would be interested to see how you prove that in low slow flow limit the problem can be tacked by steepest descent, and I would like to know how steepest descent applies to low slow flow limit. –  Graviton Sep 14 '11 at 12:21
@mbq, I appreciate the magnitude of the problem. But assuming that the terrain information is all that I have, is there anyway to derive some crude estimation for this purpose? –  Graviton Sep 14 '11 at 12:22
Guess why flow at low Re number is called "potential flow". –  Georg Sep 14 '11 at 14:51

1) Let us first ignore the technical issues concerning a triangulated irregular network and just discuss the idealized smooth problem where there is given a smooth height profile $z=\phi(x,y)$ of the terrain. One can locally introduce a stream function $\psi=\psi(x,y)$ such that the curves

$$\psi(x,y)~=~{\rm constant}$$

represent the streamlines. (However, there are global obstructions, see item (4) below.) The gradients of $\psi$ and $\phi$ must be perpendicular,

$$\nabla\psi \cdot \nabla\phi~=~ \frac{\partial \psi}{\partial x}\frac{\partial \phi}{\partial x}+\frac{\partial \psi}{\partial y}\frac{\partial \phi}{\partial y} ~=~0. \qquad (1)$$

This is a 1st-order linear PDE in $\psi$ in two variables $(x,y)$. Its solution $\psi$ formally solves the smooth problem locally.

2) If moreover the horizontal fluid velocity field $(u,v)$ is divergence-free

$$\frac{\partial u}{\partial x}+ \frac{\partial v}{\partial y} ~=~0,$$

one can demand that

$$u = \frac{\partial \psi}{\partial y}, \qquad v = -\frac{\partial \psi}{\partial x}.$$

3) If furthermore $(u,v)$ is also curl-free (=vortex-free), then the stream function $\psi$ becomes a harmonic function. See also flownets.

4) Global obstructions. The streamfunction $\psi$ is ill-defined in sources and sinks, i.e. in local extrema.

5) Now let us comment on the triangulated surface, with vertices, edges and faces. If one (instead of introducing a streamfunction $\psi$) just solve the problem one-streamline-at-the-time, one could end up with streamlines that un-physically cross each other because of numerical errors. Solving in terms of the streamfunction $\psi$ protects against such unphysical solutions locally.

6) Let $\phi$ and $\psi$ be defined on the vertices. The gradients $\nabla\psi$ and $\nabla\phi$ naturally live on the faces, i.e. the dual graph, so that the equation (1) can be made discrete.

-
This answer is not so great--- you are doing formal manipulations that are useless in this context. The function psi is much more involved than the streamlines themselves, which are found by solving an ODE at each point, and there are essential numerical issues caused by the non-differentiability of the terrain. –  Ron Maimon Nov 21 '11 at 17:15
Well, it is explicitly stated in the first sentence that the answer(v1) will only deal with smooth height profiles. However I believe that above construction has actually a wider scope. A discretization of the stream function $\psi$ could be useful for OP's problem. –  Qmechanic Nov 21 '11 at 18:52
I updated the answer. –  Qmechanic Nov 22 '11 at 11:34

I'll try to give some starting ideas.

A triangulated surface will not be smooth but it may be useful to understand how the problem would work on a smooth surface. From each point water could be assumed to flow in the steepest direction going down. This ignores momentum of the water which could affect the path and even provide water falls. If you want to model that your job is going to be harder.

If the height $z(x,y)$ is a function of two grid coordinates $x$ and $y$ and is a differentiable function then the direction of flow is given by the negative vector derivative $-grad(z)$ You can trace a curve over the surface starting from any point (a spring) by following the direction until you either flow of the edge of the grid or arrive at a local minimum. If you arrive at a minimum the water is going to form a lake there and fill up until it finds a point to exit. Such a point will always be a saddle point, i.e. a point where $grad(z)$ is zero but it is neither a minimum or a maximum. This is the kind of point that forms a mountain pass and rivers from lakes always exit at such points.

You have to come up with some strategy for deciding where to put the sources of your streams. This might be random or you might pick special points such as saddle points. If these are sometimes exit points of lakes they could make could locations for springs too. In general from a saddle point there are two opposite directions in which the stream can flow which can be found using the second derivatives. You could also start streams from summits choosing the directions in which the terrain curves away steepest for the initial direction.

In the actual problem the surface is not smooth, it is a triangulated grid. From each point a stream will flow away in the direction of steepest decent. Within a given triangle this will be a straight line. Its direction is easy to work out. Find the normal to the triangle by taking the cross product of two edge vectors. Then project the normal onto the $(x,y)$ plane. You will have to deal with the cases where the land is flat as a special case.

When the water reaches an edge of a triangle it will either flow onto the adjacent triangle and change direction or it will flow along the edge. You have to check the gradient of each possibility and take the steepest. It may also arrive at a point from where it can flow away on a triangle or an edge. Again you need to calculate each possibility and take the steepest.

To find starting points you can either take random points at high altitudes or look for saddle points and summits. To do this look at each edge joining on a vertex and determine whether they slope up or down from the point. Trace round the point and count how many times the slope changes sign. If it changes twice you are on a slope. If it never changes you are on a summit or minimum point. if it changes more than four times you are on a saddle point. More than four times is possible since the surface is not smooth. The summits and saddle points are good places to put springs with water flowing away in the steepest direction(s). Trace the path of the streams from there until you reach a minimum.

On a terrain that is like a realistic landscape you are likely to find that streams converge. Mostly they will converge along edges of triangles but they could also converge at a vertex if there is more than one direction of local steepest accent from the point. One strategy would be to start a spring at every vertex or triangle centre and count how many (weighted by the area of the triangle?) converge into each stream to find the biggest rivers.

Hope this is enough to help you work out the details and write the necessary software.

-
Lot of words circling the problem like a cat walks around some hot milk :=) Ever heard of contour lines (wiki) ? The "stream path lines" (Is there no better English word as German Falllinie?) is a line which is perpendicular to the contour lines in every point.(And they have the maximum slope!) Like electric field lines are perpendicular to equipotential lines. ("Potential" again!) –  Georg Sep 22 '11 at 17:59
Of course, but the terrain is triangulated so the contour lines have angular discontinuities that the stream path lines will cross. There is no perpendicular at those points. To resolve this you have to follow a procedure equivalent to the one I have described where the stream may follow such a discontinuity along the edges of the triangles in some places. I don't think that finding the contour lines really helps at all, except when a lake forms. –  Philip Gibbs Sep 24 '11 at 6:42