iOS中2D矩阵不规则连通区域转矩形及DFS栈溢出问题解决

问题根源 #

递归DFS在处理大型连通区域（比如513×513矩阵中的大面积区域）时，会耗尽Swift默认的调用栈空间，直接触发EXC_BAD_ACCESS错误——因为递归深度会远超系统允许的栈上限（通常仅几千层），而大型连通区的点数量可能达到十万级，完全超出调用栈的承载能力。

解决方案 #

把递归DFS替换为迭代式DFS（用堆内存中的手动栈存储待访问坐标），避免占用系统调用栈；同时计算连通区的最小外接矩形，用矩形覆盖原不规则区域。

1. 迭代式DFS查找连通区边界 #

以下代码会遍历矩阵，找到所有值为15的连通区域的最小外接矩形（minX/maxX为左右边界，minY/maxY为上下边界）：

func findBoundingRectForTargetValue(_ target: Int, in matrix: inout [[Int]]) -> (minX: Int, maxX: Int, minY: Int, maxY: Int)? {
    let rowCount = matrix.count
    guard rowCount > 0 else { return nil }
    let colCount = matrix[0].count
    var visited = Array(repeating: Array(repeating: false, count: colCount), count: rowCount)
    
    var minX = colCount, maxX = -1
    var minY = rowCount, maxY = -1
    var regionFound = false
    
    // 遍历矩阵定位第一个目标区域的起点
    for y in 0..<rowCount {
        for x in 0..<colCount {
            if matrix[y][x] == target && !visited[y][x] {
                regionFound = true
                // 手动栈存储待访问的坐标点
                var stack = [(x: Int, y: Int)]()
                stack.append((x, y))
                visited[y][x] = true
                
                while !stack.isEmpty {
                    let current = stack.popLast()!
                    let currX = current.x
                    let currY = current.y
                    
                    // 更新矩形边界
                    minX = min(minX, currX)
                    maxX = max(maxX, currX)
                    minY = min(minY, currY)
                    maxY = max(maxY, currY)
                    
                    // 检查上下左右四个相邻点
                    let directions = [(-1,0), (1,0), (0,-1), (0,1)]
                    for (dx, dy) in directions {
                        let newX = currX + dx
                        let newY = currY + dy
                        // 校验坐标合法性、未访问且为目标值
                        if newX >= 0 && newX < colCount && newY >= 0 && newY < rowCount 
                            && !visited[newY][newX] && matrix[newY][newX] == target {
                            visited[newY][newX] = true
                            stack.append((newX, newY))
                        }
                    }
                }
                // 若需处理多个连通区，可在此处收集矩形后继续遍历；此处先处理第一个区域
                break
            }
        }
        if regionFound { break }
    }
    
    return regionFound ? (minX, maxX, minY, maxY) : nil
}

2. 将连通区转换为矩形 #

找到边界后，直接填充矩形范围内的所有点为15：

func convertConnectedRegionToRectangle(_ target: Int, in matrix: inout [[Int]]) {
    guard let rect = findBoundingRectForTargetValue(target, in: &matrix) else {
        print("未找到值为\(target)的连通区域")
        return
    }
    
    // 填充矩形区域
    for y in rect.minY...rect.maxY {
        for x in rect.minX...rect.maxX {
            matrix[y][x] = target
        }
    }
}

3. 完整使用流程 #

结合你的JSON解析和绘图代码，流程如下：

// 加载矩阵（替换为你的JSON解析实现）
func loadMatrix(from filePath: String) -> [[Int]]? {
    guard let data = try? Data(contentsOf: URL(fileURLWithPath: filePath)),
          let matrix = try? JSONDecoder().decode([[Int]].self, from: data) else {
        return nil
    }
    return matrix
}

// 执行处理
guard var segmentationMatrix = loadMatrix(from: "your_matrix_file.json") else {
    fatalError("矩阵加载失败")
}

convertConnectedRegionToRectangle(15, in: &segmentationMatrix)

// 调用你的绘图函数展示结果
// drawMatrix(segmentationMatrix)

额外说明 #

• 若矩阵存在多个值为15的连通区域，修改findBoundingRectForTargetValue函数，将矩形结果存入数组，遍历数组逐一填充即可。
• 迭代式DFS使用堆内存中的数组作为栈，不受系统调用栈深度限制，完美解决大型矩阵的栈溢出问题。

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