python - 在 numpy 2D 中查找下坡所有点的索引

Question

下面的二维 numpy 数组表示表面高度。从该矩阵中的任何给定单元格中，我希望找到可以通过连续移动平坦(相同高度)或下坡(较低高度)而到达的单元格。我们可以将此视为建模，如果不允许球在另一侧的任何斜坡上回滚(无论多小)，它可能会滚动。请注意热图左侧的区域 - 它低于目标方 block ，但仍需要长途跋涉才能到达那里。

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])

Answer 1

修改后的洪水填充算法可以找到所需的索引。这是一个纯(除了用 numpy 表示二维数组)python 实现。

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 数组中将索引可视化为 1 的输出

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]])