连接组件标签-实施
image-processing
5
0

几天前我曾问过类似的问题,但是我还没有找到解决问题的有效方法。我正在开发一个简单的控制台游戏,并且我有一个2D数组,如下所示:

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路连通性)的区域。因此,在此示例中,这两个区域如下:

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

和:

       1
     1,1
       1

我一直在努力的算法,找到了单元格邻居的所有邻居,并且在这种矩阵上工作得很好。但是,当我使用较大的数组(例如90 * 90)时,程序速度很慢,有时使用的巨大数组会导致堆栈溢出。

在另一个问题上,一个人告诉我有关连接组件标记的一种有效解决方案。

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

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

参考资料:
Stack Overflow
收藏
评论
共 2 个回答
高赞 时间 活跃

这可以通过并集查找解决(尽管如其他答案所示,DFS可能更简单)。

该数据结构背后的基本思想是重复合并同一组件中的元素。这是通过将每个组件表示为树来完成的(节点跟踪其父节点,而不是相反),您可以遍历根节点来检查2个元素是否在同一组件中,并且可以合并节点通过简单地使一个根成为另一个根的父代。

一个简短的代码示例演示了这一点:

const int w = 5, h = 5;
int input[w][h] =  {{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}};
int component[w*h];

void doUnion(int a, int b)
{
    // get the root component of a and b, and set the one's parent to the other
    while (component[a] != a)
        a = component[a];
    while (component[b] != b)
        b = component[b];
    component[b] = a;
}

void unionCoords(int x, int y, int x2, int y2)
{
    if (y2 < h && x2 < w && input[x][y] && input[x2][y2])
        doUnion(x*h + y, x2*h + y2);
}

int main()
{
    for (int i = 0; i < w*h; i++)
        component[i] = i;
    for (int x = 0; x < w; x++)
    for (int y = 0; y < h; y++)
    {
        unionCoords(x, y, x+1, y);
        unionCoords(x, y, x, y+1);
    }

    // print the array
    for (int x = 0; x < w; x++)
    {
        for (int y = 0; y < h; y++)
        {
            if (input[x][y] == 0)
            {
                cout << ' ';
                continue;
            }
            int c = x*h + y;
            while (component[c] != c) c = component[c];
            cout << (char)('a'+c);
        }
        cout << "\n";
    }
}

现场演示

上面将显示每组使用不同字母的字母。

p   i
pp ii
 p  i
pppp 
   p 

修改此属性应该很容易,以分别获取组件或获取与每个组件相对应的元素列表。一种想法是替换cout << (char)('a'+c);上面带有componentMap[c].add(Point(x,y))其中componentMapmap<int, list<Point>> -然后,此映射中的每个条目将对应于一个组件,并给出一个点列表。

有各种优化措施可以提高联合查找的效率,以上只是基本的实现。

收藏
评论

我先给你代码,然后再解释一下:

// 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);
}

这是解决此问题的常用方法。

方向向量只是找到相邻单元(在四个方向中的每个方向)的一种好方法。

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

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

也可以使用堆栈来迭代完成此操作。如果将队列替换为队列,则将获得bfswideth-first-search

收藏
评论
新手导航
  • 社区规范
  • 提出问题
  • 进行投票
  • 个人资料
  • 优化问题
  • 回答问题

关于我们

常见问题

内容许可

联系我们

@2020 AskGo
京ICP备20001863号