计算机图形学扫描线种子填充算法

《计算机图形学实验》报告2016年春季学期实验四:种子点填充算法Seed Filling实验时间：2016年9月底实验地点：实验目的：掌握使用opengl 的种子点填充算法，观察改变参数对生成图形的改变(改变点的位置、颜色等)如果要填充的区域是以图像元数据方式给出的，通常使用种子填充算法进行区域填充。

种子填充算法的核心是一个递归算法，都是从指定的种子点开始，向各个方向上搜索，逐个像素进行处理，直到遇到边界。

种子填充算法常用四连通域和八连通域技术进行填充操作。

从区域内任意一点出发，通过上、下、左、右四个方向到达区域内的任意像素。

用这种方法填充的区域就称为四连通域；这种填充方法称为四向连通算法。

从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下八个方向到达区域内的任意像素。

用这种方法填充的区域就称为八连通域；这种填充方法称为八向连通算法。

算法的优点是非常简单，缺点是需要大量栈空间来存储相邻的点。

程序代码：使用的运行环境是vc++6.0#include <glut.h>#include <fstream>typedef float Color[3];//获取像素点的颜色void getpixel(GLint x, GLint y, Color color) {glReadPixels(x, y, 1, 1, GL_RGB, GL_FLOAT, color); //OPENGL自带}//画点函数void setpixel(GLint x, GLint y) {glBegin(GL_POINTS);glVertex2f(x, y);glEnd();}//比较颜色是否相等int compareColor(Color color1, Color color2) {if (color1[0] != color2[0] || color1[1] != color2[1] || color1[2] != color2[2]) { return 0; }else { return 1; }}void boundaryFill4(int x, int y, Color fillColor, Color boarderColor) {Color interiorColor;getpixel(x, y, interiorColor);if (compareColor(interiorColor, fillColor) == 0 && compareColor(interiorColor, boarderColor) == 0) { setpixel(x, y);boundaryFill4(x + 1, y, fillColor, boarderColor);boundaryFill4(x - 1, y, fillColor, boarderColor);boundaryFill4(x, y + 1, fillColor, boarderColor);boundaryFill4(x, y - 1, fillColor, boarderColor);}}void boundaryFill8(int x, int y, Color fillColor, Color boarderColor) {Color interiorColor, a, b, c, d;getpixel(x, y, interiorColor);getpixel(x + 1, y, a);getpixel(x, y - 1, b);getpixel(x, y + 1, c);getpixel(x - 1, y, d);int i = 0;if (compareColor(a, boarderColor) == 1) i++;if (compareColor(b, boarderColor) == 1) i++;if (compareColor(c, boarderColor) == 1) i++;if (compareColor(d, boarderColor) == 1) i++;if (i <= 1) {if (compareColor(interiorColor, fillColor) == 0 && compareColor(interiorColor, boarderColor) == 0) {setpixel(x, y);boundaryFill8(x+1,y,fillColor,boarderColor);boundaryFill8(x-1,y,fillColor,boarderColor);boundaryFill8(x,y+1,fillColor,boarderColor);boundaryFill8(x,y-1,fillColor,boarderColor);boundaryFill8(x-1,y+1,fillColor,boarderColor);boundaryFill8(x-1,y-1,fillColor,boarderColor);boundaryFill8(x+1,y+1,fillColor,boarderColor);boundaryFill8(x+1,y-1,fillColor,boarderColor);}}}void polygon() {glBegin(GL_LINE_LOOP);glLineWidth(5);//此处修改坐标，绘制多边形glVertex2f(100, 150);glVertex2f(150, 200);glVertex2f(200, 200);glVertex2f(200, 160);glEnd();}void display(void) {Color fillColor = {0.0, 1.0, 1.0};//填充颜色Color boarderColor = {0.0, 1.0, 0.0};//边界颜色glClear(GL_COLOR_BUFFER_BIT);glViewport(0, 0, 500, 500);glColor3fv(boarderColor);polygon();glColor3fv(fillColor);//boundaryFill4(150, 150, fillColor, boarderColor);//设置起点坐标及颜色boundaryFill8(120, 160, fillColor, boarderColor);glFlush();}int main(int argc, char **argv) {glutInit(&argc, argv);glutInitDisplayMode(GLUT_SINGLE | GLUT_RED);glutInitWindowSize(500, 500);glutInitWindowPosition(100, 100);glutCreateWindow("BoundaryFill1");glClearColor(1, 1, 1, 0.0);glMatrixMode(GL_PROJECTION);//投影模型gluOrtho2D(0.0, 500.0, 0.0, 500.0);glutDisplayFunc(display);glutMainLoop();return 0;}实验结果：（更改颜色）（更改形状）。

实验2：多边形区域扫描线填充或种子填充计科102 蓝广森 1007300441一、实验目的通过实验，进一步理解和掌握几种常用多边形填充算法的基本原理掌握多边形区域填充算法的基本过程掌握在C/C++环境下用多边形填充算法编程实现指定多边形的填充。

二、实验内容及要求实现多边形区域扫描线填充的有序边表算法，并将实现的算法应用于任意多边形的填充，要求多边形的顶点由键盘输入或鼠标拾取，填充要准确，不能多填也不能少填。

要求掌握边形区域扫描线填充的有序边表算法的基本原理和算法设计，画出算法实现的程序流程图，使用C或者VC++实现算法，并演示。

三、实验原理种子填充算法又称为边界填充算法。

其基本思想是：从多边形区域的一个内点开始，由内向外用给定的颜色画点直到边界为止。

如果边界是以一种颜色指定的，则种子填充算法可逐个像素地处理直到遇到边界颜色为止。

种子填充算法常用四连通域和八连通域技术进行填充操作。

四向连通填充算法：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上、下相邻的两条扫描线上的象素。

多边形扫描线填充算法技巧扫描线填充算法是计算机图形学中常用的一种填充算法，用于对多边形进行填充。

其基本原理是通过扫描线与多边形边界的交点来确定需要填充的像素点。

本文将介绍多边形扫描线填充算法的基本思想以及一些常用的优化技巧。

一、基本思想多边形扫描线填充算法的基本思想是将多边形分解成一系列水平线段，然后对每条水平线段进行扫描，找出与多边形边界相交的点，并进行填充。

具体步骤如下：1. 确定多边形的边界：对于给定的多边形，首先需要确定其边界。

可以使用边界表（edge table）来存储多边形的边界信息，包括每条边的起点和终点坐标以及斜率等。

2. 初始化扫描线：从多边形边界中找出最小的y坐标和最大的y坐标，作为扫描线的起点和终点。

3. 扫描线算法：对于每条扫描线，通过遍历边界表，找出与扫描线相交的边界线段。

根据相交点的x坐标，确定需要填充的像素点范围。

4. 填充像素点：根据上一步确定的像素点范围，将扫描线上的像素点进行填充。

二、技巧和优化1. 边界表的构建：为了提高算法的效率，可以对边界表进行排序，按照扫描线的y坐标来排序。

这样可以减少对边界表的遍历次数，提高算法的执行速度。

2. 边界交点的计算：在扫描线算法中，需要计算扫描线与多边形边界的交点。

可以使用活性边表（active edge table）来存储当前与扫描线相交的边界线段，并根据交点的x坐标进行排序。

这样可以减少计算交点的次数，提高算法的效率。

3. 填充像素点的优化：在填充像素点时，可以使用扫描线种子填充算法来进行优化。

该算法通过选择合适的填充起点，在填充过程中自动推进扫描线，减少不必要的计算和填充操作，提高填充的速度。

4. 填充规则的处理：在实际应用中，可能会遇到一些特殊情况，如多边形内部有孔洞或交叉等。

针对这些情况，可以通过修改填充规则来处理。

常用的填充规则有奇偶填充规则和非零填充规则，可以根据实际情况选择合适的填充规则。

5. 像素点颜色的处理：在多边形填充过程中，可以通过设置填充的颜色或纹理来实现不同的效果。

《计算机图形学》实验报告(实验二：图形填充算法)一、实验目的及要求用两种方法做图形的填充算法！二、理论基础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);pDC->LineTo (70,80);pDC->LineTo (40,40);FloodFill(51,51,RGB(255,255,255),RGB(0,0,255));pDC->LineTo (40,40);void CMyView::FloodFill(int x,int y,COLORREF oldcolor,COLORREF newcolor) {CDC* pDC;pDC=GetDC();if(pDC->GetPixel(x,y)==oldcolor){pDC->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);}四、程序调试及结果的分析1、2、四、实验心得及建议由于很多不会，所以这次没能按时当堂完成，下来花了不少时间才弄出来，第二种尤其比较麻烦，在同学的帮助下才做出来了。

填充（Fill）相关知识点填充（Fill）是一种常见的计算机图形学技术，用于在图像或物体的内部或边界区域中填充颜色或纹理。

填充技术在许多领域中被广泛应用，如图像处理、计算机辅助设计（CAD）和计算机游戏开发等。

本文将介绍填充相关的知识点，从基本原理到常见算法，让读者对填充技术有一个全面的了解。

基本原理填充技术的基本原理是通过某种规则或算法，在给定的区域内部或边界上填充颜色或纹理。

这个区域可以是一个简单的几何形状，如矩形或圆形，也可以是一个复杂的多边形。

填充通常从区域内部的某个点开始，按照一定的规则或算法进行扩散，直到填充满整个区域。

基本算法以下是一些常见的填充算法：扫描线填充算法扫描线填充算法是一种基于扫描线的填充方法。

它通过将扫描线与区域的边界进行比较，确定扫描线与区域的交点，并根据规则填充扫描线上的像素。

该算法的优点是简单易懂，并且适用于任意形状的区域。

边界填充算法边界填充算法是一种基于区域边界的填充方法。

它通过检测区域的边界像素，并根据规则填充区域内部的像素。

该算法的优点是填充效果清晰，但对于复杂的区域边界可能会存在一些问题。

种子填充算法种子填充算法是一种基于种子点的填充方法。

它通过选择一个种子点作为起始点，并按照一定的规则或算法进行扩散填充。

种子填充算法适用于复杂的区域填充，但可能存在堆栈溢出的问题。

填充的应用领域填充技术在许多领域中都有广泛的应用，以下是其中一些常见的应用领域：图像处理在图像处理中，填充技术可以用于图像的增强、修复和合成等方面。

例如，可以使用填充技术修复图像中的缺陷、填充图像的边界以及合成多个图像。

计算机辅助设计（CAD）在计算机辅助设计中，填充技术可以用于填充图形对象的内部或边界，以增加图形的真实感和细节。

例如，可以使用填充技术填充建筑物的内部、道路的纹理以及地形的颜色。

计算机游戏开发在计算机游戏开发中，填充技术可以用于填充游戏场景的地形、角色的纹理以及特效的颜色。

通过使用填充技术，可以使游戏画面更加精美和逼真。

扫描线种子填充算法扫描线种子填充算法的基本过程如下：当给定种子点(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]大，但是仍然得到了正确的填充。

计算机图形学——区域填充算法（基本光栅图形算法）⼀、区域填充概念区域：指已经表⽰成点阵形式的填充图形，是象素的集合。

区域填充：将区域内的⼀点（常称【种⼦点】）赋予给定颜⾊，然后将这种颜⾊扩展到整个区域内的过程。

区域填充算法要求区域是连通的，因为只有在连通区域中，才可能将种⼦点的颜⾊扩展到区域内的其它点。

1、区域有两种表⽰形式1）内点表⽰：枚举出区域内部的所有象素，内部所有象素着同⼀个颜⾊，边界像素着与内部象素不同的颜⾊。

2）边界表⽰：枚举出区域外部的所有象素，边界上的所有象素着同⼀个颜⾊，内部像素着与边界象素不同的颜⾊。

21）四向连通区域：从区域上⼀点出发可通过【上、下、左、右】四个⽅向移动的组合，在不越出区域的前提下，到达区域内的任意象素。

2）⼋向连通区域：从区域上⼀点出发可通过【上、下、左、右、左上、右上、左下、右下】⼋个⽅向移动的组合，在不越出区域的前提下，到达区域内的任意象素。

⼆、简单种⼦填充算法给定区域G⼀种⼦点（x, y）,⾸先判断该点是否是区域内的⼀点，如果是，则将该点填充为新的颜⾊，然后将该点周围的四个点（四连通）或⼋个点（⼋连通）作为新的种⼦点进⾏同样的处理，通过这种扩散完成对整个区域的填充。

这⾥给出⼀个四连通的种⼦填充算法（区域填充递归算法），使⽤【栈结构】来实现原理算法原理如下：种⼦像素⼊栈，当【栈⾮空】时重复如下三步：这⾥给出⼋连通的种⼦填充算法的代码：void flood_fill_8(int[] pixels, int x, int y, int old_color, int new_color){if(x<w&&x>0&&y<h&&y>0){if (pixels[y*w+x]==old_color){pixels[y*w+x]== new_color);flood_fill_8(pixels, x,y+1,old_color,new_color);flood_fill_8(pixels, x,y-1,old_color,new_color);flood_fill_8(pixels, x-1,y,old_color,new_color);flood_fill_8(pixels, x+1,y,old_color,new_color);flood_fill_8(pixels, x+1,y+1,old_color,new_color);flood_fill_8(pixels, x+1,y-1,old_color,new_color);flood_fill_8(pixels, x-1,y+1,old_color,new_color);flood_fill_8(pixels, x-1,y-1,old_color,new_color);}}}简单种⼦填充算法的不⾜a)有些像素会多次⼊栈，降低算法效率，栈结构占空间b)递归执⾏，算法简单，但效率不⾼，区域内每⼀像素都要进/出栈，费时费内存c)改进算法，减少递归次数，提⾼效率三、扫描线种⼦填充算法基本思想从给定的种⼦点开始，填充当前扫描线上种⼦点所在的⼀区段，然后确定与这⼀段相邻的上下两条扫描线上位于区域内的区段（需要填充的区间），从这些区间上各取⼀个种⼦点依次把它们存起来，作为下次填充的种⼦点。

扫描线区域填充算法
扫描线区域填充算法，又称为"扫描线填涂算法"，它用于对平面中特定区域填充指定的颜色、灰度或纹理，是计算机图形学中常用的算法之一。

该算法的原理是：给定待填充的区域内的点的有限个边界，从某一顶点开始，以某一规则遍历所有的边界点，形成边界数组，接着顺次扫描边界数组，将包含在边界中的每个合理像素点标记成已填充状态，由此而达到填充区域的目的。

算法步骤如下：
（1）设置起始点A，判断是否存在右方向上有没有边界点，若有，则把下一个边界点B作为起始点；
（2）从起始点A 开始，以扫描线的形式一次扫描边界点，把有效的像素点标记为“已填充”；
（3）把已扫描的点加入边界数组，直到下一个边界点C，且C点不等于起始点A；
（4）重复步骤（2）和（3），直至再回到起始点A，完成一次区域填充；
（5）如果还有未填充的区域，则重复步骤（1）至（4），直至所有区域填充完成。

实际应用中，为了避免停滞，可以采用八方向搜索策略；此外，由于扫描线填充算法中填充空间的范围是由边界点定义的，因此，当边界未经处理的是孤立的点或直线时，将无法实现实际的填充效果。

填充算法实验报告实验报告：填充算法研究与实验1. 实验目的填充算法在计算机图形学中有着广泛的应用，并且对于计算机图形学的发展有着重要意义。

本次实验旨在通过对填充算法的研究与实验，了解填充算法的原理和应用，掌握填充算法的基本实现方法，实现简单的填充效果。

2. 实验背景填充算法是计算机图形学中的一种常用算法，用于将指定区域进行填充。

填充算法可以应用于图像的编辑、区域选择、图像渲染等方面。

常见的填充算法包括区域种子填充算法、扫描线填充算法等。

3. 实验内容本次实验主要研究和实现了区域种子填充算法和扫描线填充算法。

区域种子填充算法是指通过指定一个待填充的种子点，在其周围的区域进行填充。

扫描线填充算法是指通过扫描图像的每一行，在特定条件下对像素进行填充。

在实验中，我们首先实现了区域种子填充算法。

通过在待填充的区域中选择一个点作为种子点，然后从指定点出发，通过递归或栈的方式对相邻的像素进行着色，直到遇到与起始点像素颜色不同的像素为止，从而完成填充效果。

其次，我们实现了扫描线填充算法。

这种算法的核心是扫描图像的每一行，在每一行上找到待填充区域的边界并将其记录下来，然后根据边界的位置对每一个像素进行填充。

我们采用了活性边表和扫描线转换算法来实现扫描线填充算法。

4. 实验结果通过实验我们成功实现了区域种子填充算法和扫描线填充算法，在输入指定的区域和种子点后，程序能够快速地对指定区域进行填充，生成了良好的填充效果。

5. 实验分析区域种子填充算法是一种简单且直观的填充算法，但对于复杂区域的填充效果并不理想。

它的主要缺点是可能导致栈溢出或填充效果不均匀，因此在实际应用中不太常用。

相比之下，扫描线填充算法具有更好的填充效果和效率。

其使用了活性边表和扫描线转换算法，可以在进行每一行的扫描时快速地找到边界并进行填充。

但该算法无法很好地处理较复杂的几何形状，例如存在凹陷和自相交的区域。

6. 实验总结通过本次实验，我们深入学习了填充算法的基本原理和实现方法，并成功实现了区域种子填充算法和扫描线填充算法。

计算机图形学——区域填充的扫描线算法一．实验名称：区域填充的扫描线算法二．实验目的：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 <stdio.h>#include <conio.h>#include <graphics.h>#include <malloc.h>#define Stack_Size 100 //栈的大小常量//定义结构体,记录种子点typedef struct{int x;int y;}Seed;//定义顺序栈(种子点)typedef struct{Seed Point[Stack_Size];int top;}SeqStack;//初始化栈操作void InitStack(SeqStack *&S){S=(SeqStack *)malloc(sizeof(SeqStack));S->top=-1;}//种子点栈置空；void setstackempty (SeqStack *S){S->top==-1;}//种子点栈状态检测函数int isstackempty (SeqStack *S){if(S->top==-1)return true; //空栈返回trueelsereturn false; //非空栈返回false}//种子点入栈；int stackpush (SeqStack *&S,Seed point){if(S->top==Stack_Size-1)//栈已满，返回false return false;S->top++;//栈未满，栈顶元素加1S->Point[S->top]= point;return true;}//取栈顶元素；int stackpop (SeqStack *&S,Seed &point){if(S->top==-1)//栈为空，返回falsereturn false;point=S->Point[S->top];S->top --;//栈未空，top减1return true;}//画圆void CirclePoints (int xc, int yc, int x, int y, int Color) {putpixel (xc + x, yc + y, Color);putpixel (xc + x, yc - y, Color);putpixel (xc - x, yc + y, Color);putpixel (xc - x, yc - y, Color);putpixel (xc + y, yc + x, Color);putpixel (xc + y, yc - x, Color);putpixel (xc - y, yc + x, Color);putpixel (xc - y, yc - x, Color); }//中点画圆算法void MidpointCircle(int radius, int Color) {int x, y;float d;x=0;y=radius;d=5.0/4-radius;CirclePoints(250,250,x,y,Color);while(x<y){if (d<0){d+=x*2.0+3;}else{d+=(x-y)*2.0+5;y--;}x++;CirclePoints(250,250,x,y,Color);}}//四连通扫描线算法void ScanLineFill4(int x, int y, int oldcolor, int newcolor) {int xl, xr, i;bool SpanNeedFill;Seed pt;//种子点SeqStack *S;//定义顺序栈InitStack(S);//定义了栈之后必须把栈先初始化setstackempty(S);//种子点栈置空；pt.x = x;pt.y = y;stackpush (S,pt); // 种子点(x, y)入栈while (!isstackempty(S)){stackpop (S,pt);//取种子点y = pt.y;x = pt.x;while (getpixel (x,y)==oldcolor) {// 从种子点开始向右填充putpixel (x, y, newcolor);x++;}xr = x -1;x = pt.x -1;while (getpixel (x,y)==oldcolor) { // 从种子点开始向左填充putpixel (x, y, newcolor);x--;}xl = x + 1;x = xl;y = y +1; // 处理上面一条扫描线while (x < xr){SpanNeedFill = false;while (getpixel (x, y)==oldcolor){SpanNeedFill = true;x++ ;} // 待填充区段搜索完毕if (SpanNeedFill){// 将右端点作为种子点入栈pt.x = x - 1;pt.y = y;stackpush (S,pt);SpanNeedFill = false;} //继续向右检查以防遗漏while ((getpixel (x, y)!=oldcolor) && (x< xr)) x++;} //上一条扫描线上检查完毕x = xl;y=y-2; // 处理下面一条扫描线while (x < xr){SpanNeedFill = false;while (getpixel (x, y)==oldcolor){SpanNeedFill=true;x++ ;}if (SpanNeedFill){pt.x= x - 1;pt.y = y;stackpush (S,pt);SpanNeedFill=false;}while ((getpixel (x, y)!=oldcolor) && (x < xr))x++;}}}//主函数检测void main(){int radius,color;int x,y;//种子点int oldcolor,newcolor;//原色与填充色//输入参数值printf("input radius and color:\n");//画圆参数scanf("%d,%d",&radius,&color);printf("input x and y:\n"); //读入内点scanf("%d,%d", &x, &y);printf("input oldcolor and newcolor:\n"); //读入原色与填充色scanf("%d,%d", &oldcolor, &newcolor);int gdriver = DETECT,gmode;initgraph(&gdriver, &gmode, "c:\\tc");// 用背景色清空屏幕cleardevice();// 设置绘图色为红色setcolor(RED);MidpointCircle(radius,color);//用中点画圆算法画圆rectangle(150, 150, 350, 350);//再画一个矩形区域ScanLineFill4 (x,y,oldcolor,newcolor);//扫描线区域填充getch();closegraph();}五．运行结果与讨论：测试结果1：测试结果2：六．实验分析与讨论：1.通过借助栈这一数据结构，完成了区域填充的扫描线算法的实现，并利用以前所学的画圆等算法，进行综合运用，在此基础上进行扩充，设计多种图案，进行扫描线填充算法的检测，都得到了理想的结果，体现了算法的有效性；2.栈的数据结构给种子点的操作带来了极大的方便，为算法的实现提供了便利，同时还提高了算法的复用性和可靠性；3.此扫描线填充算法能够对多种图案进行填充，展现了算法的实用性。

扫描线区域填充算法算法步骤如下：1.首先需要定义一个边表（ET）和活动边表（AET）。

-边表是存储多边形所有边的一张表格，将每条边的y坐标、x坐标以及斜率存储起来。

-活动边表是指当前扫描线与多边形边的交点，它是一个按照x坐标排列的列表。

2.初始化边表（ET）和活动边表（AET）。

-通过遍历多边形的边，将边表中存储对应的边信息。

-初始时活动边表为空。

3.根据多边形的顶点，将边添加到边表中。

-对于每条边，计算出其斜率，以及y坐标的最小值和最大值。

4.进行扫描线填充：a.设置当前扫描线的y坐标，从最小的y值开始，逐行向下扫描。

b.遍历边表，将与当前扫描线相交的边添加到活动边表中。

c.按照x坐标对活动边表进行排序。

d.遍历活动边表，两两配对，填充对应的像素点。

e.过滤掉扫描线下方的边。

f.更新活动边表，将不再与当前扫描线相交的边从活动边表中删除。

5.重复步骤4，直到扫描完整个区域。

然而，扫描线区域填充算法也存在一些局限性和问题：-对于包含小尺寸多边形的大区域填充，算法的迭代次数会增加，导致填充时间变长。

-在多边形内有重叠区域时，算法无法区分内外部，可能导致填充错误。

-当多边形内有孔洞时，算法无法正确填充孔洞。

为了解决以上问题，可以采用一些优化策略来改进算法性能和填充效果。

例如，可以使用边表索引和活动边表的双向链表结构，减少查找和插入操作的时间开销。

此外，还可以使用扫描线的上下两根线段来同时填充两个相邻区域，提高填充速度。

总结起来，扫描线区域填充算法是一种常用且有效的图形填充算法，通过逐行扫描和交点判断来填充封闭区域。

它可以广泛应用于计算机图形学领域，如图形渲染、图像处理等。

算法在实际应用中需根据具体场景进行优化和改进，以满足不同需求。

扫描线填充种子填充算法（原创完整版）// 计算机图形学View.cpp : implementation of the CMyView class//// 种子填充和扫描线填充算法// Author:: codeants_for_sdau2012// Date::2014/10/24#include "stdafx.h"#include "计算机图形学.h"#include "计算机图形学Doc.h"#include "计算机图形学View.h"#include "DDA.h"#include "afxtempl.h"#include#include#include#include "debug1.h"#include "xyz_dialog.h"#ifdef _DEBUG#define new DEBUG_NEW#undef THIS_FILEstatic char THIS_FILE[] = __FILE__;#endifusing namespace std;/////////////////////////////////////////////////////////////////// //////////// CMyViewIMPLEMENT_DYNCREATE(CMyView, CView)BEGIN_MESSAGE_MAP(CMyView, CView)//{{AFX_MSG_MAP(CMyView)ON_COMMAND(ID_MENUITEM32771, OnDDA)ON_COMMAND(ID_MENUITEM32772, OnBrem)ON_COMMAND(ID_MENUITEM32773, OnSqureBrush)ON_COMMAND(ID_MENUITEM32774, Onseek1)ON_COMMAND(ID_MENUITEM32775, OnSeekin8)ON_COMMAND(ID_MENUITEM32776, OnAETLine)//}}AFX_MSG_MAP// Standard printing commandsON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint) ON_COMMAND(ID_FILE_PRINT_PREVIEW,CView::OnFilePrintPreview) END_MESSAGE_MAP()/////////////////////////////////////////////////////////////////// //////////// CMyView construction/destructionCMyView::CMyView(){// TODO: add construction code here}CMyView::~CMyView(){}BOOL CMyView::PreCreateWindow(CREATESTRUCT& cs){// TODO: Modify the Window class or styles here by modifying// the CREATESTRUCT csreturn CView::PreCreateWindow(cs);}/////////////////////////////////////////////////////////////////// //////////// CMyView drawingvoid CMyView::OnDraw(CDC* pDC){CMyDoc* pDoc = GetDocument();ASSERT_V ALID(pDoc);// TODO: add draw code for native data here}/////////////////////////////////////////////////////////////////// //////////// CMyView printingBOOL CMyView::OnPreparePrinting(CPrintInfo* pInfo){// default preparationreturn DoPreparePrinting(pInfo);}void CMyView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/) {// TODO: add extra initialization before printing}void CMyView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/) {// TODO: add cleanup after printing}/////////////////////////////////////////////////////////////////// //////////// CMyView diagnostics#ifdef _DEBUGvoid CMyView::AssertValid() constCView::AssertValid();}void CMyView::Dump(CDumpContext& dc) const{CView::Dump(dc);}CMyDoc* CMyView::GetDocument() // non-debug version is inline{ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CMyDo c)));return (CMyDoc*)m_pDocument;}#endif //_DEBUG/////////////////////////////////////////////////////////////////// //////////// CMyView message handlersvoid swap(int& xt,int& yt){int tmp=xt;xt=yt;yt=tmp;}void DDAxt(int x0,int y0,int x1,int y1,int color,CDC* pDC){int x;float dx,dy,k;dx=x1-x0;dy=y1-y0;if(dx==0)if(y1<y0)< bdsfid="172" p=""></y0)<>swap(y1,y0);for(int y=y0;y<y1;y++)< bdsfid="175" p=""></y1;y++)<> {pDC->SetPixel(x1,y,color);}return;}k=dy/dx; double y=y0;if(x0>x1){swap(x0,x1);swap(y0,y1);}for(x=x0;x<=x1;x++){pDC->SetPixel(x,int (y+0.5), color);y=y+k;}}int x0,y0,x1,y1;void CMyView::OnDDA(){DDA s1;//debug1 d1;s1.DoModal();//Invalidate();//UpdateData(true);x0=s1.m_x0;y0=s1.m_y0;x1=s1.m_x1;y1=s1.m_y1;//UpdateData(false);//s1.EndDialog(3);CDC* pDC;pDC=GetDC();CMyDoc* pDoc = GetDocument();ASSERT_V ALID(pDoc);DDAxt(x0,y0,x1,y1,RGB(255,0,255),pDC);}void Brem(int x0,int y0,int x1,int y1,int color,CDC* pDC) { double xt,yt,k,b;double dx,dy,d0,dt1,dt2;if(x0>x1){swap(x0,x1);swap(y0,y1);}dx=x1-x0,dy=y1-y0;if(x1==x0){if(y1<y0)< bdsfid="225" p=""></y0)<>swap(y1,y0);for(int y=y0;y<y1;y++)< bdsfid="228" p=""></y1;y++)<> {pDC->SetPixel(x1,y,color);}return;}k=(y1-y0)/(x1-x0);b=(x1*y0-x0*y1)/(x1-x0);if(k<=1&&k>=0){d0=dx-2*dy;dt1=2*dx-2*dy;dt2=-2*dy;int y=y0;for(int x=x0;x<=x1;x++){if(d0<0){y++;d0+=dt1;}else d0+=dt2;pDC->SetPixel(x,y,color);}}else if(k>1){if(y1<y0)< bdsfid="256" p=""></y0)<> {swap(x1,x0);swap(y1,y0);dx=-dx;dy=-dy;}d0=dx-2*dy;dt1=2*dy-2*dx;dt2=-2*dx;int x=x0;for(int y=y0;y<=y1;y++){if(d0<0){x++;d0+=dt1;}else d0+=dt2;pDC->SetPixel(x,y,color);}}else if(k<0&&k>=-1){if(x1<x0)< bdsfid="281" p=""></x0)<> {swap(x1,x0);swap(y1,y0);dx=-dx;dy=-dy;}d0=-dx;dt1=-2*dx-2*dy;dt2=-2*dy;int y=y0;for(int x=x0;x<=x1;x++){if(d0>=0){y--;d0+=dt1;}else d0+=dt2;pDC->SetPixel(x,y,color);}}else if(k<-1){if(y1<y0)< bdsfid="306" p=""></y0)<> {swap(x1,x0);swap(y1,y0);dx=-dx;dy=-dy;}d0=-dy;dt1=-2*dy-2*dx;dt2=-2*dx;int x=x0;for(int y=y0;y<=y1;x++){if(d0>=0){x--;d0+=dt1;}else d0+=dt2;pDC->SetPixel(x,y,color);}}}void CMyView::OnBrem(){DDA s1;//debug1 d1;s1.DoModal();//Invalidate();//UpdateData(true);x0=s1.m_x0;y0=s1.m_y0;x1=s1.m_x1;y1=s1.m_y1;//UpdateData(false);//s1.EndDialog(3);CDC* pDC;pDC=GetDC();CMyDoc* pDoc = GetDocument();ASSERT_V ALID(pDoc);Brem(x0,y0,x1,y1,RGB(255,0,255),pDC);}void squr(int x0,int y0,int x1,int y1,int color,CDC* pDC) { pDC->SetPixel(x0,y0,color);pDC->SetPixel(x0+1,y0,color);pDC->SetPixel(x0+1,y0+1,color);pDC->SetPixel(x0+1,y0-1,color);pDC->SetPixel(x0,y0+1,color);pDC->SetPixel(x0,y0-1,color);pDC->SetPixel(x0-1,y0,color);pDC->SetPixel(x0-1,y0+1,color);pDC->SetPixel(x0-1,y0-1,color);pDC->SetPixel(x1,y1,color);pDC->SetPixel(x1+1,y1,color);pDC->SetPixel(x1+1,y1+1,color);pDC->SetPixel(x1+1,y1-1,color);pDC->SetPixel(x1,y1+1,color);pDC->SetPixel(x1,y1-1,color);pDC->SetPixel(x1-1,y1,color);pDC->SetPixel(x1-1,y1+1,color);pDC->SetPixel(x1-1,y1-1,color);}void CMyView::OnSqureBrush(){DDA s1;s1.DoModal();//Invalidate();//UpdateData(true);x0=s1.m_x0;y0=s1.m_y0;x1=s1.m_x1;y1=s1.m_y1;//UpdateData(false);//s1.EndDialog(3);CDC* pDC;pDC=GetDC();CMyDoc* pDoc = GetDocument(); ASSERT_V ALID(pDoc);Brem(x0,y0,x1,y1,RGB(255,0,255),pDC); Brem(x0,y0,101,1001,RGB(255,0,255),pDC); //squr(x0,y0,x1,y1,RGB(255,0,255),pDC);}void seekIn(int x,int y,int color,CDC* pDC)//4方向的填充{ CArray my1;//CArray *first,*rear;my1.Add(CPoint(x,y));pDC->SetPixel(x,y,color);//first=&my1.ElementAt(0);//int first=0,rear=1;while(my1.GetSize()!=0){CPoint p=my1.GetAt(0);my1.RemoveAt(0);CPoint tmp=CPoint(p.x+1,p.y);if(pDC->GetPixel(tmp)!=color){pDC->SetPixel(p.x+1,p.y,color);my1.Add(tmp);}tmp=CPoint(p.x-1,p.y);if(pDC->GetPixel(tmp)!=color){pDC->SetPixel(p.x-1,p.y,color);my1.Add(tmp);}tmp=CPoint(p.x,p.y+1);if(pDC->GetPixel(tmp)!=color){pDC->SetPixel(p.x,p.y+1,color);my1.Add(tmp);}tmp=CPoint(p.x,p.y-1);if(pDC->GetPixel(tmp)!=color){pDC->SetPixel(p.x,p.y-1,color);my1.Add(tmp);}}}void seekIn8(int x,int y,int color,CDC* pDC)//8方向的填充{ CArray my1;//CArray *first,*rear;my1.Add(CPoint(x,y));pDC->SetPixel(x,y,color);//first=&my1.ElementAt(0);//int first=0,rear=1;while(my1.GetSize()!=0){CPoint p=my1.GetAt(0);my1.RemoveAt(0);CPoint tmp=CPoint(p.x+1,p.y);if(pDC->GetPixel(tmp)!=color){pDC->SetPixel(p.x+1,p.y,color);my1.Add(tmp);}tmp=CPoint(p.x-1,p.y);if(pDC->GetPixel(tmp)!=color){pDC->SetPixel(p.x-1,p.y,color);my1.Add(tmp);tmp=CPoint(p.x,p.y+1);if(pDC->GetPixel(tmp)!=color) {pDC->SetPixel(p.x,p.y+1,color); my1.Add(tmp);}tmp=CPoint(p.x,p.y-1);if(pDC->GetPixel(tmp)!=color) {pDC->SetPixel(p.x,p.y-1,color); my1.Add(tmp);}tmp=CPoint(p.x+1,p.y+1);if(pDC->GetPixel(tmp)!=color) {pDC->SetPixel(p.x+1,p.y+1,color); my1.Add(tmp);}tmp=CPoint(p.x-1,p.y+1);if(pDC->GetPixel(tmp)!=color) {pDC->SetPixel(p.x-1,p.y+1,color); my1.Add(tmp);}tmp=CPoint(p.x-1,p.y-1);if(pDC->GetPixel(tmp)!=color) {pDC->SetPixel(p.x-1,p.y-1,color); my1.Add(tmp);tmp=CPoint(p.x+1,p.y-1);if(pDC->GetPixel(tmp)!=color){pDC->SetPixel(p.x+1,p.y-1,color);my1.Add(tmp);}}}void CMyView::Onseek1()//四方向的种子填充算法{ CDC* pDC;pDC=GetDC();CMyDoc* pDoc = GetDocument();ASSERT_V ALID(pDoc);CPoint p[4];p[0]=CPoint(20,40);p[1]=CPoint(20,400);p[2]=CPoint(200,400);p[3]=CPoint(200,40);int color=RGB(255,0,255);pDC->MoveTo(p[0]);for(int i=1;i<=3;i++){pDC->LineT o(p[i]);}pDC->LineT o(p[0]);color=pDC->GetPixel(p[1]);seekIn(110,220,color,pDC);}void CMyView::OnSeekin8() //8方向的种子填充算法{CDC* pDC;pDC=GetDC();CMyDoc* pDoc = GetDocument(); ASSERT_V ALID(pDoc);CPoint p[4];p[0]=CPoint(320,40);p[1]=CPoint(320,400);p[2]=CPoint(500,400);p[3]=CPoint(500,40);int color=RGB(255,0,255);pDC->MoveTo(p[0]);for(int i=1;i<=3;i++){pDC->LineT o(p[i]);}pDC->LineT o(p[0]);color=pDC->GetPixel(p[1]);seekIn8(410,220,color,pDC);}//扫描线填充struct edge//edge信息{double xi;double dx;int ymax;bool operator <(edge& S)const{return xi<s.xi;< bdsfid="539" p=""></s.xi;<> }};void initLineNewedge(vector< list >& ve,vector& py,int ymin,int ymax)//初始化边参数{edge e;int sz=py.size();for(int i=0;i<sz;i++)< bdsfid="549" p=""></sz;i++)<>{CPoint& ps=py[i];CPoint& pe=py[(i+1)%sz];CPoint& pee=py[(i+2)%sz];CPoint& pss=py[(i-1+sz)%sz];if(pe.y!=ps.y){e.dx=(double)(pe.x-ps.x)/(double)(pe.y-ps.y);if(pe.y>ps.y){e.xi=ps.x;if(pee.y>=pe.y) e.ymax=pe.y-1;else e.ymax=pe.y;ve[ps.y-ymin].push_front(e);}else{e.xi=pe.x;if(pss.y>=ps.y) e.ymax=ps.y-1;else e.ymax=ps.y;ve[pe.y-ymin].push_front(e);}}}void insertNetListT oAet(list& st,list& aet)//插入活动边{for(list::iterator it=st.begin();it!=st.end();it++)aet.push_front((*it));}void fillScannLine(list& st,int y,int color,CDC* pDC)//填充{CPen pen;pen.CreatePen(PS_SOLID,2,RGB(255,0,255));CPen* pOldPen=pDC->SelectObject(&pen);int sz=st.size();for(list::iterator it=st.begin();it!=st.end();++it){pDC->MoveTo(CPoint((*it).xi,y));++it;pDC->LineT o(CPoint((*it).xi,y));}pDC->SelectObject(pOldPen);}void RemoveNonActiveLine(list& st,int y)//删除非活动边{for(list::iterator it=st.begin();it!=st.end();){if((*it).ymax==y)it=st.erase(it);else it++;}}void UpdateAetEdgeInfo(edge& e)e.xi += e.dx;}void updateAndResortAet(list& st)//更新活动边和对活动边进行排序{for(list::iterator it=st.begin();it!=st.end();it++){(*it).xi+=(*it).dx;}st.sort();}void hzLine(vector& py,CDC* pDC){int sz=py.size();CPen newpen;newpen.CreatePen(PS_SOLID,1,RGB(255,0,255));CPen* pOldPen=pDC->SelectObject(&newpen);for(int i=1;i<sz;i++)< bdsfid="631" p=""></sz;i++)<>{if(py[i].y==py[i-1].y){pDC->MoveTo(CPoint(py[i-1].x,py[i-1].y));pDC->LineT o(CPoint(py[i].x,py[i].y));}}if(py[sz-1].y==py[0].y){pDC->MoveTo(CPoint(py[0].x,py[0].y));pDC->LineT o(CPoint(py[sz-1].x,py[sz-1].y));}pDC->SelectObject(pOldPen);}void CMyView::OnAETLine(){vector py;py.clear();int ymax=-1000001,ymin=1000001;/*xyz_dialog xz[6];for(int i=0;i<6;i++){xz[i].DoModal();UpdateData(true);if(ymaxelse if(ymin>xz[i].m_y) ymin=xz[i].m_y; py.push_back(CPoint(xz[i].m_x,xz[i].m_y)); UpdateData(false);}*/CPoint p[6];p[0]=CPoint(200,40);p[1]=CPoint(200,300);p[2]=CPoint(350,170);p[3]=CPoint(400,170);p[4]=CPoint(500,300);p[5]=CPoint(500,40);ymin=40;ymax=300;for(int i=0;i<6;i++){py.push_back(p[i]);}vector< list > ve(ymax-ymin+1);CDC* pDC;pDC=GetDC();CMyDoc* pDoc = GetDocument(); ASSERT_V ALID(pDoc); initLineNewedge(ve,py,ymin,ymax); hzLine(py,pDC);list aet;int color=RGB(255,0,255);//AfxMessageBox("hello world!"); for(int y=ymin;y<=ymax;y++) {insertNetListToAet(ve[y-ymin],aet); fillScannLine(aet,y,color,pDC); RemoveNonActiveLine(aet,y); updateAndResortAet(aet);}}。