求可在numpy二维数组非零值岛屿外生成最优包围边界的算法

实现思路 #

• 核心逻辑通过四邻域邻接判定+形态学膨胀即可实现，天然满足近岛自动共用围墙的需求：
  1. 基础围墙判定规则：围墙为原本取值为0的空位，且和至少一个资源点（取值为1）四向相邻；如果两个资源岛之间仅隔1个空位，该空位会同时属于两个岛的邻接范围，不需要额外处理就可以作为共用围墙。
  2. 如果需要把间隔小于指定阈值的岛都合并到同一个围墙圈内，只需要先对资源点数组做对应次数的四向膨胀，再取膨胀后区域的外围邻接坐标即可，调整膨胀次数就能自定义“距离极近”的判定标准。
• 性能层面你的数组边长最大仅40，总元素数不超过1600，哪怕暴力遍历所有点的四邻域都完全够用，不需要复杂优化。

代码实现 #

方案1：纯NumPy实现（无额外依赖） #

import numpy as np

def get_barricade_positions(mat: np.ndarray) -> list[tuple[int, int]]:
    size = mat.shape[0]
    # 上下左右四个方向的偏移量
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    barricades = set()

    # 遍历所有资源点的四邻域
    for (x, y) in np.argwhere(mat == 1):
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            # 坐标在数组范围内，且原本是0的位置即为围墙位
            if 0 <= nx < size and 0 <= ny < size and mat[nx][ny] == 0:
                barricades.add((nx, ny))
    
    return list(barricades)

# 测试用你提供的初始代码
size = 15
test_mat = np.zeros((size, size))
test_mat[(4, 5, 5, 6), (5, 4, 6, 5)] = 1
test_mat[(9, 9, 9, 10, 10, 11, 11), (8, 9, 10, 8, 10, 8, 10)] = 1

# 获取围墙坐标
barrier_pos = get_barricade_positions(test_mat)
# 写入数组查看效果
for x, y in barrier_pos:
    test_mat[x][y] = 2

print(test_mat.astype(int))

方案2：支持近岛合并的进阶实现 #

如果需要把距离≤K的岛都包进同一个围墙，可通过形态学膨胀实现，调整参数即可自定义合并阈值：

import numpy as np
from scipy.ndimage import binary_dilation

def get_merged_barricades(mat: np.ndarray, merge_distance: int = 1) -> list[tuple[int, int]]:
    size = mat.shape[0]
    # 四连通的膨胀结构元
    structure = [[0,1,0], [1,1,1], [0,1,0]]
    # 对资源点做指定次数膨胀，距离小于阈值的岛会被合并为同一个连通块
    dilated = binary_dilation(mat == 1, structure=structure, iterations=merge_distance)
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    barricades = set()
    for (x, y) in np.argwhere(dilated):
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if 0 <= nx < size and 0 <= ny < size and mat[nx][ny] == 0 and not dilated[nx][ny]:
                barricades.add((nx, ny))
    return list(barricades)

内容的提问来源于stack exchange，提问作者user10929733