Title: An Experimental Evaluation of Various Approximate Watershed Algorithms

Speaker: Stijn Koopal, Technische Universiteit Eindhoven

Location: Nygaard 395, Building no. 5335

Abstract:

Modeling how water flows on landscapes, and therefore predicting floods and other environmental phenomena, has always been of major importance in hydrology and ecological sciences. Today, flow modeling on landscapes is performed in a computer-based environment using digital representations of real-world terrains. One of the most popular digital terrain representations are the so-called Triangulated Irregular Networks (TINs) which are piecewise linear surfaces that consist of 3D triangles.

A natural way to model water flow on a surface is to consider that, at any point on the surface, water follows the direction of steepest descent (DSD). However, even this simple flow model has been proven computationally infeasible when applied on TINs.

On the other hand, there exist many methods that compute flow paths on TINs approximately, that is without following strictly the DSD on the surface.

Such methods do not suffer from the computational problems of the exact flow model. However, flow structures that are produced using these methods may provide a poor approximation of the original structures that are implied by the exact flow model.

In this talk we present various approximate algorithms for computing drainage basins on TINs. We evaluate these algorithms both in terms of efficiency and approximation quality in comparison to the exact flow model.

We consider two different categories of methods; the first category involves methods that use exact arithmetic, and can introduce new vertices on the TIN with coordinates of possibly large bit-size. The methods of the second category are restricted to performing comparisons between floating point numbers. Among other results, we show that certain methods provide a good quality of approximation for terrains of certain morphology; some methods do well on relatively mountainous terrains whereas others do better on nearly flat terrains.

Host: Constantinos Tsirogiannis