A New Algorithm to Automatically Extract the Drainage Networks and Catchments Based on Triangulation Irregular Network Digital Elevation Model

doi:10.1007/s12204-014-1511-9

Abstract

Abstract: A new algorithm to automatically extract drainage networks and catchments based on triangulation irregular networks (TINs) digital elevation model (DEM) was developed. The flow direction in this approach is determined by computing the spatial gradient of triangle and triangle edges. Outflow edge was defined by comparing the contribution area that is separated by the steepest descent of the triangle. Local channels were then tracked to build drainage networks. Both triangle edges and facets were considered to construct flow path. The algorithm has been tested in the site for Hawaiian Island of Kaho’olawe, and the results were compared with those calculated by ARCGIS as well as terrain map. The reported algorithm has been proved to be a reliable approach with high efficiency to generate well-connected and coherent drainage networks.

摘要： A new algorithm to automatically extract drainage networks and catchments based on triangulation irregular networks (TINs) digital elevation model (DEM) was developed. The flow direction in this approach is determined by computing the spatial gradient of triangle and triangle edges. Outflow edge was defined by comparing the contribution area that is separated by the steepest descent of the triangle. Local channels were then tracked to build drainage networks. Both triangle edges and facets were considered to construct flow path. The algorithm has been tested in the site for Hawaiian Island of Kaho’olawe, and the results were compared with those calculated by ARCGIS as well as terrain map. The reported algorithm has been proved to be a reliable approach with high efficiency to generate well-connected and coherent drainage networks.

CLC Number:

TV 12

QU Guo-dong1,2 (屈国栋), SU Dan-yang1* (苏丹阳), LOU Zhang-hua1 (楼章华). A New Algorithm to Automatically Extract the Drainage Networks and Catchments Based on Triangulation Irregular Network Digital Elevation Model[J]. Journal of shanghai Jiaotong University (Science), 2014, 19(3): 367-377.

References

[1] Liu Jia-hong, Wang Guang-qian, Wang Kai. Review on advancement of study on digital river basin in China[J]. Journal of Hydraulic Engineering, 2006, 37(2):240-246 (in Chinese).
[2] Ivanov V Y, Vivoni E R, Bras R L, et al. Catchment hydrologic response with a fully distributed triangulated irregular network model [J]. Water Resources Research, 2004, 40(W11102): 1-23.
[3] Doll P, Lehner B. Validation of a new global 30-min drainage direction map [J]. Journal of Hydrology,2002, 258(1-4): 214-231.
[4] Colombo R, Vogt J V, Soille P, et al. Deriving river networks and catchments at the European scale from medium resolution digital elevation data [J].Catena, 2006, 70(3): 296-305.
[5] Qian Jian-hong, Ehrich R W, Campbell J B.DNESYS—An expert system for automatic extraction of drainage networks from digital elevation data[J]. IEEE Transactions on Geoscience and Remote Sensing, 1990, 28(1): 29-45.
[6] Vogt J V, Colombo R, Bertolo F. Deriving drainage networks and catchment boundaries: A new methodology combining digital elevation data and environmental characteristics [J]. Geomorphology, 2003,53(3-4): 281-298.
[7] Zhang Yu, Liu Yong-xue, Chen Zhen-jie. Multi-flow direction algorithms for extraction drainage network based on digital elevation model [J]. Geospatial Information Science, 2007, 6753(2B): 1-9.
[8] Jenson S K, Domingue J O. Extracting topographic structure from digital elevation data for geographic information system analysis [J]. Photogrammetric Engineering and Remote Sensing, 1988, 54(11): 1593-1600.
[9] Martz L W, Garbrecht J. Automated recognition of valley lines and drainage networks from grid digital elevation models: A review and a new method—Comment [J]. Journal of Hydrology, 1995, 167(1-4):393-396.
[10] Tarboton D G. A new method for the determination of flow directions and upslope areas in grid digital elevation models [J]. Water Resources Research, 1997,33(2): 309-319.
[11] Chorowicz J, Ichoku C, Riazanoff S, et al.Acombined algorithm for automated drainage network extraction [J]. Water Resources Research, 1992, 28(5):1293-1302.
[12] Zehana M, Desachy J, Zahzah E H. A multilevel drainage network computation and representation with vectors and topographical attributes[C]//Geoscience and Remote Sensing Symposium.Houston, USA: IEEE, 1992: 31-33.
[13] Zhang W, Fu C, Yan X. Automatic watershed delineation for a complicated terrain in the Heihe River Basin, Northwestern China [C]//Geoscience and Remote Sensing Symposium. Seoul, Korea: IEEE, 2005:2347-2350.
[14] Wu Fan, Su Wei-min, Yang Ying-wei, et al. Extracting terrain features from contour maps based on United-Delaunay-Triangulation model [J]. Journal of China University of Mining & Technology, 2007, 36(2):172-176 (in Chinese).
[15] Ai Ting-hua, Zhu Guo-rui, Zhang Gen-shou. Extraction of landform features and organization of valley tree structure based on delaunay triangulation model[J]. Journal of Remote Sensing, 2003, 7(4): 292-299(in Chinese).
[16] Konederink J J, van Doom A J. Local features of smooth shapes: Ridges and courses [C]//Geometric Methods in Computer Vision II. San Diego, CA, USA:SPIE, 1993.
[17] VanderKwaak J E, Loague K. Hydrologic-response simulations for the R-5 catchment with a comprehensive physics-based model [J]. Water Resources Research,2001, 37(4): 999-1013.
[18] Ebei B A, Loague K, Montgomery D R, et al. Physics-based continuous simulation of long-term near-surface hydrologic response for the Coos Bay experimental catchment [J]. Water Resources Research,2008, 44(W07417): 1-23.
[19] VanderKwaak J E. Numerical simulation of flow and chemical transport in integrated surface-subsurface hydrologic systems [D]. Waterloo, Ontario, Canada:Earth Science, University of Waterloo, 1999.
[20] Tucker G E, Lancaster S T, Gasparini N M, et al. An object-oriented framework for distributed hydrologic and geomorphic modeling using triangulated irregular networks [J]. Computer & Geosciences, 2001,27: 959-973.
[21] Jones N L, Wright S G.Watershed delineation with triangle-based terrain models [J]. Journal of Hydraulic Engineering, 1990, 116(10): 1232-1251.
[22] Yu Si-di, van Kreveld M, Snoeyink J. Drainage queries in TINs: From local to global and back again [C]//Advances in GIS Research II: Proceedings of the 7th International Symposium on Spatial Data Handling.Delft Holland: Delft University of Technology,1996.
[23] Liu Xue-jun, Wang Yong-jun, Ren Zheng, et al. Algorithm for extracting drainage network based on triangulated irregular network [J]. Journal of Hydraulic Engineering, 2008, 39(1): 27-34 (in Chinese).
[24] Mcallister M, Snoeyink J. Extracting consistent watersheds from digital river and elevation data [C]//ASPRS/ACSM Annual Conference. Washington D C: Washington State Convention Center, 1999.
[25] Braun J, Sambridge M. Modelling landscape evolution on geological time scales: A new method based on irregular spatial discretization [J]. Basin Research,1997, 9(1): 27-52.
[26] Coppola E, Tomassetti B, Mariotti L, et al. Cellular automata algorithms for drainage network extraction and rainfall data assimilation [J]. Hydrological Sciences,2007, 52(3): 579-592.
[27] Planchon O, Darboux F. A fast, simple and versatile algorithm to fill the depressions of digital elevation models [J]. Catena, 2002, 46(2-3): 159-176.
[28] Grimaldi S, Nardi F, Benedetto F D. A physically-based method for removing pits in digital elevation models [J]. Advances in Water Resources,2007, 30: 2151-2158.
[29] Temme A J A M, Schoorl J M, Veldkamp A. Algorithm for dealing with depressions in dynamic landscape evolution models [J]. Computers & Geosciences,2006, 32(4): 452-461.
[30] Zhu Qing, Tian Yi-xiang, Zhao Jie. An efficient depression processing algorithm for hydrologic analysis [J]. Computers & Geosciences, 2006, 32(5): 615-623.
[31] Chou Tian-yin, Lin Wen-tzu, Lin Chao-yuan. Application of the PROMETHEE technique to determine depression outlet location and flow direction in DEM[J]. Journal of Hydrology, 2004, 287(1-4): 49-61.
[32] Kenny F, Matthews B, Todd K. Routing overland flow through sinks and flats in interpolated raster terrain surfaces [J]. Computers & Geosciences, 2008,34(11): 1417-1430.
[33] Soille P, Vogt J, Colombo R. Carving and adaptive drainage enforcement of grid digital elevation models [J]. Water Resources Research, 2003, 39(12):1-13.
[34] Soille P. Optimal removal of spurious pits in grid digital elevation models [J]. Water Resources Research,2004, 40(W12509): 1-9.
[35] Garbrecht J, Martz L W. The assignment of drainage direction over flat surfaces in raster digital elevation models [J]. Journal of Hydrology, 1997, 193(1-4): 204-213.
[36] Soille P, Gratin C. An efficient algorithm for drainage networks extraction on DEMs [J]. Journal of Visual Communication Image Representation, 1994,5(2): 181-189.
[37] Nardi F, Grimaldi S, Santini M, et al. Hydrogeomorphic properties of simulated drainage patterns using digital elevation models: The flat area issue [J].Hydrological Sciences, 2008, 53(6): 1176-1193.
[38] Franke R, Nielson G. Smooth interpolation of large sets of scattered data [J]. International Journal of Numerical Method Engineering, 1980, 15: 1691-1704.
[39] Shepard D. A two dimensional interpolation function for regularly spaced data [C]//Proceedings of the 23rd National Conference of the Association for Computing Machinery. Princeton, NJ: ACM, 1968.
[40] Agrawal R, Ahmad N, Anjum J P, et al. Comparative evaluation of various algorithms for drainage extraction using Cartosat-1 stereo data [C]//Agriculture and Hydrology Applications of Remote Sensing. Goa,India: SPIE, 2006.
[41] Mccoy R M. Automatic measurement of drainage networks [J]. IEEE Transactions on Geoscience Electronics,1970, 8(3): 178-182.
[42] Mayorga E, Logsdon M G, Balleater M V R, et al. Estimating cell-to-cell land surface drainage paths from digital channel networks, with an application to the Amazon basin [J]. Journal of Hydrology, 2005,315(1-4): 167-182.
[43] Graham S T, Famiglietti J S, Maidment D R. Five-minute, 1/2 and 1 degree data sets of continental watersheds and river networks for use in regional and global hydrologic and climate system modelling studies[J]. Water Resources Research, 1999, 35(2): 583-587.