连接组件标签 - 实施 [英] Connected Component Labeling - Implementation

问题描述

几天前我问过一个类似的问题，但我还没有找到解决我的问题的有效方法.我正在开发一个简单的控制台游戏，我有一个像这样的二维数组:

I have asked a similar question some days ago, but I have yet to find an efficient way of solving my problem. I'm developing a simple console game, and I have a 2D array like this:

1,0,0,0,1
1,1,0,1,1
0,1,0,0,1
1,1,1,1,0
0,0,0,1,0

我正在尝试查找由相邻 1(4 路连接)组成的所有区域.因此，在此示例中，2 个区域如下:

I am trying to find all the areas that consist of neighboring 1's (4-way connectivity). So, in this example the 2 areas are as following:

1
1,1
  1
1,1,1,1
      1

和:

       1
     1,1
       1

我一直在研究的算法会找到一个单元格的邻居的所有邻居，并且在这种矩阵上运行得非常好.但是，当我使用更大的数组(如 90*90)时，程序非常慢，有时使用的大数组会导致堆栈溢出.

The algorithm, that I've been working on, finds all the neighbors of the neighbors of a cell and works perfectly fine on this kind of matrices. However, when I use bigger arrays (like 90*90) the program is very slow and sometimes the huge arrays that are used cause stack overflows.

我的另一个问题的一个人告诉我关于连接组件标签是我的问题的有效解决方案.

One guy on my other question told me about connected-component labelling as an efficient solution to my problem.

有人可以向我展示使用这种算法的任何 C++ 代码吗，因为我对它如何与这种不相交的数据结构一起实际工作感到有点困惑...

Can somebody show me any C++ code which uses this algorithm, because I'm kinda confused about how it actually works along with this disjoint-set data structure thing...

非常感谢您的帮助和时间.

Thanks a lot for your help and time.

推荐答案

我先给你代码，再解释一下:

I'll first give you the code and then explain it a bit:

// direction vectors
const int dx[] = {+1, 0, -1, 0};
const int dy[] = {0, +1, 0, -1};

// matrix dimensions
int row_count;
int col_count;

// the input matrix
int m[MAX][MAX];

// the labels, 0 means unlabeled
int label[MAX][MAX];

void dfs(int x, int y, int current_label) {
  if (x < 0 || x == row_count) return; // out of bounds
  if (y < 0 || y == col_count) return; // out of bounds
  if (label[x][y] || !m[x][y]) return; // already labeled or not marked with 1 in m

  // mark the current cell
  label[x][y] = current_label;

  // recursively mark the neighbors
  for (int direction = 0; direction < 4; ++direction)
    dfs(x + dx[direction], y + dy[direction], current_label);
}

void find_components() {
  int component = 0;
  for (int i = 0; i < row_count; ++i) 
    for (int j = 0; j < col_count; ++j) 
      if (!label[i][j] && m[i][j]) dfs(i, j, ++component);
}

这是解决这个问题的常用方法.

This is a common way of solving this problem.

方向向量只是寻找相邻单元格(在四个方向中的每一个方向)的好方法.

The direction vectors are just a nice way to find the neighboring cells (in each of the four directions).

dfs 函数对网格执行深度优先搜索.这只是意味着它将访问从起始单元格可到达的所有单元格.每个单元格都将标有 current_label

The dfs function performs a depth-first-search of the grid. That simply means it will visit all the cells reachable from the starting cell. Each cell will be marked with current_label

find_components 函数遍历网格的所有单元格，如果找到未标记的单元格(标有 1)，则开始组件标记.

The find_components function goes through all the cells of the grid and starts a component labeling if it finds an unlabeled cell (marked with 1).

这也可以使用堆栈迭代地完成.如果用队列替换堆栈，您将获得bfs 或广度优先搜索.

This can also be done iteratively using a stack. If you replace the stack with a queue, you obtain the bfs or breadth-first-search.

这篇关于连接组件标签 - 实施的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！