计算机图形学（四）—— 实验四：种子填充算法

实验四：种子填充算法

4.1实验目的

掌握种子填充算法（递归算法）、改进的种子填充算法、扫描线种子填充算法

4.2实验内容

C++中编写函数
模板库的使用stack

4.3算法思路

所有种子填充算法的核心其实就是一个递归算法，都是从指定的种子点开始，向各个方向上搜索，逐个像素进行处理，直到遇到边界，各种种子填充算法只是在处理 颜色和边界的方式上有所不同。
边界填充算法与注入填充算法的本质其实是一样的，都是递归和搜索，区别只在于对边界的确认，也就是递归的结束条件不一样。注入填充算法没有边界的概念，只是对联通区域内指定的颜色进行替换，而边界填充算法恰恰强调边界的存在，只要是边界内的点无论是什么颜色，都替换成指定的颜色。边界填充算法在应用上也非常的广泛，画图软件中的“油漆桶”功能就是边界填充算法的例子。
扫描线种子填充算法的基本过程如下：当给定种子点(x, y)时，首先分别向左和向右两个方向填充种子点所在扫描线上的位于给定区域的一个区段，同时记下这个区段的范围[xLeft, xRight]，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。

4.4流程图

（1）种子填充算法（递归算法）
（2）边界种子填充算法（改进）
（3）扫描线种子填充算法

4.5实验步骤

（1）种子填充算法（递归算法）
通过getpixel方法来获取点的颜色，判断其是否与原颜色相同，如果不相同，则变化其颜色为新的颜色，通过递归其4连通区域来达到有序在不越出区域的情况下，到达区域内的任意元素。
（2）边界种子填充算法（改进）
通过getpixel方法来获取点的颜色，判断其是否与原颜色相同而且是否与边界颜色相同，如果都不相同，则变化其颜色为新的颜色，通过递归其4连通区域来达到有序在不越出区域的情况下，到达区域内的任意元素。
（3）扫描线种子填充算法
1） 初始化一个空的栈用于存放种子点，将种子点(x, y)入栈；
2）判断栈是否为空，如果栈为空则结束算法，否则取出栈顶元素作为当前扫描线的种子点(x, y)，y是当前的扫描线；
3） 从种子点(x, y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xLeft和xRight；
4）分别检查与当前扫描线相邻的y - 1和y + 1两条扫描线在区间[xLeft, xRight]中的像素，从xLeft开始向xRight方向搜索，若存在非边界且未填充的像素点，则找出这些相邻的像素点中最右边的一个，并将其作为种子点压入栈中，然后返回第（2）步；

4.6实验代码

（1）在CLiHuchenView().h中添加代码：

public:
	void Draw();//添加画图成员
	CDC* mpDC;//定义指针
	void Scanseedfill(int x,int y,COLORREF oldColor,COLORREF newColor);//定义扫描线种子填充算法
	void FloodFill(int x, int y, COLORREF oldcolor, COLORREF newcolor);//定义递归种子填充算法
	void BoundaryFill(int x, int y, COLORREF oldcolor, COLORREF newcolor);//定义改进的种子填充算法

（2）在LiHuchenView.cpp中添加：

//引入种子库
#include "stack"
using namespace std;
extern stack<CPoint> s;

（3）在在LiHuchenView.cpp中的OnDraw()添加：

Draw();//添加画图函数

（4）添加函数

/*
-----------------------------------区域填充算法---------------------------------------
*/
/////////////////////////////////////////////////////////////////////////////
//画图
/////////////////////////////////////////////////////////////////////////////
void CLiHuchenView::Draw()
{
	CDC *pDC=GetDC();//定义指针
	mpDC=pDC;
	POINT ptpolygon1[6]={{600,50},{600,250},{700,250},{700,230},{620,230},{620,50}};//多边形坐标
	mpDC->Polygon(ptpolygon1,6);//绘制多边形


//	Scanseedfill(610,100,RGB(255,255,255),RGB(255,0,0));//扫描线种子填充算法
//  FloodFill(610,100,RGB(255,255,255),RGB(0,255,0));//递归种子填充算法
    BoundaryFill(610,100,RGB(0,0,0),RGB(0,0,255));//边界种子填充算法
}
/////////////////////////////////////////////////////////////////////////////
//记录种子点
/////////////////////////////////////////////////////////////////////////////
struct Seed
{
	int x;int y;
};

/////////////////////////////////////////////////////////////////////////////
//扫描线种子填充算法
/////////////////////////////////////////////////////////////////////////////

void CLiHuchenView::Scanseedfill(int x, int y, COLORREF oldColor, COLORREF newColor)
{
	stack<Seed> sp;//种子库
	int xl,xr;
	bool spanNeedfill;
	Seed pt;
	pt.x=x;pt.y=y;
	sp.push(pt);
	while(!sp.empty())
	{
		pt=sp.top();sp.pop();
		y=pt.y;x=pt.x;
		while(mpDC->GetPixel(x,y)==oldColor)//向右填充
		{
			mpDC->SetPixel(x,y,newColor);
			x++;
		}
		xr=x-1;x=pt.x-1;
		while(mpDC->GetPixel(x,y)==oldColor)//向左填充
		{
			mpDC->SetPixel(x,y,newColor);
			x--;
		}
		xl=x+1;
		//处理上面一条扫描线
		x=xl;y=y+1;
		while(x<=xr)
		{
			spanNeedfill=false;
			while(mpDC->GetPixel(x,y)==oldColor)
			{
				spanNeedfill=true;
				x++;
			}
			if(spanNeedfill)
			{
				pt.x=x-1;pt.y=y;
				sp.push(pt);
				spanNeedfill=false;
			}
			while((mpDC->GetPixel(x,y)!=oldColor)&&x<=xr) x++;
		}
 
		//处理下面一条扫描线
		x=xl;y=y-2;
		while(x<=xr)
		{
			spanNeedfill=false;
			while(mpDC->GetPixel(x,y)==oldColor)
			{
				spanNeedfill=true;
				x++;
			}
			if(spanNeedfill)
			{
				pt.x=x-1;pt.y=y;
				sp.push(pt);
				spanNeedfill=false;
			}
			while((mpDC->GetPixel(x,y)!=oldColor)&&x<=xr) x++;
		}
	}

}


/////////////////////////////////////////////////////////////////////////////
//递归种子填充算法
/////////////////////////////////////////////////////////////////////////////
void CLiHuchenView::FloodFill(int x, int y, COLORREF oldcolor, COLORREF newcolor) 
{
	//判断当前颜色
	if (mpDC->GetPixel(x, y) == oldcolor)
	{

		mpDC->SetPixel(x, y,newcolor); //修改颜色
		//寻找周围的临近点，递归
        FloodFill(x, y + 1, oldcolor, newcolor);
        FloodFill(x, y - 1, oldcolor, newcolor);
        FloodFill(x - 1, y, oldcolor, newcolor);
        FloodFill(x + 1, y, oldcolor, newcolor);
     }  
}

/////////////////////////////////////////////////////////////////////////////
//改进的种子填充算法（边界填充）
/////////////////////////////////////////////////////////////////////////////
void CLiHuchenView::BoundaryFill(int x, int y, COLORREF boundarycolor, COLORREF newcolor)
{
	//判断是否为边界颜色或者新的颜色
	//默认边界颜色为黑色
	if(mpDC->GetPixel(x, y) != boundarycolor &&mpDC->GetPixel(x, y) !=newcolor)
	{
		mpDC->SetPixel(x, y, newcolor); //修改颜色
		//寻找周围的临近点，递归
        BoundaryFill(x, y + 1, boundarycolor, newcolor);
        BoundaryFill(x, y - 1, boundarycolor, newcolor);
        BoundaryFill(x - 1, y, boundarycolor, newcolor);
        BoundaryFill(x + 1, y, boundarycolor, newcolor);
	}
	
}

4.7实验结果展示

（1）扫描线种子填充算法
（2）递归种子填充算法
（3）边界种子填充算法（改进的）