【c++】200*200 01灰度矩阵求所有的连通区域坐标集合

1.题目

题目要求：给定一个200x200的01灰度矩阵，求所有的连通区域坐标集合。 连通区域：相邻的1（上下左右，或者也可以包括对角线，这里通常使用4连通或8连通）。这里我们假设使用4连通（上下左右）即可，但题目没有明确，我们可以先按4连通实现，如果需要8连通可以稍作修改。

2.算法思想

算法思想：使用深度优先搜索(DFS)或广度优先搜索(BFS)来遍历每个连通区域。由于矩阵大小为200x200，DFS递归可能导致栈溢出，因此我们使用BFS或非递归DFS。这里我们使用BFS。

步骤：

1. 创建一个与输入矩阵同样大小的visited矩阵，用于标记每个位置是否已经被访问过。

2. 遍历矩阵中的每一个像素点： 如果该点为1且未被访问，则从该点开始进行BFS/DFS，将相邻的1都找出来，标记为已访问，并将这些坐标存入一个集合（即一个连通区域）。

3. 将每个连通区域的坐标集合保存起来。 注意：相邻指的是4连通（上、下、左、右）或者8连通。根据题目，这里我们先采用4连通。如果需要8连通，则搜索8个方向即可。 我们使用队列实现BFS。 具体步骤： 初始化一个队列，将起始点入队，并标记为已访问。 当队列不为空时，取出队首元素，将其坐标加入当前连通区域集合，然后检查其四个方向（上、下、左、右）的相邻点： 如果相邻点在矩阵范围内，值为1且未被访问，则将其入队并标记为已访问。

4. 重复以上过程直到队列为空，此时得到一个连通区域。

5. 继续遍历矩阵，直到所有点都被访问过。 由于矩阵是01的，我们只需要考虑值为1的点。 我们假设输入矩阵是一个二维数组（或vector<vector<int>>），0和1为整数。 输出：一个包含多个连通区域的列表，每个连通区域是一个点的列表（可以用vector<pair<int,int>>表示 or自己定义数据结构）。

3.代码

（1）c++ BFS

#include <iostream>
#include <vector>
#include <queue>
#include <utility> // for pair

using namespace std;

// 定义坐标类型
typedef pair<int, int> Point;

// 获取所有连通区域的坐标集合
vector<vector<Point>> findConnectedRegions(const vector<vector<int>>& matrix) {
    // 矩阵尺寸
    int rows = matrix.size();
    if (rows == 0) return {};
    int cols = matrix[0].size();
    
    // 访问标记矩阵
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    
    // 连通区域结果集
    vector<vector<Point>> regions;
    
    // 4连通方向：上、下、左、右
    vector<Point> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    // 遍历所有像素
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            // 跳过0值或已访问的像素
            if (matrix[i][j] == 0 || visited[i][j]) 
                continue;
            
            // 初始化新的连通区域
            vector<Point> region;
            queue<Point> q;
            
            // 从当前点开始BFS
            q.push({i, j});
            visited[i][j] = true;
            
            while (!q.empty()) {
                Point p = q.front();
                q.pop();
                int x = p.first, y = p.second;
                
                // 将当前点加入区域
                region.push_back(p);
                
                // 检查4个方向
                for (const auto& dir : directions) {
                    int nx = x + dir.first;
                    int ny = y + dir.second;
                    
                    // 检查边界
                    if (nx >= 0 && nx < rows && ny >= 0 && ny < cols) {
                        // 如果是1且未访问
                        if (matrix[nx][ny] == 1 && !visited[nx][ny]) {
                            visited[nx][ny] = true;
                            q.push({nx, ny});
                        }
                    }
                }
            }
            
            // 将当前区域加入结果集
            regions.push_back(region);
        }
    }
    
    return regions;
}

int main() {
    // 示例：创建一个200×200的01矩阵
    const int SIZE = 200;
    vector<vector<int>> matrix(SIZE, vector<int>(SIZE, 0));
    
    // 随机生成一些连通区域（实际应用中应替换为真实数据）
    // 这里创建两个简单区域作为示例
    for (int i = 50; i < 100; i++) {
        for (int j = 50; j < 100; j++) {
            matrix[i][j] = 1;  // 第一个方形区域
        }
    }
    
    for (int i = 150; i < 180; i++) {
        for (int j = 120; j < 170; j++) {
            matrix[i][j] = 1;  // 第二个矩形区域
        }
    }
    
    // 添加一个对角线区域
    for (int i = 0; i < 30; i++) {
        matrix[i][i] = 1;
    }
    
    // 查找所有连通区域
    vector<vector<Point>> regions = findConnectedRegions(matrix);
    
    // 输出结果
    cout << "Found " << regions.size() << " connected regions:\n";
    for (int i = 0; i < regions.size(); i++) {
        cout << "Region " << i+1 << " has " << regions[i].size() << " points.\n";
        
        // 输出前5个点（大区域只输出部分）
        int num_to_show = min(5, static_cast<int>(regions[i].size()));
        for (int j = 0; j < num_to_show; j++) {
            cout << "  (" << regions[i][j].first << ", " << regions[i][j].second << ")";
        }
        if (regions[i].size() > num_to_show) {
            cout << " ... and " << regions[i].size() - num_to_show << " more";
        }
        cout << endl;
    }
    
    return 0;
}

（2）c++ BFS Eigen

使用eigen做上面的题

#include <iostream>
#include <vector>
#include <queue>
#include <Eigen/Dense>

using namespace Eigen;
using namespace std;

// 查找所有连通区域
vector<vector<Vector2i>> findConnectedRegions(const MatrixXi& matrix) {
    vector<vector<Vector2i>> regions;
    int rows = matrix.rows();
    int cols = matrix.cols();
    
    // 访问标记矩阵
    MatrixXi visited = MatrixXi::Zero(rows, cols);
    
    // 4连通方向：上、下、左、右
    vector<Vector2i> directions = {
        Vector2i(-1, 0), Vector2i(1, 0), Vector2i(0, -1), Vector2i(0, 1)
    };
    
    // 遍历所有像素
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            // 跳过0值或已访问的像素
            if (matrix(i, j) == 0 || visited(i, j) == 1) 
                continue;
            
            // 初始化新的连通区域
            vector<Vector2i> region;
            queue<Vector2i> q;
            
            // 从当前点开始BFS
            q.push(Vector2i(i, j));
            visited(i, j) = 1;
            
            while (!q.empty()) {
                Vector2i p = q.front();
                q.pop();
                
                // 将当前点加入区域
                region.push_back(p);
                
                // 检查4个方向
                for (const auto& dir : directions) {
                    Vector2i neighbor = p + dir;
                    int nx = neighbor(0);
                    int ny = neighbor(1);
                    
                    // 检查边界
                    if (nx >= 0 && nx < rows && ny >= 0 && ny < cols) {
                        // 如果是1且未访问
                        if (matrix(nx, ny) == 1 && visited(nx, ny) == 0) {
                            visited(nx, ny) = 1;
                            q.push(neighbor);
                        }
                    }
                }
            }
            
            // 将当前区域加入结果集
            regions.push_back(region);
        }
    }
    
    return regions;
}

// 创建测试矩阵
MatrixXi createTestMatrix(int size) {
    MatrixXi matrix = MatrixXi::Zero(size, size);
    
    // 添加一些区域
    for (int i = 50; i < 100; i++) {
        for (int j = 50; j < 100; j++) {
            matrix(i, j) = 1;  // 方形区域
        }
    }
    
    for (int i = 150; i < 180; i++) {
        for (int j = 120; j < 170; j++) {
            matrix(i, j) = 1;  // 矩形区域
        }
    }
    
    // 添加对角线区域
    for (int i = 0; i < 30; i++) {
        matrix(i, i) = 1;
    }
    
    // 添加孤立的点
    matrix(10, 150) = 1;
    matrix(160, 10) = 1;
    
    // 添加一个小孔洞
    matrix(75, 75) = 0;
    
    return matrix;
}

int main() {
    const int SIZE = 200;
    
    // 创建测试矩阵
    MatrixXi matrix = createTestMatrix(SIZE);
    
    // 查找所有连通区域
    auto regions = findConnectedRegions(matrix);
    
    // 输出结果
    cout << "Found " << regions.size() << " connected regions:\n";
    for (size_t i = 0; i < regions.size(); i++) {
        cout << "Region " << i+1 << " has " << regions[i].size() << " points.\n";
        
        // 输出前5个点（大区域只输出部分）
        int num_to_show = min(5, static_cast<int>(regions[i].size()));
        for (int j = 0; j < num_to_show; j++) {
            auto& p = regions[i][j];
            cout << "  (" << p(0) << ", " << p(1) << ")";
        }
        if (regions[i].size() > num_to_show) {
            cout << " ... and " << regions[i].size() - num_to_show << " more";
        }
        cout << endl;
    }
    
    // 可选：保存矩阵到文件
    // ofstream fout("matrix.txt");
    // fout << matrix << endl;
    // fout.close();
    
    return 0;
}

代码说明

1. Eigen矩阵使用：

   • MatrixXi 用于存储整数矩阵

   • Vector2i 表示二维坐标点

   • 使用Zero()初始化矩阵

2. 连通区域检测：

   • 使用BFS算法遍历连通区域

   • 使用4连通方向（可轻松扩展为8连通）

   • 边界检查直接使用矩阵的行列尺寸

3. 测试矩阵创建：

   • 包含多种形状区域：方形、矩形、对角线

   • 添加孤立点和孔洞测试边界情况

4. 输出结果：

   • 显示找到的区域数量

   • 显示每个区域的点数

   • 显示每个区域的部分坐标点

运行：

g++ -std=c++11 -I/path/to/eigen eigen_connected_regions.cpp -o eigen_connected_regions

结果：

Found 4 connected regions:
Region 1 has 2499 points.
  (50, 50)  (50, 51)  (50, 52)  (50, 53)  (50, 54) ... and 2494 more
Region 2 has 30 points.
  (0, 0)  (1, 1)  (2, 2)  (3, 3)  (4, 4) ... and 25 more
Region 3 has 1 points.
  (10, 150)
Region 4 has 1 points.
  (160, 10)