网站导航
> 技术文档 > 【c++】200*200 01灰度矩阵求所有的连通区域坐标集合

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

网友: 技术文档 2025-07-26 19:57:30

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>），0和1为整数。 输出：一个包含多个连通区域的列表，每个连通区域是一个点的列表（可以用vector<pair>表示 or自己定义数据结构）。

3.代码

（1）c++ BFS

#include #include #include #include  // for pairusing namespace std;// 定义坐标类型typedef pair Point;// 获取所有连通区域的坐标集合vector<vector> findConnectedRegions(const vector<vector>& matrix) { // 矩阵尺寸 int rows = matrix.size(); if (rows == 0) return {}; int cols = matrix[0].size(); // 访问标记矩阵 vector<vector> visited(rows, vector(cols, false)); // 连通区域结果集 vector<vector> regions; // 4连通方向：上、下、左、右 vector 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 region; queue 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 = 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> matrix(SIZE, vector(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> 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(regions[i].size())); for (int j = 0; j < num_to_show; j++) { cout << \" (\" << regions[i][j].first << \", \" << regions[i][j].second < num_to_show) { cout << \" ... and \" << regions[i].size() - num_to_show << \" more\"; } cout << endl; } return 0;}

（2）c++ BFS Eigen

使用eigen做上面的题

#include #include #include #include using namespace Eigen;using namespace std;// 查找所有连通区域vector<vector> findConnectedRegions(const MatrixXi& matrix) { vector<vector> regions; int rows = matrix.rows(); int cols = matrix.cols(); // 访问标记矩阵 MatrixXi visited = MatrixXi::Zero(rows, cols); // 4连通方向：上、下、左、右 vector 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 region; queue 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 = 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(regions[i].size())); for (int j = 0; j < num_to_show; j++) { auto& p = regions[i][j]; cout << \" (\" << p(0) << \", \" << p(1) < 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 moreRegion 2 has 30 points. (0, 0) (1, 1) (2, 2) (3, 3) (4, 4) ... and 25 moreRegion 3 has 1 points. (10, 150)Region 4 has 1 points. (160, 10)

拔智齿技巧

网络标签：

相关问题