用递归方法来搜索连通区域

  直接使用递归方法来搜索连通区域,如果连通区域是大的整块的值,这样就会出现递归溢出的问题,所以我使用了边界递归的思路,建立一个图像大小的二值数组,保存图像的每个像素的值(0或者1).这样在递归的时候如果一个像素的4或者8方向都是跟自己值相同,就可以跳过这点继续搜索,因为他不在边界上,同时为搜索过的每个像素保存状态,后面就可以跳过搜索过的点.

下面是C#描述算法:

private bool[][] sArr;
    private bool[][] vArr;
//
    private void findRect()
    {
      recArr = newArrayList();
      for (int i=0;i<bmp.Width; i++){
        for(int j=0; j<bmp.Height; j++)
          sArr[i][j]=false;
      }
      //
      for (int i=1;i<bmp.Width-1; i++) {
        for(int j=1; j<bmp.Height-1; j++) {
          if(vArr[i][j]) {
            rec= new Rectangle();
            rec.Y= j;
            rec.Height= j;
            rec.X= i;
            rec.Width= i;
            //
            if(findNext(i,j)) {
              if(rec.Width>0 && rec.Height>0) {
                rec.Height= rec.Height - rec.Y;
                rec.Width= rec.Width - rec.X;
                drawOneRec(rec);
                recArr.Add(rec);
              }
            }
            fnCount= 0;
          }
        }
      }
    }

    private int fnCount=0;

    private bool findNext(int i,intj)
    {
      fnCount++;
      if(fnCount> 10000)
      {
        //fnCount= 0;
        returntrue;
      }
      try
      {
        if(i<2||i>bmp.Width-2||j<2||j>bmp.Height-2)
        {
          //throw(newException("error"));
        }
        elseif (vArr[i][j] && !sArr[i][j])
        {
          if(j<rec.Y)
          {
            rec.Y=j;
          }
          if(j>rec.Height)
          {
            rec.Height=j;
          }
          if(i<rec.X)
          {
            rec.X=i;
          }
          if(i>rec.Width)
          {
            rec.Width=i;
          }
          //
          sArr[i][j]= true;
          //if(!vArr[i+1][j+1] || !vArr[i+1][j-1])
          if(vArr[i+1][j] && !sArr[i+1][j])
            findNext(i+1,j);
          if(vArr[i-1][j] && !sArr[i-1][j])
            findNext(i-1,j);
          if(vArr[i][j+1] && !sArr[i][j+1])
            findNext(i,j+1);
          if(vArr[i][j-1] && !sArr[i][j-1])
            findNext(i,j-1);
     
          //
          //findNext(i+1,j+1);
          //findNext(i-1,j-1);
          //findNext(i-1,j+1);
          //findNext(i+1,j-1);

       
        }
      }
      catch(Exception e)
      {
        //MessageBox.Show(e.Message);
        //returntrue;
       
      }
      returntrue;

  }

本文转自feisky博客园博客，原文链接：http://www.cnblogs.com/feisky/archive/2008/04/11/1586639.html，如需转载请自行联系原作者