在NumPy 2D数组中查找所有下坡点的索引。

Question

下面的2D numpy数组代表一个地形高度。从这个矩阵中的任意单元格开始，我希望找到那些可以通过不断向斜坡下方（高度更低）或平地移动到达的单元格。我们可以将其想象为模拟如果不允许球在另一侧的任何斜坡上回滚（无论多小），它可以可能滚动到的区域。请注意热图左侧的区域-它低于目标正方形，但仍需要爬上山才能到达那里。

import numpy as np
arr_surface_2D = np.array([
    [64, 64, 65, 66, 66, 67, 68, 68, 69, 70, 70, 70, 69],
    [65, 66, 66, 67, 68, 68, 69, 70, 70, 71, 72, 71, 70],
    [64, 65, 66, 66, 67, 68, 68, 69, 70, 70, 71, 70, 70],
    [66, 66, 67, 68, 68, 69, 70, 70, 71, 71, 72, 72, 71],
    [65, 66, 66, 67, 68, 68, 69, 69, 70, 71, 71, 71, 70],
    [63, 64, 65, 65, 66, 66, 67, 68, 68, 69, 70, 69, 68],
    [63, 63, 64, 64, 65, 66, 66, 67, 68, 68, 69, 68, 68],
    [70, 66, 65, 64, 65, 66, 66, 67, 67, 68, 69, 68, 68],
    [68, 65, 63, 62, 63, 63, 64, 65, 65, 66, 67, 66, 65],
    [57, 58, 58, 59, 59, 60, 61, 61, 62, 63, 63, 63, 62],
    [56, 56, 57, 58, 58, 59, 60, 60, 61, 62, 62, 62, 61],
    [55, 56, 57, 57, 58, 59, 59, 60, 61, 61, 62, 61, 61],
    [55, 56, 57, 57, 58, 59, 59, 60, 60, 61, 62, 61, 61]
]
)

如果数组是一维的，我可以想出一个不太优雅的解决方案，但是我认为可能有更优雅的解决方案可以扩展到二维？

idx_target = 7
arr_surface_1D = np.array([
    70, 66, 65, 64, 65, 66, 66, 67, # <-"target"
    67, 68, 69, 68, 68])

# Slice array to the left side of idx_target, reverse direction to allow diff in next step
arr_left = arr_surface_1D[:idx_target][::-1]
# Determine number of spaces to the left where the values first start increasing
steps_left = np.argmax((np.diff(arr_left) > 0))

# Slice array to the right side of idx_target
arr_right = arr_surface_1D[idx_target + 1:]
# Determine number of spaces to the right where the values first start increasing
steps_right = np.argmax((np.diff(arr_right) > 0))

arr_downhill = arr_surface_1D[idx_target-(steps_left+1):idx_target+(steps_right)]
# Result is array array([64, 65, 66, 66])

- DaveB

---

请在 [mre] 中包含预期结果。 - Michael Szczesny

Answer 1

这是一个“寻路问题”。可以使用BFS（在探索邻居时，要考虑源/目标单元格的高度）来解决。像python-pathfinding这样的软件包可能会帮助您完成任务。如果您打算自己实现此功能，请注意可以使用Numba（或Cython）来加速，因为在纯Python中进行直接索引太慢了。相对于您的约束条件来说，这肯定比使用现有软件包更快。

请注意，如果您计划在所有单元格上执行此操作，那么我认为基于流域的更快的算法可以在（准）线性时间（两次遍历）内执行。在这种情况下，使用BFS将不高效，因为大多数单元格需要重新计算。

- Jérôme Richard

---

嗨，Jerome，感谢你介绍了一些技术，这非常有帮助。排水分流算法听起来正是我需要的，但我找不到任何实现。上面Michael的答案可以工作，但由于它是纯Python，所以无法很好地扩展。你有没有碰巧遇到过任何更快的实现呢？ - DaveB

经过调查，我发现了一个有希望的实现方式 https://scikit-image.org/docs/dev/api/skimage.segmentation.html#flood - 如果它可以达到上面Michael的实现相同的结果，我将进行调查并在这里发布答案。 - DaveB

Answer 2

一种修改过的泛洪填充算法可以找到所需的索引。以下是一个纯Python实现（除了用numpy表示二维数组）。

def downhill(arr, start):

    q = [start]
    fill = {start}
    while q:
        e = q.pop()
        x, y = e
        
        res = []
        if x > 0: res.append((x-1, y))
        if x < arr.shape[0]-1: res.append((x+1, y))
        if y > 0: res.append((x, y-1))
        if y < arr.shape[1]-1: res.append((x, y+1))

        for p in res:
            if p not in fill and arr[p] <= arr[e]:
                q.append(p)
                fill.add(p)

    return np.array(tuple(fill))

x, y = downhill(arr_surface_2D, (4,7)).T
res = np.zeros_like(arr_surface_2D)
res[x,y] = 1
res

将索引以数组中的0显示为1s的输出

array([[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
       [1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
       [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0],
       [1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0],
       [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0],
       [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0],
       [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0],
       [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
       [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
       [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
       [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]])

- Michael Szczesny