本文共 8018 字，大约阅读时间需要 26 分钟。

区域填充算法，代码原创，已经过测试。

包含：扫描线种子填充算法(可以填充凹形区域) 和广度优先搜索算法。

时间复杂度：N 矩阵的长宽 x1000 ， 时间单位：毫秒

 

 

//________________________________

readme：

RegionFilling.h / .cpp 是填充算法实现文件

RegionFill.cpp 是演示文件。

//_______________________________

 

// RegionFill.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include "RegionFilling.h"#include <iostream>#include "time.h"#include "math.h"using namespace std;

void usageDemo(int seedx, int seedy);

int _tmain(int argc, _TCHAR* argv[])

{

 usageDemo(4,4);  return 1;

}

void usageDemo(int seedx, int seedy)

{  // step1. indicate a pointer(mat) to 2D matrix or image. // step2. connect edge points. then we got the contour of the region // step3. call scan line regionfilling (or bfs) function to fill region.  // step4. save matrix to a image

 

 

 char **mat= new char*[30]; for(int i=0; i<30; i++) {   mat[i] = new char[30];  for(int j=0; j<30; ++j)  {    mat[i][j]=0;  } } // step1: indicate a pointer(mat) to 2D matrix or image. CRegionFilling rgnfil(mat,30,30,1,0,0);

 int x[9];

 int y[9];

 x[0]=2;y[0]=2;

 x[1]=2;y[1]=28; x[2]=6;y[2]=15; x[3]=10;y[3]=27; x[4]=14;y[4]=15; x[5]=18;y[5]=27; x[6]=23;y[6]=15; x[7]=28;y[7]=26; x[8]=27;y[8]=4;

 // step2. connect edge points. then we got the contour of the region

 rgnfil.drawLine(x[0],y[0],x[8],y[8]);

 for(int i=1; i<9; ++i)

 {   rgnfil.drawLine(x[i-1],y[i-1],x[i],y[i]); }

 

 for(int i=0; i<30; ++i)

 {   for(int j=0; j<30; ++j)  {    if(i==0 || j==0 ||i==30-1 || j==30-1)    mat[i][j]=1;  } }

 for(int i=0; i<30; ++i)

 {   for(int j=0; j<30; ++j)  {    if(mat[i][j]==1)   {     cout<<"* ";   }   else    cout<<"  ";

  }

  cout<<endl;

 }

 cout<<endl;

 //step3. call scan line regionfilling function to fill region.

 rgnfil.regionfill_scanning(seedx,seedy);

 for(int i=0; i<30; ++i) {   for(int j=0; j<30; ++j)  {    if(mat[i][j]==1)   {     cout<<"* ";   }   else    cout<<"  ";

  }

  cout<<endl; } cout<<endl<<endl<<endl;

 //step4. save matrix to a image  //code need to be added.

 for(int del=0; del<30; ++del)

  delete []mat[del]; delete []mat;

}

 

 

#pragma once

#include <stack>using namespace  std;

class CRegionFilling

{ public: //pmat pointer to 2D matrix(image). 指向二维矩阵(图像)的指针 //Width: matrix width 矩阵宽度 //Height:matrix height 矩阵高度 //fillColor: fill color 填充颜色 //blankColor: indicate this point is not filled 空白的颜色 //connective_0for4_1for8: 4-connected using 0,8-connected using 1.连通性_0指定四连通_1指定8连通 CRegionFilling(char **pmat, int Width, int Height, int fillColor=1,int blankColor=0,int connective_0for4_1for8=0) :mat(pmat),width(Width),height(Height), fillclr(fillColor),blankclr(blankColor), connectivity(connective_0for4_1for8) {}; ~CRegionFilling(void){};private: char **mat; int width; int height; int fillclr; int blankclr; int connectivity;

 struct cpixel

 {   cpixel(void){};  cpixel(int X, int Y):x(X),y(Y){};  int x;  int y; }; stack<cpixel> stc;

 

public: //(x0,y0) start point of line, (x1,y1):end point of line. // if(mat==NULL) return false, else return true. bool drawLine(int x0, int y0, int x1, int y1);

 //Time cost = O(N), N:height of matrix(image)

 bool regionfill_scanning(int seedx, int seedy);  //Time cost = O(M*N), M*N means height*width of matrix(image) bool regionfill_bfs(int seedx, int seedy);

 

private: //this function is called by Breadth First Search (BFS) algorithm //check the four neighbors of seed point, //if( belongs to region && not filled) push to queue and brush it with fillclr. //return value: if( belongs to region && not filled) return true,else return false. inline bool checkNeighbor(int x, int y, int direction, cpixel& pt);

private: //called by  scan line algorithm //fill scan line. (xr,yr) is the most right point of current scan line. inline bool scanning(int xr,int yr);

 //find new seeds and push to stack .

 //return value: if found return true, else return false. bool pushNewSeeds(int lx, int rx, int y);

};

bool CRegionFilling::checkNeighbor(int x, int y, int direction, cpixel& pt)

{

 if(direction==0 && y-1>=0 && mat[y-1][x]==blankclr )

 {   pt.x=x; pt.y=y-1;  return true;

 }

 else if(direction==2 && y+1<height && mat[y+1][x]==blankclr) {   pt.x=x;pt.y=y+1;  return true; } else if(direction==1 && x+1<width && mat[y][x+1]==blankclr) {   pt.x=x+1; pt.y=y;  return true; } else if(direction==3 && x-1>=0 && mat[y][x-1]==blankclr) {   pt.x=x-1; pt.y=y;  return true; } else  return false;

}

bool CRegionFilling::scanning(int xr,int yr)

{  int x=xr; while(x>=0 && mat[yr][x]==blankclr) {   mat[yr][x]=fillclr;  --x; } return true;}

 

 

 

 

 

#include "StdAfx.h"

#include "RegionFilling.h"#include "math.h"#include <stack>#include <queue>

using namespace std;

bool CRegionFilling::regionfill_scanning(int seedx, int seedy){  int lx,rx; int x=seedx; int y=seedy; cpixel seed(seedx,seedy);  //1 找到current行的右端点 while(x<width && mat[y][x]==blankclr)  ++x; --x; rx=x; //2找到current行的左端点 x=seedx; while(x>=0 && mat[y][x]==blankclr)  --x; ++x; lx=x;  stc.push(cpixel(rx,y)); while(!stc.empty()) {   seed = stc.top();  stc.pop();    rx=seed.x;  y=seed.y;    lx=rx;  while(lx>=0 && mat[y][lx] ==blankclr)   --lx;  ++lx;  scanning(seed.x,seed.y);    if(y-1>=0)    pushNewSeeds(lx,rx,y-1);  if(y+1<width)   pushNewSeeds(lx,rx,y+1);

 }

 return true;

}

 

 

bool CRegionFilling::pushNewSeeds(int lx, int rx, int y){

 if(y<0 || y>=height) return false;

 //返回标识ret

 //true;seeds or seed are found。 // false: seed not found. bool ret=false;

 //x是新的种子点的x坐标。

 int x=rx; int xa=lx,xb=rx; while(lx<=rx) {   x=rx;  //step1  //4.11 潜在的新种子点在rx之右，■是旧的种子点  // ●○○○○●  // ●●●■●  //       rx  //x 1,2,3,4,5,6  if(mat[y][x]==blankclr)  {    //step1.找到新的种子点   while(x<width && mat[y][x]== blankclr)    ++x;    //x=6   --x;     //x=5    stc.push(cpixel(x,y)); //new seed.x=5   ret=true;    //step2.找到扫描线的左端点   while(x>=0 && mat[y][x]==blankclr)    --x;       rx=x;     //rx=1   // ●○○○○●   // ●●●■●   // rx      //x 1,2,3,4,5,6  }  //4.12潜在的新种子点在 rx之左。  // ●○○○○●●●  // ●●●●●●■●  //             rx  else  {    --x;   while(x>=lx && mat[y][x]==fillclr)    --x;   if(x>=lx)   {     stc.push(cpixel(x,y));    ret=true;    //找到扫描线的左端点    while(x>=0 && mat[y][x]==blankclr)     --x;    rx=x;   }  }

  if(lx>rx) continue;

  // step1.   // ●○○○○●○○○○●○○○○●  // ●●●●●●●●●●●●●●●●  //   lx                rx  // 新的种子点位置      ★

  // step2

  // ●○○○○●○○○○●○○○○●  // ●●●●●●●●●●●●●●●●  //             lx      rx  //     ★

  // step3 进入第二次循环

  // ●○○○○●○○○○●○○○○●  // ●●●●●●●●●●●●●●●●  //             lx  //           rx              //               ★  //(lx>rx) 结束while

  //从左边lx向右找，找到潜在的新种子点SEED_NEW，看 SEED_NEW =? SEED_R

  //step2  x=lx;  if(mat[y][x]==blankclr)  {    //向右找   while(x<rx && mat[y][x]==blankclr)    ++x;   --x;   stc.push(cpixel(x,y));   ret=true;   lx=x+2;  }  else  {    //仍然是向右找，找到扫描线的左端点停止，再继续找扫描线的右端点。   while(x<rx && mat[y][x]==fillclr)    ++x;   //找扫描线的右端点。   if(x<rx)   {     while(x<rx && mat[y][x]==blankclr)     ++x;    --x;    stc.push(cpixel(x,y));    ret=true;   }   lx=x+2;  }              }//while has another scan line to be found.

 // 凹形区域的填充

 // ●●●●      ●●●    ●●●● // ●○○●      ●○●    ●○○●  // ●○○○●  ●○○●  ●○○○●  // ●○○○●  ●○○●  ●○○○●  // ●○○○○●○○○○●○○○○● // ●○○○○○○○○○○○○○○●  // ●○○○○○○○○○○○○○○●  // ●●●●●●●●●●●●●●●●

 return ret;

 

}//findSeed()

 

//广度优先搜索算法(Breadth First Search) -- 搜索填充点--入队列--填充

bool CRegionFilling::regionfill_bfs(int seedx, int seedy){  queue<cpixel> s; s.push(cpixel(seedx,seedy)); register cpixel pt; while(!s.empty()) {   pt=s.front();   s.pop();  register cpixel newpt;  //i=0-->3 表示 ↑ → ↓ ←  for(int i=0; i<4; ++i)  {    if( checkNeighbor(pt.x,pt.y,i,newpt))    {     s.push(newpt);    mat[newpt.y][newpt.x]=fillclr;   }  }

 }

 return true;

}

bool CRegionFilling::drawLine(const int x0, const int y0, const int x1, const int y1)

{  if(!mat) return false; //temp variable x,y int x,y;

 //水平和竖直情况

 if(x1==x0) {   for(y=y0; y<=y1; ++y)   mat[y][x1]=fillclr;  return true; } if(y1==y0) {   for(x=x0; x<=x1; ++x)   mat[y1][x]=fillclr;  return true; }

 //斜线  y = k*x + b

 int dx=x1-x0; int dy=y1-y0;  double k=dy/(double)dx; double b=(x1*y0-x0*y1)/(double)(x1-x0); if( abs(dx) >= abs(dy) ) {   int l,r,prey;  if(x0<x1) {l=x0;r=x1;prey=y0;}  else {l=x1,r=x0;prey=y1;}  for(x=l; x<=r; ++x)  {    y =(int) (k*x+b +0.5);    mat[y][x]=fillclr;   //code for 4-connective rule.   if(connectivity==0)   {     if(y!=prey)    {      mat[prey][x]=fillclr;     prey = y;    }

   }

      } } else {   int prex;  int l,r;    if(y0<y1) {l=y0;r=y1;prex=x0;}  else {l=y1,r=y0;prex=x1;}

  for(y=l; y<=r; ++y)

  {    x=(int)((y-b)/k + 0.5);   mat[y][x]=fillclr;   //code for 4-connective rule.   if(connectivity==0)   {     if(x!=prex)    {      mat[y][prex]=fillclr;     prex = x;    }   }      } }

 return true;

}