Improved branch identification

This version includes improvements in branch identification algorithm used by second and third stage. The n_dir array technique is completely replaced by the more versatile mdrid_n_xy one (array of array-coordinates) in all the three stages.

It is tested on the complete SRTM N39E021, just like 2021-04. See GitHub action 3943311051. The performance is improved mostly because of the optimizations in arrange_lines, but also by the slow assert-s made optional.

Summary of the major changes:

• New accumulate_by_mgrid function, that allows dropping of n_dir technique and neighbor point limitations
• Optimization in arrange_lines to use sorted pend_lines array
• Final geometry generation improvements, like optional geometry layers, line smoothing and OSM tags

Work in progress:

• Support for full cylinder/sphere wrapped around maps (allowed after the transition to mdrid_n_xy)
• More optimizations by accumulating the coverage area of each point in parallel
• Experiments with flattened mgrid_n_xy array (converted to array of indices)

Branch identification based on the area of coverage

This version includes fully rewritten second and third processing stage. Both stages use same technique to identify major vs. minor branches. There is no changes in the first stage.

It is tested on the complete SRTM N39E021, just like 2021-01. See GitHub action 2428150017. The performance is significantly degraded due to unfinished optimizations and quite more detailed result.

Branch identification technique by area of coverage:

1. The area of coverage of all the pixels is pre-calculated, by taking into account the terrain slope
2. A branch is created at each graph-leaf pixel, where no other pixels point to
3. Each branch continues forward by accumulating the area of the pixel from the tree-graph
4. When graph-node is reached, where multiple branches are connected, the one with largest area of coverage is selected as the major one. It continues further alone, by using the accumulated area of the others
5. The major branch that reaches the graph-seed is referred as trunk (just one trunk per seed, even if it is also a graph-node)
6. The branches that do not include a graph-node are referred as leaf-branches, or leaf-trunks when they end at seed

Summary of the major changes:

• The second and third stages use a new common function arrange_lines, to distinguish major from minor branches. It uses the area of coverage, instead of the total length
• The trunk branches are the only needed by the second stage of processing, where they are flipped to generate the largest ones, similar to the trick from 2020-11
• The third stage, repeats the same process, but keeps all the non-leaf branches. Smallest ones are discarded at the end
• An area verification function calc_branch_area is called during the geometry generation to double-check the previously calculated branch areas (this does some extra slowdown)
• Some changes in CI process including update of GDAL version and change of the SRTM download link

Work in progress:

• Additional parallelization in arrange_lines
• The area of coverage can be used as map zoom-level filter
• The ridge volume is considered to replace the area of coverage. It could improve the filtering-out of the ridges in flat areas

Performance improvements by parallelization

This version includes serious performance optimizations by running parallel numpy operations. This allows the SRTM3 DEM files (1201x1201) to be processed within the GitHub actions time-limits.

It is tested on the complete SRTM N39E021, unlike 2020-11 which was tested on a cropped SE region. See GitHub action 516151978.

Summary of the major changes:

• The trace_ridges() (first stage) is made as simple as possible, by separating the distance calculations
• The second stage consists of three sub-stages, where the distances calculation are performed twice, but is highly parallelized:
  • Calculate distances to identify the longest lines
  • Flip the longest lines in all valid elevation islands, including the regions created by the fake ridge removal algorithm
  • Re-calculate the distances to reflect the flipped lines and extract the result_lines (leaf pixels)
• The third stage processing is highly parallelized by running reduced_distance() on multiple lines in parallel
• The result includes more ridge lines, as the shortest ridge limit is reduced to 5% of the longest one

Work in progress:

• Parallelization processing optimizations: these techniques causes slowdown when the DEM is more than 9MP. This is mostly because of a copying of large number of dummy-data
• Optimization by processing the "node" pixels only
• The generates ridge lines, esp. when their number grows, need to be grouped in some "rank" hierarchy
• The ridges in flat areas need improvement, esp. on water surfaces
• It is nice to have some identification of a "closed" ridges, like in volcano craters

Flip longest line processing stage and improvements

This version includes a new processing stage after the trace_ridges() one, to flip the longest ridge line in each valid-elevation island. This causes, this line to become extension of the other lines, which in fact creates the longest possible ridge line. The distances along all the lines is adjusted to reflect this.

Note that, it is not necessary the initial "seed" point to be part of this "longest possible" line. This trick also makes the algorithm almost invariant from the "seed" point selection.

It is tested on SRTM N39E021, just like 2020-10. See GitHub action 384135885.

Summary of the major changes:

• Flip the longest ridge line processing stage
• Better handling of the boundary pixels, now the fake ridges around the boundaries are almost gone
• Minor parallelization changes to prepare for wide parallelization use in all steps
• GitHub workflow improvements, including merge source DEMs option and migration to GDAL 3.2
• Alternative distance calculation methods, slightly faster, but mostly to avoid pyproj
• Development option to keep/resume processing at the 2 points between stages

Work in progress:

• Very serious parallelization of all stages, like line length calculation
• Minimal processing in the fist stage
• Different technique for the second stage, including generation of the data skipped by the first one
• Quick identification of non-ridge lines, could allow early trimming
• Rank the ridges to allow grouping
• More detailed topology with shorter longer lines, that requires trim improvement

Skeleton algorithm to create terrain ridge structure

First version of the algorithm to create ridges, which generates quite satisfactory results.

It is tested on SRTM N39E021, see GitHub action 323871576. This is part of the Thessaly region in Greece, which is highly folded. No major river beds are crossed by the generated ridges, except at the DEM boundaries.

Known issues:

• Very slow (5-6h to process 1200x1200 DEM image), needs lots of improvements and numpy parallelization
• The final polyline generation needs rework, to avoid the "seed" point dependency
• Improper behavior at the DEM image edges, must consider to just stop propagation
• The polylines ending at the DEM image edges are treated like others, and often dropped because of short length