[C/C++] Connected Component

• Connected Component

Download:conncpn.cpp

Connected Component是圖學理論裡一個很重要且很基本的定理，他主要的用意就是將一張圖畫分成數個區塊，一般分為四方向鄰邊偵測（上下左右），以及八方向鄰邊偵測（上下左右，右上，右下，左上，左下）。下圖是一個10x10的矩陣，乍看之下所有有效數值都是1，如果以八方向來劃分共可分成六堆，分堆原則很簡單，如果某一個元素他的八方向鄰邊皆為0，那他就自成一堆，反之則與鄰邊的數值成為一堆。



以八方向為例，只需要檢測左，左上，上，這三個方向數值即可:



檢測的程式碼片段如下：

void findCpn(int **map, int row, int col)
{
    int i,j,currn=0,max;
    for(i=1;i<row+1;i++){
        for(j=1;j<col+1;j++){
            if(max = (findMax(map[i][j-1], map[i-1][j], map[i-1][j-1]))){
                if(map[i][j-1] && map[i][j-1] != max) checkAndReplace(map,i,j-1,map[i][j-1],max);
                if(map[i-1][j-1] && map[i-1][j-1] != max) checkAndReplace(map,i-1,j-1,map[i-1][j-1],max);
                if(map[i-1][j] && map[i-1][j] != max) checkAndReplace(map,i-1,j,map[i-1][j],max);
                if(map[i][j]) map[i][j] = max;
            }else if(map[i][j]) map[i][j]=++currn;
        }
    }
}
比較有效率的撰寫方式會使用到Tree的結構來做分堆，由於筆者比較懶所以就直接使用類似老鼠走迷宮的遞迴模式來做鄰邊的分類，如下程式碼：
void checkAndReplace(int **map,int i,int j,int ori,int modi)
{
    if(map[i][j]==ori){
        map[i][j]=modi;
        checkAndReplace(map,i-1,j,ori,modi);
        checkAndReplace(map,i,j-1,ori,modi);
        checkAndReplace(map,i,j+1,ori,modi);
        checkAndReplace(map,i+1,j,ori,modi);
        checkAndReplace(map,i-1,j-1,ori,modi);
        checkAndReplace(map,i+1,j-1,ori,modi);
        checkAndReplace(map,i-1,j+1,ori,modi);
        checkAndReplace(map,i+1,j+1,ori,modi);
    }
}
遞迴的部份觀念非常簡單，就以某個指定的map[i][j]為中心，向八個方向做檢測。

最後的輸出結果如下：

所以你可以很清楚的看到，原始的地圖經過conncpn的程式運算之後就會劃分成如上的區塊。(這裡為了demo方便使用了recursive的形式，正常來講不應該這樣實做，因為會損失很大的效率)