如何定位2D数组中由1构成轮廓的闭合区域内的所有元素？

针对扫描线法无法处理带凹陷的闭合区域问题，推荐使用外部区域标记法，通过区分外部与内部的0元素，准确提取闭合区域（含轮廓1与内部0）的所有坐标，步骤如下：

核心思路 #

1. 标记外部0元素：从数组的边界（四周边缘的0点）出发，用广度优先搜索（BFS）或深度优先搜索（DFS）标记所有与边界连通的0（即外部区域）。
2. 筛选目标区域：遍历整个数组，收集所有未被标记的0（内部区域）和所有1（轮廓区域）的坐标，这些就是闭合区域内的全部元素。

代码实现（Python） #

import queue

def extract_closed_region(arr):
    rows = len(arr)
    cols = len(arr[0]) if rows else 0
    # 标记外部区域的访问状态
    is_external = [[False for _ in range(cols)] for _ in range(rows)]
    q = queue.Queue()

    # 将四周边界的0点加入队列，作为外部区域的起点
    for i in range(rows):
        for j in [0, cols-1]:
            if arr[i][j] == 0 and not is_external[i][j]:
                q.put((i, j))
                is_external[i][j] = True
    for j in range(cols):
        for i in [0, rows-1]:
            if arr[i][j] == 0 and not is_external[i][j]:
                q.put((i, j))
                is_external[i][j] = True

    # BFS遍历标记所有外部连通的0
    directions = [(-1,0), (1,0), (0,-1), (0,1)]
    while not q.empty():
        x, y = q.get()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols:
                if arr[nx][ny] == 0 and not is_external[nx][ny]:
                    is_external[nx][ny] = True
                    q.put((nx, ny))

    # 收集闭合区域内的所有坐标
    region_coords = []
    for i in range(rows):
        for j in range(cols):
            if arr[i][j] == 1 or (arr[i][j] == 0 and not is_external[i][j]):
                region_coords.append((i, j))
    return region_coords

# 示例输入数组
sample_array = [
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,1,1,1,1,0],
    [0,0,1,1,1,0,0,1,0],
    [0,0,1,0,0,1,1,1,0],
    [0,0,1,1,0,1,0,0,0],
    [0,0,0,1,0,1,1,0,0],
    [0,0,0,1,0,0,1,0,0],
    [0,0,0,1,1,1,1,0,0],
    [0,0,0,0,0,0,0,0,0]
]

# 输出结果
print(extract_closed_region(sample_array))

方法优势 #

• 不受区域凹陷、复杂轮廓影响，能准确识别所有闭合区域内的元素；
• 无需提前寻找内部种子点，仅通过边界遍历即可完成外部区域标记，鲁棒性更强；
• 可同时处理多个独立的闭合区域（若存在）。

内容的提问来源于stack exchange，提问作者Hoai Nam Nguyen