Efficient Digital-Elevation-Model-Based Flow Direction Estimation Using Priority Queue with Flow Distance and Zigzag Route Considerations

Extracting drainage networks from a digital elevation model (DEM) with massive cells is time-consuming due to depressions and flats, where flow paths to the outlet cannot be extracted using downslope gradients. Algorithms based on a priority queue are an efficient solution for this task. However, the existing algorithms depend on the insertion order in a priority queue to determine flow directions for cells with equal elevation. This dependency increases the sorting time in the priority queue. Our study developed an improved algorithm (referred to as DZFlood), adopting a dual priority queue. The queue considers elevation and flow distance to outlets. Cells sharing equal elevation and flow distance can be randomly arranged to reduce time costs. A secondary correction is applied to select a more tortuous yet shortest flow path for each flat cell. The visual assessment results show that the flow paths derived by DZFlood are more accurate than five existing algorithms and consistent with the real rivers and lakes. The computation efficiency of DZFlood is 19.2% faster, on average, than that of another priority-queue-based algorithm named LCP. The relative difference between their runtimes is greater when a larger DEM is used. Over a DEM with 3 × 108 cells, DZFlood performs at least 28% faster than LCP.