连接组件标签-实施 [英] Connected Component Labeling - Implementation
问题描述
几天前,我曾问过类似的问题,但我还没有找到解决问题的有效方法. 我正在开发一个简单的控制台游戏,并且我有一个2D数组,如下所示:
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路连通性)的所有区域.因此,在此示例中,这两个区域如下:
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 函数对网格执行 depth-first-search .这只是意味着它将访问从起始单元格可到达的所有单元格.每个单元格都将标记为 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 或 breadth-first-search .
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屋!