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

针对数字高程模型(digital elevation model,DEM)大区域数据量大,而常用的洪水淹没算法(如种子蔓延法)不适用于对DEM的分块计算和分次存储,且用时和耗内存大,设计了一种使用图遍历来有效计算洪水淹没范围的算法,对DEM数据分条带读入计算机内存,然后采用块码压缩方式将潜在淹没区域压缩成块存入磁盘,使用广度优先搜索的图遍历方法读取数据。该算法设计逻辑清晰、实用性强且运算效率高,适用于大范围地形复杂的淹没区域。选取北京市、四川省的DEM数据进行实验,实验结果验证了该算法满足计算快速、占用内存少的要求。

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

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.