Automatic delineation of drainage basins from contour elevation data using skeleton construction techniques

A new method for automatic delineation of drainage basins from contour elevation data is presented. As a preprocessing step, contour line vertices are used to construct Delaunay and Voronoi diagrams along with other useful structures known in computational geometry as the crust and the skeleton or medial axis transform. Using the skeleton of contour lines, a recursive algorithm is then developed to solve critical topographic structures such as ridges, saddles, and peaks in a fully-automated and accurate manner. Numerical experiments based on high- accuracy contour elevation data of real terrains (generated from LiDAR surveys) show that the proposed method is able to process automatically any topographic structure and to produce results that are comparable to those that can be interpreted visually from contour lines. The gain in accuracy over state-of-the-art solutions is generally found to be significant and to increase as the contour interval increases. Finally, it is shown how the proposed method can be easily applied to construct accurate flow nets in a fully-automated manner. Skeleton construction techniques allow the morphological information implicitly present in contour elevation data to be explicitly revealed and appropriately processed by a computer program, and therefore appear useful means for improving the accuracy with which physiographic features of drainage basins are determined. The proposed method can be used to advance the construction of flow nets and contour-based digital elevation models (as outlined in this study) and to test the reliability of algorithms for the analysis of more efficient and straightforward, gridded or triangulated, elevation data (as shown in a companion study).