TopoToolbox / libtopotoolbox

A C library for the analysis of digital elevation models.
https://topotoolbox.github.io/libtopotoolbox/
GNU General Public License v3.0
0 stars 3 forks source link

Implement excess topography #46

Closed wkearn closed 3 weeks ago

wkearn commented 3 weeks ago

This pull request adds several functions to compute excess topography using a new method based on solving a constrained eikonal equation. This approach is not identical to excesstopography as currently implemented in the MATLAB version of TopoToolbox, which uses morphological filtering, but the eikonal solver is significantly faster.

There are three new API functions, each of which is namespaced with excesstopography_.

The fast sweeping method is faster with constant or slowly varying threshold slopes, and it does not require memory be allocated for a priority queue. The fast marching method is faster with quickly varying threshold slopes and requires a priority queue, but it is also guaranteed to complete with a single scan of the DEM.

The names might be slightly misleading: each function writes the constrained topography to its output parameter. If you want to compute the excess topography, you need to subtract that from the original DEM. Packages built on libtopotoolbox should be able to handle this efficiently, and can provide options for returning either the true excess topography or the constrained topography.

In addition, this PR adds an implementation of a heap-based priority queue that is needed by the fast marching method. It has ptrdiff_t keys and float priorities, and it is suitable for other purposes (namely #10).

The tests add a new executable to prevent the random_dem from getting too crowded, but they likewise use property-based tests to ensure that the slopes of the constrained topography are indeed less than the thresholds. excesstopography_fmm3d is run during the tests, but its results are not checked.

wkearn commented 3 weeks ago

Some CI-revealed issues here: