Watershed algorithm: Difference between revisions

From Tygron Support wiki
Jump to navigation Jump to search
Line 31: Line 31:
====References====
====References====
<references/>
<references/>
===See also===

Revision as of 13:41, 20 May 2020

The Watershed algorithm has two variants, one based on absolute height values of the DTM and one based on a Water Overlay's Surface Direction result type.

Data initialization

The basic watershed algorithm has been adjusted to allow users to mark waterways and water surfaces as uniquely identified minimas present at the start of the algorithm.

Additionally, culverts can be considered connections between waterways that can propagate these minima areas to waterways that are not initially marked.

Optionally, the direction of the flow through the culvert can be considered to limit the expansion of minima areas to other waterways. In such case only the waterways that flow towards a waterway marked as a minima are also marked with the same unique minima id.

Watershed Algoritm

  1. Setup label (applied once): Convert Input data to cell references, in 8 directions. Cells without a direction angle become a plateau with a unique id.
  2. Label plateaus (loop until stable): Calls without a reference to other are re-evaluated. Such a cell will reference the first neighboring cell that flow away from it.
  3. Fix self directions (only once): Neighboring cells that reference each other, are both set back to being a plateau. They can now be seen as a minima.
  4. Store directions as a result type.
  5. Set Minima IDs (only once): For cells that are marked as a plateau, mark them now as minima with a unique id.
  6. Propagate minima IDs (loop until stable): Union minima cells ids, by giving them both the lowest ids of the two.
  7. Store minima as a result type.
  8. Flood (loop until stable): Cells referencing a cell with a (minima) label are updated to that same label id.
  9. Fill (loop until stable): Assign a label to an unlabeled cell based on first found neighbor with a label. Optionally limit this step to cells that are not roads.

Notes

  • The watershed algorithm implementation is an adapted version of the algorithm proposed by Vitor et. al. [1].
  • A plateau is a cell without a reference to other cells and without a unique label id. It can become either a:
    • border cell, which will reference cells directing away from it;
    • minima cell, which will receive a unique id.
  • Direction in the Fill step does not matter at this stage, because it would have been labeled otherwise. Cells can remained unlabeled when restrictions are put on the minima labeled.

Tips

  • When using a Water Overlay's Flow direction result as an input for the Watershed Overlay, it is important to consider what rain settings are used. Generally, you want select a rainfall big enough for local minima, due to small depressions in the terrain, to disappear. On the other side, the rainfall should not be too big for the marked ditches it should end up in.

References

  1. Vitor, Giovani & Körbes, André & Lotufo, Roberto & Ferreira, Janito. (2010). Analysis of a Step-Based Watershed Algorithm Using CUDA. IJNCR. 1. 16-28. 10.4018/jncr.2010100102.


See also