基于图遍历的计算DEM数据洪水淹没范围的算法  

Algorithm for Calculating Flood Submergence Range from DEM Data Based on Graph Traversal

作　　者：王思雪 李英成[1,2] 刘沛 耿中元 孙新博[1,2] WANG Sixue;LI Yingcheng;LIU Pei;GENG Zhongyuan;SUN Xinbo(Key Laboratory for Aerial Remote Sensing Technology of National Administration of Surveying,Mapping and Geoinformation,Beijing 100039,China;China TopRS Technology Co.Ltd,Beijing 100039,China)

机构地区：[1]航空遥感技术国家测绘地理信息局重点实验室,北京100039 [2]中测新图(北京)遥感技术有限责任公司,北京100039

出　　处：《遥感信息》2020年第1期87-92,共6页Remote Sensing Information

基　　金：国家重点研发计划(2016YFC0803104、2016YFC0803109、2018YFF0215301)。

摘　　要：针对数字高程模型(digital elevation model,DEM)大区域数据量大,而常用的洪水淹没算法(如种子蔓延法)不适用于对DEM的分块计算和分次存储,且用时和耗内存大,设计了一种使用图遍历来有效计算洪水淹没范围的算法,对DEM数据分条带读入计算机内存,然后采用块码压缩方式将潜在淹没区域压缩成块存入磁盘,使用广度优先搜索的图遍历方法读取数据。该算法设计逻辑清晰、实用性强且运算效率高,适用于大范围地形复杂的淹没区域。选取北京市、四川省的DEM数据进行实验,实验结果验证了该算法满足计算快速、占用内存少的要求。To prevent the overflow of the computer memory during processing the large data volume of DEM in flooding analysis,flooding algorithms commonly used(such as the seed spread method)are not suitable for the calculation and storage of DEM blocks,and the time and memory consumption are large.This paper designs an algorithm that uses graph traversal to effectively calculate the flood submergence range.Dividing the DEM data into multiple stripes and reading it into computer memory,this algorithm uses the block codes method to compress the potential flooded area into blocks and stores them in disk,then it reads data by using a breadth-first search graph traversal method.The algorithm has clear logic design,strong practicability and high computational efficiency which is suitable for analysis of flooded areas with complex terrain.This paper selects DEM data from Beijing and Sichuan province for experiments.The experimental results verify that the algorithm meets the requirements of fast calculation and low memory consumption.

关 键 词：数字高程模型 水淹分析 图遍历 块码 广度优先搜索 

分 类 号：TP751.1[自动化与计算机技术—检测技术与自动化装置]