Priority flood algorithm for height map

priority-flood.md

Priority Flood algorithm for a Digital elevation model (DEM)

A generalization of the hierarchical-queue and priority-queue methods described by previous authors. The algorithm is described using pictures in Fig. 1. Upon entry, (1) DEM contains the elevations of every cell or the value NoData for cells not part of the DEM. (2) The value NoData is less than the elevation of any cell. At exit, (1) DEM contains the elevations of every cell or the value NoData for cells not part of the DEM. (2) The elevations of DEM are such that there are no digital dams and no undrainable depressions in the landscape, though there may be flats.

Require: DEM

1. Let Open be a priority queue
2. Let Closed have the same dimensions as DEM
3. Let Closed be initialized to false
4. for all c on the edges of DEM do
   1. Push c onto Open with priority DEM (c)
   2. Closed(c) ← true
5. while Open is not empty do
   1. c ← pop(Open)
   2. for all neighbors n of c do
   3. if Closed(n) then repeat loop
   4. DEM(n) ← max(DEM(n), DEM(c))
   5. Closed(n) ← true
   6. Push n onto Open with priority DEM (n)

---

Source: https://arxiv.org/pdf/1511.04463v1.pdf