一、四向种子填充算法
void BoundaryFill4(int x, int y, COLORREF fillClr, COLORREF edgeClr, CDC *pDC)
{
COLORREF cPixel;
cPixel=pDC->GetPixel(x, y);
if((cPixel !=edgeClr)&&(cPixel !=fillClr))
{
pDC->SetPixel(x,y,fillClr);
Sleep(0);
BoundaryFill4( x, y+1, fillClr,edgeClr,pDC);
BoundaryFill4( x, y-1, fillClr,edgeClr,pDC);
BoundaryFill4( x-1, y, fillClr,edgeClr,pDC);
BoundaryFill4( x+1, y, fillClr,edgeClr,pDC);
}
}
二、八向种子填充算法
void Scanline_seed_fill(CDC *pDC, int seedx, int seedy, COLORREF color, COLORREF fillcolor)
{
COLORREF clr;
int x,y,x0,y0,xl,xr,flag,xnextspan;
iStack=0;
x=seedx;
y=seedy;
y0=y;
push(x,y);
color=pDC->SetPixel(x,y,color);
while(iStack >0)
{
pop(x,y);
clr=pDC->SetPixel(x,y,fillcolor);
x0=x+1;
while(pDC->GetPixel(x0,y) !=color)
{
pDC->SetPixelV(x0,y,fillcolor);
x0++;
}
xr=x0-1; // 最右像素
x0=x-1;
while(pDC->GetPixel(x0,y) !=color)
{
pDC->SetPixelV(x0,y,fillcolor);
x0--;
}
xl=x0+1; // 最左像素
//
x0=xl;
y=y+1;
while(x0<=xr)
{
flag=0;
while(pDC->GetPixel(x0,y) !=color &&
pDC->GetPixel(x0,y) !=clr && x0 { if(flag==0) flag=1; x0++; } if(flag==1) { if(x0==xr && pDC->GetPixel(x0,y) !=color && pDC->GetPixel(x0,y) !=clr) push(x0,y); else push(x0-1,y); flag=0; } xnextspan=x0; while(pDC->GetPixel(x0,y) ==color || pDC->GetPixel(x0,y) ==clr && x0<=xr) x0++; if(xnextspan==x0) x0++; } // x0=xl; y=y-2; while(x0<=xr) { flag=0; while(pDC->GetPixel(x0,y) !=color && pDC->GetPixel(x0,y) !=clr && x0 { if(flag==0) flag=1; x0++; } if(flag==1) { if(x0==xr && pDC->GetPixel(x0,y) !=color && pDC->GetPixel(x0,y) !=clr) push(x0,y); else push(x0-1,y); flag=0; } xnextspan=x0; while(pDC->GetPixel(x0,y) ==color || pDC->GetPixel(x0,y) ==clr && x0<=xr) x0++; if(xnextspan==x0) x0++; } } } void push(int x, int y) { if(iStack>1000) return; else { iStack++; stackX[iStack]=x; stackY[iStack]=y; } } int pop(int &x, int &y) { if(iStack<=0) return -1; x=stackX[iStack]; y=stackY[iStack]; iStack--; return iStack; } 13. 设五边形的五个顶点坐标为(10, 10)，(15, 5)，(12, 5)，(8, 2)和(4, 5)，利用多边形区域填充算法，编一程序生成一个实心图。 解：假设以上五个顶点依次对应编号A-B-C-D-E，首先计算得到ET表： 6-10 5 4 3 2 1 该多边形的AET指针的内容为： 1 AET为空 2 3 4 1 2 3 4 5 6 7 8 9 10 01234567891011121314 1516 5 6 7 8 9 10 具体编程实现如下： 第1步：(1) 根据输入的五个顶点坐标找到y 值最小的点(例如点D ，此时y=2)，并找到与D 有边关系的两个顶点(此时为E 和C)，在y=2处建立ET 边表记录(ymax 、xi 和m 值均可通过顶点坐标间的计算得到，例如DE 边的建立，特别注意：当D 点和E 点y 坐标值相同时，也即是DE 与x 轴平行，该边不能计入ET 边表)，之后标记D 点被访问过；(2) 排除访问过的点以及和该点相关联的边，重复(1)直至将ET 表建立完善。 [注]边关系的建立可通过邻接矩阵的数据结构实现，权值可以为该矩阵行编号对应点的y 坐标值，ET 边表采用邻接表的数据结构 第2步：根据ET 表构建AET 表，并逐行完成多边形填充，具体的C++代码如下： (1) 建立头文件base_class.h ，主要是边表结点结构体和ET 边表类的实现 enum ResultCode{Success, Failure}; template /种子填充算法 void CZhztchView::boundaryfill4(int x, int y, int boundarycolor, int newcolor) { int color; CClientDC dc(this); //获取客户区设备描述表 color=dc.GetPixel(x,y); if(color!=newcolor&&color!=boundarycolor) { dc.SetPixel(x,y,newcolor); boundaryfill4(x,y+1,boundarycolor,newcolor); boundaryfill4(x,y-1,boundarycolor,newcolor); boundaryfill4(x-1,y,boundarycolor,newcolor); boundaryfill4(x+1,y,boundarycolor,newcolor); } } ///////////////////////////////////////////////////////////////// /////////////// //扫描线填充算法 void CZhztchView::OnScanfill() { RedrawWindow(); CDC* pDC=GetDC(); CPen newpen(PS_SOLID,3,RGB(255,0,0)); CPen *old=pDC->SelectObject(&newpen); spt[0]=CPoint(100,100); //绘制多边形区域 spt[1]=CPoint(300,100); spt[2]=CPoint(250,250); spt[3]=CPoint(100,250); spt[4]=CPoint(150,200); spt[5]=CPoint(90,180); spt[6]=CPoint(150,150); spt[7]=CPoint(100,100); pDC->Polyline(spt,8); //pDC->SelectObject(old); //ReleaseDC(pDC); // TODO: Add your command handler code here //CDC* pDC=GetDC(); CPen newpen2(PS_SOLID,1,RGB(0,255,0)); CPen *old2=pDC->SelectObject(&newpen2); int j,k,s = 0; 实验四区域填充算法的实现 班级 08信计2班学号 20080502088 姓名许延恒分数 一、实验目的和要求： 1、理解区域的表示和类型。 2、能正确区分四连通和八连通的区域 3、了解区域填充的实验原理。 4、利用C++实现区域填充的递归算法。 二、实验内容： 1假设在多边形内有一像素已知，由此出发利用连通性找到区域内所有像素。 2 取（x，y）为种子点将整个区域填充为新的颜色。 3 进行递归填充。 三、实验结果分析 区域填充属性包括填充样式，填充颜色和填充图案的类型。C语言中定义了某种图形后，即可调用-floodfill函数，对指定区域进行填充 . 程序代码 #include 实验三区域填充种子算法实现 实验目的： 1、熟练在Visual C＋＋中程序实现及调试的能力。 2、通过程序的设计熟练区域填充种子算法过程； 3、掌握堆栈在数据结构中的应用 实验内容： 1、visual c＋＋中菜单的修改，点的输入及鼠标函数的控制； 2、复习数据结构中堆栈的建立，入栈，出栈等函数； 3、实现整个多边形的区域填充种子算法，与扫描转换算法进行区分； 实验步骤： 预处理：多边形点列的输入，存储于数组中P[100]，种子点的输入，确定为point（x，y） 确定多边形的边界色（旧画笔色），初始色（背景色），填充色（新画笔色）； 数据结构的建立：建立堆栈，包括数组stack[100],及一个指标top，用来指向当前堆栈的最外面的栈口的元素。 步骤：1、堆栈置为空，top=0; 2、将初始的种子点point进栈，push(x,y); 3、填色堆栈非空即top>0时，一直循环下列步骤 取栈顶的元素，出栈pop(x,y)，savex=x; 从当前点开始沿当前扫描线往右检验，若有未填新色的，则填色。 然后同样往左检验。 当前扫描线俩个方向都检查完后，检验上一条扫描线y=y+1; 若有未填新色的，则把所有未填新色区间的右端点压入堆栈。 同理检验下一条扫描线y=y-2; 实验指导： 一、 在实验二的基础上进行编程 ； （1） 引入实验二代码 scanline.dsw 二、 编辑菜单资源 选中窗口左边栏的“ResourceView ”，其中的“Menu ”，双击“IDR_MAINFRAME ”，右边即为菜单，在菜单上空处双击，出项如图所示窗口，其中弹出不选中； 如上，同样创建其余菜单项。(如下表)； 三、 添加消息处理函数 由菜单的“查看”，“建立类向导”，打开ClassWizard （也可CTRL+W ）为应用程序添加与菜单项相关的消息处理函数，ClassName 栏选中CScanLineView 类，根据表建立。 输入菜单项名称，（如显示多边形） 双击，出现如下窗口 扫描线种子填充算法 扫描线种子填充算法的基本过程如下：当给定种子点(x, y)时，首先分别向左和向右两个方向填充种子点所在扫描线上的位于给定区域的一个区段，同时记下这个区段的范围[xLeft, xRight]，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。 扫描线种子填充算法可由下列四个步骤实现： (1) 初始化一个空的栈用于存放种子点，将种子点(x, y)入栈； (2) 判断栈是否为空，如果栈为空则结束算法，否则取出栈顶元素作为当前扫描线的种子点(x, y)，y是当前的扫描线； (3) 从种子点(x, y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xLeft和xRight； (4) 分别检查与当前扫描线相邻的y - 1和y + 1两条扫描线在区间[xLeft, xRight]中的像素，从xLeft开始向xRight方向搜索，若存在非边界且未填充的像素点，则找出这些相邻的像素点中最右边的一个，并将其作为种子点压入栈中，然后返回第（2）步； 这个算法中最关键的是第（4）步，就是从当前扫描线的上一条扫描线和下一条扫描线中寻找新的种子点。如果新扫描线上实际点的区间比当前扫描线的[xLeft, xRight]区间大，而且是连续的情况下，算法的第（3）步就处理了这种情况。如图所示： 新扫描线区间增大且连续的情况 假设当前处理的扫描线是黄色点所在的第7行，则经过第3步处理后可以得到一个区间[6,10]。然后第4步操作，从相邻的第6行和第8行两条扫描线的第6列开始向右搜索，确定红色的两个点分别是第6行和第8行的种子点，于是按照顺序将（6, 10）和（8, 10）两个种子点入栈。接下来的循环会处理（8, 10）这个种子点，根据算法第3步说明，会从（8, 10）开始向左和向右填充，由于中间没有边界点，因此填充会直到遇到边界为止，所以尽管第8行实际区域比第7行的区间[6,10]大，但是仍然得到了正确的填充。 如果新扫描线上实际点的区间比当前扫描线的[xLeft, xRight]区间大，而且中间有边界点的情况，算法又是怎么处理呢？算法描述中虽然没有明确对这种情况的处理方法，但是第4步确定上、下相邻扫描线的种子点的方法，以及靠右取点的原则，实际上暗含了从相邻扫描线绕过障碍点的方法。如下图所示： 新扫描线区间增大且不连续的情况 算法第3步处理完第5行后，确定了区间[7, 9]，相邻的第4行虽然实际范围比区间[7, 9]大，但是因为被（4, 6）这个边界点阻碍，使得在确定种子点（4, 9）后向左填充只能填充右边的第7列到第10列之间的区域，而左边的第3列到第5列之间的区域没有填充。虽然作为第5行的相邻行，第一次对第4行的扫描根据靠右原则只确定了（4, 9）一个种子点。但是对第3行处理完后，第4行的左边部分作为第3行下边的相邻行，再次得到扫描的机会。第3行的区间是[3, 9]，向左跨过了第6列这个障碍点，第2次扫描第4行的时候就从第3列开始，向右找，可以确定种子点（4, 5）。这样第4行就有了两个种子点，就可以被完整地填充了。 由此可见，对于有障碍点的行，通过相邻边的关系，可以跨越障碍点，通过多次扫描得到完整的填充，算法已经隐含了对这种情况的处理。扫描线种子填充算法的实现如下： 计算机图形学——区域填充的扫描线算法 一．实验名称： 区域填充的扫描线算法 二．实验目的： 1、理解区域填充扫描线算法的原理； 2、实现区域填充的扫描线算法并测试； 三．算法原理： 算法基本思想: 首先填充种子点所在扫描线上位于区域内的区段，然后确定与该区段相邻的上下两条扫描线上位于区域内的区段，并依次将各区段的起始位置保存, 这些区段分别被用区域边界色显示的像素点所包围。随后,逐步取出一开始点并重复上述过程，直到所保存各区段都填充完毕为止。 借助于栈结构，区域填充的扫描线算法之步骤如下： Step 1. 初始化种子点栈：置种子点栈为空栈，并将给定的种子点入栈； Step 2. 出栈：若种子点栈为空，算法结束；否则，取栈顶元素(x，y)为种子点； Step 3. 区段填充：从种子点(x, y) 开始沿纵坐标为y 的当前扫描线向左右两个方向逐像素点进行填色，其颜色值置为newcolor 直至到达区域边界。分别以xl 和xr 表示该填充区段两端点的横坐标； Step 4. 新种子点入栈: 分别确定当前扫描线上、下相邻的两条 扫描线上位于区段[xl, xr] 内的区域内的区段。若这些区段内的像素点颜色值为newolor ,则转至Step 2；否则以区段的右端点为种子点入种子点栈，再转至Step 2。 四．原程序代码： /*****************************************/ /*4-ScanLineFill 区域填充的扫描线算法实现*/ /*****************************************/ #include 《计算机图形学实验》报告 2016年春季学期 实验四:种子点填充算法Seed Filling 实验时间：2016年9月底 实验地点： 实验目的：掌握使用opengl 的种子点填充算法，观察改变参数对生成图形的改变(改变点的位置、 颜色等) 如果要填充的区域是以图像元数据方式给出的，通常使 用种子填充算法进行区域填充。种子填充算法的核心是 一个递归算法，都是从指定的种子点开始，向各个方向 上搜索，逐个像素进行处理，直到遇到边界。种子填充算法常用四连通域和八连通域技术进行填充操作。 从区域内任意一点出发，通过上、下、左、右四个方向到达区域内的任意像素。用这种方法填充的区域就称为四连通域；这种填充方法称为四向连通算法。 从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下八个方向到达区域内的任意像素。用这种方法填充的区域就称为八连通域；这种填充方法称为八向连通算法。 算法的优点是非常简单，缺点是需要大量栈空间来存储相邻的点。 程序代码： 使用的运行环境是vc++6.0 #include 实验2：多边形区域扫描线填充或种子填充 一、实验目的 1.通过实验，进一步理解和掌握几种常用多边形填充算法的基本原理 2.掌握多边形区域填充算法的基本过程 3.掌握在C/C++环境下用多边形填充算法编程实现指定多边形的填充。 二、实验内容 用种子填充算法和扫描线填充算法等任意两种算法实现指定多边形的区域填充。 三、实验原理 种子填充算法又称为边界填充算法。其基本思想是：从多边形区域的一个内点开始，由内向外用给定的颜色画点直到边界为止。如果边界是以一种颜色指定的，则种子填充算法可逐个像素地处理直到遇到边界颜色为止。种子填充算法常用四连通域和八连通域技术进行填充操作。 四向连通填充算法： a）种子像素压入栈中； b）如果栈为空，则转e)；否则转c)； c）弹出一个像素，并将该像素置成填充色；并判断该像素相邻的四连通像素是否为边界色或已经置成多边形的填充色，若不是，则将该像素压入栈； d）转b）； e）结束。 扫描线填充算法的基本过程如下：当给定种子点(x,y)时，首先填充种子点所在扫描线上的位于给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。 区域填充的扫描线算法可由下列四个步骤实现： (1)初始化：堆栈置空。将种子点(x,y)入栈。 (2)出栈：若栈空则结束。否则取栈顶元素(x,y)，以y作为当前扫描线。 (3)填充并确定种子点所在区段：从种子点(x,y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。 (4)并确定新的种子点：在区间[xl，xr]中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。 四、实验步骤 1.复习有关算法，明确实验目的和要求； 2.依据算法思想，绘制程序流程图（指定填充多边形）； 3.设计程序界面，要求操作方便； 4.用C/C++语言编写源程序并调试、执行（最好能用动画显示填充过程）； 5.分析实验结果 6.对程序设计过程中出现的问题进行分析与总结； 7.打印源程序或把源程序以文件的形式提交； 8.按格式要求完成实验报告。 五、实验结果及分析 种子填充算法的优点是非常简单，缺点是需要大量栈空间来存储相邻的点。扫描线填充算法就是它的改进的方法。它是通过沿扫描线填充水平像素段，来处理四连通或八连通相邻点，这样就仅仅只需要将每个水平像素段的起始位置压入栈，而不需要将当前位置周围尚未处理的相邻像素都压入栈，从而可以节省大量的栈空间。 六、实验结果 实验四区域填充算法的实现 班级08信计学号58 姓名陈瑞雪分数 一、实验目的和要求： 1、掌握区域填充算法基本知识 2、理解区域的表示和类型，能正确区分四连通和八连通的区域 3、了解区域填充的实现原理，利用Microsoft Visual C++ （及EasyX_2011版） 实现区域种子填充的递归算法。 二、实验内容： 1、编程完成区域填色 2、利用画线函数，在屏幕上定义一个封闭区域。 3、利用以下两种种子填充算法，填充上述步骤中定义的区域 (1)边界表示的四连通区域种子填充的实现 (2)内点表示的四连通区域种子填充的实现 4、将上述算法作部分改动应用于八连通区域，构成八连通区域种子填充算法， 并编程实现。 三、实验结果分析 1、以上各种算法相应代码及运行结果如下： 程序代码： #include<> #include<> #include<> void FloodFill4(int x,int y,int oldcolor,int newcolor) { if(getpixel(x,y)==oldcolor) { putpixel(x,y,newcolor); Sleep(1); FloodFill4(x-1,y,oldcolor,newcolor); FloodFill4(x,y+1,oldcolor,newcolor); FloodFill4(x+1,y,oldcolor,newcolor); FloodFill4(x,y-1,oldcolor,newcolor); } } void main() { int a,b,c,d,i,j; int graphdriver=DETECT; int graphmode=0; initgraph(&graphdriver,&graphmode," "); 一、实验目标 1.了解基于种子填充算法的基本思想； 2.掌握基于种子填充算法的算法实现； 3.掌握栈的使用。 二、实验内容 本次实验主要是实现递归种子填充算法、简单种子填充算法、扫描线种子填充算法以及区域图案填充算法。 种子填充算法原理简述：在开始介绍种子填充算法之前，首先也介绍两个概念，就是“4-连通算法”和“8-连通算法”。既然是搜索就涉及到搜索的方向问题，从区域内任意一点出发，如果只是通过上、下、左、右四个方向搜索到达区域内的任意像素，则用这种方法填充的区域就称为四连通域，这种填充方法就称为“4-连通算法”。如果从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下全部八个方向到达区域内的任意像素，则这种方法填充的区域就称为八连通域，这种填充方法就称为“8-连通算法”。种子填充算法采用的边界定义是区域边界上所有像素均具有某个特定的颜色值，区域内部所有像素均不取这一特定颜色，而边界外的像素则可以具有和边界相同的颜色值。程序从（x，y）开始，先检测该点的颜色，如果它与边界色和填充色均不相同，就用填充色填充该点，然后检测相邻位置，以确定它们是否边界色和填充色，若不是，就填充该相邻点。这个过程延续到已经检测完边界范围内的所有像素为止。 扫描线种子填充算法原理简述：当给定种子点(x, y)时，首先分别向左和向右两个方向填充种子点所在扫描线上的位于给定区域的一个区段，同时记下这个 区段的范围[xLeft, xRight]，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。 扫描线种子填充算法可由下列四个步骤实现： (1)初始化一个空的栈用于存放种子点，将种子点(x, y)入栈； (2)判断栈是否为空，如果栈为空则结束算法，否则取出栈顶元素作为当前扫描线的种子点(x, y)，y是当前的扫描线； (3)从种子点(x, y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xLeft和xRight； (4) 分别检查与当前扫描线相邻的y - 1和y + 1两条扫描线在区间[xLeft, xRight]中的像素，从xLeft开始向xRight方向搜索，若存在非边界且未填充的像素点，则找出这些相邻的像素点中最右边的一个，并将其作为种子点压入栈中，然后返回第（2）步； 区域图案填充算法：以上介绍的区域填充算法，都是把区域内部的像素全部置成同一种颜色。但在实际应用中，有时需要用图案来填充平面区域。在确定了区域内点后，不是马上对像素填色，而是先将该像素映射到图案位图的对应位置。根据图案上对应位置的像素值，决定填充颜色。一般来说，图案比填充区域要小得多。所以图案总是成周期性的，使之能通过重复使用，构成任意尺寸的图案。 图案填充方式分为透明方式和不透明方式。透明方式：当图案位图的对应位置为1时，用前景色写像素，否则，不改变该像素的值。不透明方式：则图案位图的对应位置为1时，用前景色写像素，否则，用背景色写像素。 本实验实现在绝对定位法下用不透明方式对平面区域填充图案： 1.假设填充图案是一个M*N的位图，用M*N的数组存放； 2.当确定了区域内点p(x,y)后，则图案位图上的对应位置为p’(x%M,y%N)，其中%为c语言整除取余运算符，然后取出图案位图该位置的像素进行填充。 计算机图形学实验报告实验三二维图形的区域填充 一．实验目的： 1．理解二维图形区域填充的含义。 2．理解有序边表算法的基本思想。 3．理解边填充算法的基本思想。 4．掌握种子填充算法的原理及实现。 5．掌握你所使用的开发环境的填充函数及相关函数。 2．实验内容： 1.实现种子填充算法，并测试你的算法，用它填充一个圆域和一个多边形域。 2.（tc下）测试getpixel、floodfill、setfillstyle函数。（其它环境选择相应函数） 2．（选做）实现有序边表填充算法。 3．（选做）实现边填充算法。 三．实验报告 1. 问题描述：采用种子填充算法填充圆 2. 程序清单： #include "graphics.h" #include "conio.h" void YING(int x,int y,int oldcolor,int newcolor); void main() { int gdriver=DETECT,gmode; initgraph(&gdriver,&gmode,"C:\\TC30\\BGI"); setbkcolor(LIGHTBLUE); setcolor(RED); circle(100,100,20); YING(100,100,BLACK,RED); getch(); closegraph(); } void YING(int x,int y,int oldcolor,int newcolor) { if(getpixel(x,y)==oldcolor) { putpixel(x,y,newcolor); getch(); YING(x,y+1,oldcolor,newcolor); YING(x,y-1,oldcolor,newcolor); YING(x-1,y,oldcolor,newcolor); YING(x+1,y,oldcolor,newcolor); } } 实验四区域填充算法的实现 一、实验目的和要求： 1、掌握区域填充算法基本知识 2、理解区域的表示和类型，能正确区分四连通和八连通的区域 3、了解区域填充的实现原理，利用Microsoft Visual C++ 6.0（及EasyX_2011版） 实现区域种子填充的递归算法。 二、实验内容： 1、编程完成区域填色 2、利用画线函数，在屏幕上定义一个封闭区域。 3、利用以下两种种子填充算法，填充上述步骤中定义的区域 (1)边界表示的四连通区域种子填充的实现 (2)内点表示的四连通区域种子填充的实现 4、将上述算法作部分改动应用于八连通区域，构成八连通区域种子填充算法， 并编程实现。 三、实验结果分析 1、以上各种算法相应代码及运行结果如下： 程序代码： #include 算法系列之十二：多边形区域填充算法－－递归种子填充算 法 平面区域填充算法是计算机图形学领域的一个很重要的算法，区域填充即给出一个区域的边界（也可以是没有边界，只是给出指定颜色），要求将边界范围内的所有象素单元都修改成指定的颜色（也可能是图案填充）。区域填充中最常用的是多边形填色，本文中我们就讨论几种多边形区域填充算法。一、种子填充算法（Seed Filling）如果要填充的区域是以图像元数据方式给出的，通常使用种子填充算法（Seed Filling）进行区域填充。种子填充算法需要给出图像数据的区域，以及区域内的一个点，这种算法比较适合人机交互方式进行的图像填充操作，不适合计算机自动处理和判断填色。根据对图像区域边界定义方式以及对点的颜色修改方式，种子填充又可细分为几类，比如注入填充算法（Flood Fill Algorithm）、边界填充算法（Boundary Fill Algorithm）以及为减少递归和压栈次数而改进的扫描线种子填充算法等等。所有种子填充算法的核心其实就是一个递归算法，都是从指定的种子点开始，向各个方向上搜索，逐个像素进行处理，直到遇到边界，各种种子填充算法只是在处理颜色和边界的方式上有所不同。在开始介绍种子填充算法之前，首先也介绍两个概念，就是“4-联通算法” 和“8-联通算法”。既然是搜索就涉及到搜索的方向问题，从区域内任意一点出发，如果只是通过上、下、左、右四个方向搜索到达区域内的任意像素，则用这种方法填充的区域就称为四连通域，这种填充方法就称为“4-联通算法”。如果从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下全部八个方向到达区域内的任意像素，则这种方法填充的区域就称为八连通域，这种填充方法就称为“8-联通算法”。如图1（a）所示，假设中心的蓝色点是当前处理的点，如果是“4-联通算法”，则只搜索处理周围蓝色标识的四个点，如果是“8-联通算法”则除了处理上、下、左、右四个蓝色标识的点，还搜索处理四个红色标识的点。两种搜索算法的填充效果分别如如图1（b）和图1（c）所示，假如都是从黄色点开始填充，则“4-联通算法”如图1（b）所示只搜索填充左下角的区域，而“8-联通算法”则如图1（c）所示，将左下角和右上角的区域都填充了。图（1）“4-联通”和“8-联通”填充效果并不能仅仅因为图1 的填充效果就认为“8-联通算法”一定比“4-联通算法”好，应该根据应用环境和实际的需求选择联通搜索方式，在很多情况下，只有“4-联通算法”才能得到正确的结果。1.1 注入填充算法（Flood Fill Algorithm）注入填充算法不特别强调区域的边界，它只是从指定位置开始，将所有联通区域内某种指定颜色的点都替换成另一种颜色，从而实现填 《计算机图形学》实验报告 (实验二：图形填充算法) 一、实验目的及要求 用两种方法做图形的填充算法！ 二、理论基础 1.边填充算法 对于每一条扫描线和每条多边形的交点（x1,y1），将该扫描线上的交点右方的 所有像素取补。 2.种子填充算法 利用栈来实现种子填充算法。种子像素入栈，当栈非空时重复执行如下步骤： 将栈顶像素出栈，将出栈像素置成多边形色，按左，上，右，下顺序检查与出 栈像素相邻的四个像素，若其中某个像素不再边界且未置成多边形，则把该像 素入栈！ 三、算法设计与分析 1、边填充算法 void CEdge_mark_fillView::OnDraw(CDC* pDC) { CEdge_mark_fillDoc* pDoc = GetDocument(); ASSERT_V ALID(pDoc); int d[500][500]={0};int inside;int x,y; Bresenham(80,101,100,400,d); Bresenham(100,300,290,400,d); Bresenham(292,400,382,50,d); Bresenham(380,50,202,150,d); Bresenham(200,150,82,101,d); for(y=0;y<500;y++) { inside=0; for(x=0;x<500;x++) { if(d[x][y]==1) if(d[x+1][y]!=1) { inside=!(inside); } if(inside!=0) pDC->SetPixel(x,y,12); } } }2、种子填充 int x=299,y=51; COLORREF oldcolor; COLORREF newcolor; oldcolor=RGB(256,256,256); newcolor=RGB(123,123,123); pDC->MoveTo (40,40); pDC->LineTo (80,40); 1.3扫描线种子填充算法 1.1和1.2节介绍的两种种子填充算法的优点是非常简单，缺点是使用了递归算法，这不但需要大量栈空间来存储相邻的点，而且效率不高。为了减少算法中的递归调用，节省栈空间的使用，人们提出了很多改进算法，其中一种就是扫描线种子填充算法。扫描线种子填充算法不再采用递归的方式处理“4-联通”和“8-联通”的相邻点，而是通过沿水平扫描线填充像素段，一段一段地来处理“4-联通”和“8-联通”的相邻点。这样算法处理过程中就只需要将每个水平像素段的起始点位置压入一个特殊的栈，而不需要象递归算法那样将当前位置周围尚未处理的所有相邻点都压入堆栈，从而可以节省堆栈空间。应该说，扫描线填充算法只是一种避免递归，提高效率的思想，前面提到的注入填充算法和边界填充算法都可以改进成扫描线填充算法，下面介绍的就是结合了边界填充算法的扫描线种子填充算法。 扫描线种子填充算法的基本过程如下：当给定种子点(x, y)时，首先分别向左和向右两个方向填充种子点所在扫描线上的位于给定区域的一个区段，同时记下这个区段的范围[xLeft, xRight]，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。 扫描线种子填充算法可由下列四个步骤实现： (1) 初始化一个空的栈用于存放种子点，将种子点(x, y)入栈； (2) 判断栈是否为空，如果栈为空则结束算法，否则取出栈顶元素作为当前扫描线的种子点(x, y)，y是当前的扫描线； (3) 从种子点(x, y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xLeft和xRight； (4) 分别检查与当前扫描线相邻的y - 1和y + 1两条扫描线在区间[xLeft, xRight]中的像素，从xLeft开始向xRight方向搜索，若存在非边界且未填充的像素点，则找出这些相邻的像素点中最右边的一个，并将其作为种子点压入栈中，然后返回第（2）步； 这个算法中最关键的是第（4）步，就是从当前扫描线的上一条扫描线和下一条扫描线中寻找新的种子点。这里比较难理解的一点就是为什么只是检查新扫描线上区间[xLeft, xRight]中的像素？如果新扫描线的实际范围比这个区间大（而且 实验三区域填充算法的实现 班级 10信计2班学号姓名 一、实验目的和要求： 1、掌握区域填充算法基本知识 2、理解区域的表示和类型，能正确区分四连通和八连通的区域 3、了解区域填充的实现原理，利用Microsoft Visual C++ 6.0或win-TC实现区 域种子填充的递归算法。 二、实验内容： 1、编程完成区域填色 2、利用画线函数，在屏幕上定义一个封闭区域。 3、利用以下两种种子填充算法，填充上述步骤中定义的区域 (1)边界表示的四连通区域种子填充的实现 (2)内点表示的四连通区域种子填充的实现 4、将上述算法作部分改动应用于八连通区域，构成八连通区域种子填充算法， 并编程实现。 三、实验结果分析 四连通图的实现: 程序代码： #include 实验一种子填充算法 实验目的： 掌握种子填充算法的思想，掌握队列的使用，掌握基于队列的四连通区域填充算法。 实验内容： 对于任意给定的多边形，在屏幕上显示该多边形，根据给定的多边形区域内种子，对多边形区域进行填充。多边形区域为四连通区域，要求采用链队存储种子点。 实验原理： 种子填充算法采用的边界定义是区域边界上所有像素均具有某个特定的颜色值，区域内部所有像素均不取这一特定颜色，而边界外的像素则可以具有和边界相同的颜色值。程序从（x，y）开始，先检测该点的颜色，如果它与边界色和填充色均不相同，就用填充色填充该点，然后检测相邻位置，以确定它们是否边界色和填充色，若不是，就填充该相邻点。这个过程延续到已经检测完边界范围内的所有像素为止。 实验步骤： （1）队列结构定义 种子堆栈的结构和队列结构，并定义相应变量。 （2）确定多边形顶点坐标 在Initial函数中对顶点序列进行赋值。 （3）生成多边形 即将由顶点序列所定义的多边形显示出来，也就实现了多边形的边界定义。 （4）填充多边形区域 1）确定初始种子点 可以交互给出，例中直接给出。用指定的非填充颜色填充该像素，以标出初始种子点，同时将该点送入种子队列。 2）如果，种子队列非空，从队尾取出种子。 3）判断种子是否为边界色或填充色，如果不是填充该点，将该种子送入队列。 4）判断该点的四个相邻像素是否为边界色或填充色，如果不是，填充该像素，同时将该点送入种子队列。 5）重复步骤2），3），4） 实验效果： 程序实现： "SeedFillView.h" // SeedFillView.h : interface of the CSeedFillView class // ///////////////////////////////////////////////////////////////////////////// #if !defined(AFX_SEEDFILLVIEW_H__A4808C3F_AA5A_438B_93CD_5295DF06ABBD__IN CLUDED_) #define AFX_SEEDFILLVIEW_H__A4808C3F_AA5A_438B_93CD_5295DF06ABBD__INCLUDED_ #if _MSC_VER > 1000 #pragma once #endif // _MSC_VER > 1000 typedef struct QNode{POINT Data; struct QNode *next;}; //链表结构 typedef struct LinkQueue{QNode *front; QNode *rear; }; //队列结构 class CSeedFillView : public CView { protected: // create from serialization only CSeedFillView(); DECLARE_DYNCREATE(CSeedFillView) // Attributes public: CSeedFillDoc* GetDocument(); // Operations public: // Overrides // ClassWizard generated virtual function overrides //{{AFX_VIRTUAL(CSeedFillView) public: virtual void OnDraw(CDC* pDC); // overridden to draw this view virtual BOOL PreCreateWindow(CREATESTRUCT& cs); protected: virtual BOOL OnPreparePrinting(CPrintInfo* pInfo); virtual void OnBeginPrinting(CDC* pDC, CPrintInfo* pInfo); virtual void OnEndPrinting(CDC* pDC, CPrintInfo* pInfo); //}}AFX_VIRTUAL // Implementation 一、四向种子填充算法 void BoundaryFill4(int x, int y, COLORREF fillClr, COLORREF edgeClr, CDC *pDC) { COLORREF cPixel; cPixel=pDC->GetPixel(x, y); if((cPixel !=edgeClr)&&(cPixel !=fillClr)) { pDC->SetPixel(x,y,fillClr); Sleep(0); BoundaryFill4( x, y+1, fillClr,edgeClr,pDC); BoundaryFill4( x, y-1, fillClr,edgeClr,pDC); BoundaryFill4( x-1, y, fillClr,edgeClr,pDC); BoundaryFill4( x+1, y, fillClr,edgeClr,pDC); } } 二、八向种子填充算法 void Scanline_seed_fill(CDC *pDC, int seedx, int seedy, COLORREF color, COLORREF fillcolor) { COLORREF clr; int x,y,x0,y0,xl,xr,flag,xnextspan; iStack=0; x=seedx; y=seedy; y0=y; push(x,y); color=pDC->SetPixel(x,y,color); while(iStack >0) { pop(x,y); clr=pDC->SetPixel(x,y,fillcolor); x0=x+1; while(pDC->GetPixel(x0,y) !=color) { pDC->SetPixelV(x0,y,fillcolor); x0++; } xr=x0-1; // 最右像素 x0=x-1; while(pDC->GetPixel(x0,y) !=color) {多边形区域填充算法
图形学种子填充算法
计算机图形学 区域填充算法的实现
区域填充种子算法实现
扫描线种子填充算法
计算机图形学-区域填充的扫描线算法
计算机图形学实验报告8-种子点填充
实验2：多边形区域扫描线填充或种子填充
计算机图形学区域填充算法的实现
种子填充算法
计算机图形学圆的填充
区域填充算法的实现
算法系列之十二：多边形区域填充算法--递归种子填充算法
实验二：图形填充算法实验报告
扫描种子填充算法
计算机图形学实验 区域填充算法的实现
实验一 种子填充算法
一、四向种子填充算法.doc
相关主题
文本预览