《种子填充算法》由会员分享，可在线阅读，更多相关《种子填充算法（6页珍藏版）》请在金锄头文库上搜索。
1、0一、实验目标一、实验目标1.了解基于种子填充算法的基本思想；2.掌握基于种子填充算法的算法实现；3.掌握栈的使用。二、实验内容二、实验内容本次实验主要是实现递归种子填充算法、简单种子填充算法、扫描线种子填充算法以及区域图案填充算法。种子填充算法原理简述：在开始介绍种子填充算法之前，首先也介绍两个概念，就是“4-连通算法”和“8-连通算法”。既然是搜索就涉及到搜索的方向问题，从区域内任意一点出发，如果只是通过上、下、左、右四个方向搜索到达区域内的任意像素，则用这种方法填充的区域就称为四连通域，这种填充方法就称为“4-连通算法”。如果从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右
2、下全部八个方向到达区域内的任意像素，则这种方法填充的区域就称为八连通域，这种填充方法就称为“8-连通算法”。种子填充算法采用的边界定义是区域边界上所有像素均具有某个特定的颜色值，区域内部所有像素均不取这一特定颜色，而边界外的像素则可以具有和边界相同的颜色值。程序从（x，y）开始，先检测该点的颜色，如果它与边界色和填充色均不相同，就用填充色填充该点，然后检测相邻位置，以确定它们是否边界色和填充色，若不是，就填充该相邻点。这个过程延续到已经检测完边界范围内的所有像素为止。扫描线种子填充算法原理简述：当给定种子点(x, y)时，首先分别向左和向1右两个方向填充种子点所在扫描线上的位于给定区域的一个区
3、段，同时记下这个区段的范围xLeft, xRight，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。扫描线种子填充算法可由下列四个步骤实现：(1) 初始化一个空的栈用于存放种子点，将种子点(x, y)入栈；(2) 判断栈是否为空，如果栈为空则结束算法，否则取出栈顶元素作为当前扫描线的种子点(x, y)，y 是当前的扫描线；(3) 从种子点(x, y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为 xLeft 和 xRight；(4) 分别检查与当前扫描线相邻的 y - 1 和 y + 1 两条扫描
4、线在区间xLeft, xRight中的像素，从 xLeft 开始向 xRight 方向搜索，若存在非边界且未填充的像素点，则找出这些相邻的像素点中最右边的一个，并将其作为种子点压入栈中，然后返回第（2）步；区域图案填充算法：以上介绍的区域填充算法，都是把区域内部的像素全部置成同一种颜色。但在实际应用中，有时需要用图案来填充平面区域。在确定了区域内点后，不是马上对像素填色，而是先将该像素映射到图案位图的对应位置。根据图案上对应位置的像素值，决定填充颜色。一般来说，图案比填充区域要小得多。所以图案总是成周期性的，使之能通过重复使用，构成任意尺寸的图案。图案填充方式分为透明方式和不透明方式。透明方式
5、：当图案位图的对应位置为 1 时，用前景色写像素，否则，不改变该像素的值。不透明方式：则图案位图的对应位置为 1 时，用前景色写像素，否则，用背景色写像素。本实验实现在绝对定位法下用不透明方式对平面区域填充图案：1.假设填充图案是一个 M*N 的位图，用 M*N 的数组存放；2.当确定了区域内点 p(x,y)后，则图案位图上的对应位置为 p(x%M,y%N)，其中%为 c 语言整除取余运算符，然后取出图案位图该位置的像素进行填充。2三、实验步骤三、实验步骤一、打开 cgdemoMFC 工程1.打开 Microsoft Visual Studio 20082.FileOpencgdemo.sln
6、二、添加菜单1.左侧视图栏中有三个视图：ClassView、ResourceView、FileView，点击 ResourceView2.展开 cgdemo，展开 Menu，双击 IDR_MAINFRAME3.在右侧窗口菜单栏中找到“基本图形生成”菜单项，在该菜单项中添加“递归种子填充算法”，在“递归种子填充算法”属性框中找到 ID 框填：ID_FILLRECURSION。在该菜单项中添加“简单种子填充算法”，在“简单种子填充算法”属性框中找到 ID 框填：ID_FILLEASY。在该菜单项中添加“扫描线种子填充算法”，在“扫描线种子填充算法”属性框中找到 ID 框填：ID_FILLZZSCA
7、NLINE。在该菜单项中添加“区域图案填充算法”，在“区域图案填充算法”属性框中找到 ID 框填：ID_FILLPATTERN。三、创建、编辑函数1.打开 cgdemoView.h 头文件，在 cgdemoView 类枚举类型成员变量m_drawsty 中添加FILL_RECURSION、FILL_EASY,FILL_SCANLINE,FILL_PATTERN2.给菜单项“递归种子填充算法”添加命令消息响应函数 OnFillrecursion()在该函数中添加以下程序代码。 void CcgdemoView:OnFillrecursion() / TODO: Add your command
8、handler code here m_drawstyle=FILL_RECURSION; Invalidate(true);给菜单项“简单种子填充算法”添加命令消息响应函数 OnFilleasy()在该函数中添加以下程序代码。3void CcgdemoView:OnFilleasy() / TODO: Add your command handler code here m_drawstyle=FILL_EASY; Invalidate(true);给菜单项“扫描线种子填充算法”添加命令消息响应函数 OnFillzzscanline()在该函数中添加以下程序代码。 void CcgdemoV
9、iew:OnFillzzscanline() / TODO: Add your command handler code here m_drawstyle=FILL_SCANLINE; Invalidate(true);给菜单项“区域图案填充算法”添加命令消息响应函数 OnFillpattern()在该函数中添加以下程序代码。 void CcgdemoView:OnFillpattern() / TODO: Add your command handler code here m_drawstyle=FILL_PATTERN; Invalidate(true);3.在鼠标右键按下消息响应函数中
10、添加如下所示代码。 void CcgdemoView:OnRButtonDown(UINT nFlags, CPoint point) / TODO: Add your message handler code here and/or call default switch(m_drawstyle) case FILL_RECURSION: case FILL_EASY: case FILL_SCANLINE: case FILL_PATTERN:4.在鼠标移动消息响应函数中添加如下所示代码。 void CcgdemoView:OnMouseMove(UINT nFlags, CPoint p
11、oint) / TODO: Add your message handler code here and/or call default switch(m_drawstyle) case LINE_DDA: case LINE_MIDPT:4case LINE_CIRCLE: 5.在 cgdemoView.h 头文件类中分别添加成员函数 void FillRecursion(CDC* pDC,int x,int y,int boundarycolor,int newcolor);并在 cgdemoView.cpp 源文件中void FillRecursion(CDC* pDC,int x,in
12、t y,int boundarycolor,int newcolor);为其添加编写的递归种子填充算法；在 cgdemoView.h 头文件类中分别添加成员函数 void EasySeedFill(CDC* pDC,CPoint seedpot,int boundarycolor,int newcolor);并在 cgdemoView.cpp 源文件中 void EasySeedFill(CDC* pDC,CPoint seedpot,int boundarycolor,int newcolor);为其添加编写的简单种子填充算法；在 cgdemoView.h 头文件类中分别添加成员函数 voi
13、d ScanLineSeedFill(CDC* pDC,int x,int y,int boundarycolor,int newcolor);并在cgdemoView.cpp 源文件中 void ScanLineSeedFill(CDC* pDC,int x,int y,int boundarycolor,int newcolor);为其添加编写的扫描线种子填充算法；在 cgdemoView.h 头文件类中分别添加成员函数 void FillPattern(CDC* pDC,int x,int y,int boundarycolor,int newcolor);并在 cgdemoView.c
14、pp 源文件中void FillPattern(CDC* pDC,int x,int y,int boundarycolor,int newcolor);为其添加编写的区域图案填充算法；在种子填充算法中用到栈 stack，因此要在 cgdemoView.cpp 添加#include “stack“头文件，并使用标准名空间。在 cgdemoView.cpp 源文件中 void CcgdemoView:OnDraw(CDC* pDC)添加m_drawstyle 分别为选中四种算法所执行的代码。5四、实验遇到的问题及其解决方法四、实验遇到的问题及其解决方法（重点）（重点）在编写递归种子填充算法时，如
15、果多边形画的太大程序会崩溃，这是由于递归种子填充算法本身的 bug，系统栈空间不足时会导致程序崩溃。在编写简单种子填充算法时，用到数据结构栈(stack)的使用，在该算法中定义 stackst; 编译的时候出现如下错误：error C2065: stack : undeclared identifier error C2275: POINT : illegal use of this type as an expressionerror C2065: st : undeclared identifiererror C2228: left of .push must have class/str
16、uct/unionerror C2228: left of .empty must have class/struct/union通过以上错误的提示发现是栈的头文件没有添加。通过添加栈的头文件#include “stack“，但是编译还是出现相同的错误。通过添加 using namespace std;最后编译成功。C+标准程序库中的所有标识符都被定义于一个名为 std 的 namespace 中。namespace 是指标识符的各种可见范围，命名空间用关键字 namespace 来定义。命名空间是 C+的一种机制，用来把单个标识符下的大量有逻辑联系的程序实体组合到一起。此标识符作为此组群的名字。因为 stack 标识符定义在名为 std 的 namespace 中，由于没有添加 using namespace std，从而导致程序编译的时候 stack 识别错误。五、实验结论五、实验结论和收获和收获通过递归种子填充算法、简单种子填充算法、扫描线种子填充算法以及区域图案填充算法，使
