Find all "depressions" in a matrix that are connected to a seed point using python

20 views Asked by At

I'm working with some images/rasters and I want to find the lowest points that are connected to a seed point using python. I will explain it with an example:

Consider the seed point (2, 5) and the matrix A =

[[ 5.   5.   4.   8.   9.  11.   9.   8.   7.   8.   7. ]
 [ 1.8  5.   3.   4.   4.  11.   5.   9.   9.   7.   5. ]
 [ 1.   5.   3.   4.   3.  10.   3.   6.   4.   8.   9. ]
 [ 1.   2.   2.   3.   5.  11.   5.   2.   5.   6.   5. ]
 [ 1.   5.   1.   5.   4.  12.   5.   8.   1.   5.   6. ]
 [ 1.   4.   1.8  6.   6.  13.   9.   6.   2.   8.   9. ]
 [ 3.   4.   4.   2.   2.   7.   7.   2.1  5.   6.   5. ]
 [ 9.   9.   9.   9.   3.   1.1  2.2  5.   1.   8.   6. ]
 [ 9.   9.   9.   9.   3.   1.5  5.   7.   6.   4.   3. ]
 [ 9.   9.   9.   9.   3.   3.   3.   3.   2.   8.   9. ]]

Then, the depressions that are connected to the seed point are at positions (4,2) and (4,8). This depressions are connected to the seed point by the paths [(2, 5), (2,4), (3,3), (4, 2)] and [(2,5), (2,6), (3,7), (4,8)], respectively. It is like finding the "drainage" in a basin starting from a seed point.

I developed an algorithm that works like this:

  1. starting from the seed point look for the neighbors ("valid neighbors") that are inside the matrix (usually 8 neighbors)
  2. find the smallest of the neighbors and their positions
  3. from the previous positions repeat the procedure
  4. stop if the central cell is smaller than the neighbors (these cells will correspond to my "end points" or "depression" or "local minimum")

My algorithm works, but, since I'm working with lists and loops in python, I wonder if there's is any library that can do the same but faster. I used the search bar but couldn't find something like this.

0

There are 0 answers