Location: Bowdoin / Computer Science / Student Projects / Summer / 2005 / Richard Hoang

Computer Science

Richard Hoang '06

Richard HoangAs a Surdna Undergraduate Research Fellow, Richard spent the summer of 2005 at Bowdoin College working with Professor Laura Toma. His main research was to model flow on terrains represented as digital elevation models (DEMs). Why flow? Flow is one of the most basic processes in nature; flow is used to predict the river network, the watersheds and the areas susceptible to flooding, and to model many other processes on terrains, like erosion, sediment transport, flooding, and pollution. All geographic information systems (GIS) provide some type of support for flow modeling on DEMs.

Terrains are most commonly represented by sampling with a uniform grid. A grid DEM is a matrix of elevation values, where each point in the matrix represents the elevation of that point on the terrain. Grids are widely used, as terrain data comes readily in grid form from remote sensing technology. Also grids contain a simple structure, therefore yielding simple algorithms. However, grids are not the most space-efficient way to represent terrains. It is more efficient to have fewer points to represent flat areas, and more points to represent variations in elevations.

Flow
Flow

Another way to represent terrains is to sample the terrain non-uniformly, using more points in areas of high variation and fewer points in flat areas. By triangulating these points one obtains a so-called triangulated irregular network (TIN). TINs are more space efficient, but harder to handle algorithmically than grids. TINs are less used in GIS practice; most GIS packages offer very little support for TINs, compared to grids. In his honors project Jon Todd '05 researched refining terrains to convert from grid to TIN representation; Richard extended Jon's work to model flow on TINs.

The general idea in flow modeling is that water flows down, from higher to lower elevations. One of the choices in flow modeling is to assign flow direction to each point (point-based model), or to every triangle (triangle-based model). The overall goal is to develop a model that is as realistic as possible, and that can be computed efficiently. Richard developed a point-based model for flow modeling. Each point in the TIN looks at its adjacent edges and assigns flow to the vertex that has a lower elevation than it. The advantage is that the flow network is a subset of the TIN, and it can handle degenerate cases like ridges, valleys, and saddle edges. The hardest part for this research is to deal with flat areas. In Richard's work, he is trying to find realistic ways to route flow across the flat areas such that flow is globally routed to the outlet points of the flat area.

Currently, Richard's algorithm is able to read in a TIN DEM, and assigns flow direction to every edge in the TIN, including flat areas. Work to investigate how realistic the model is on real-life terrains is still underway.