下载文档原格式
一、实验目标1.了解基于种子填充算法的基本思想；2.掌握基于种子填充算法的算法实现；3.掌握栈的使用。
二、实验内容本次实验主要是实现递归种子填充算法、简单种子填充算法、扫描线种子填充算法以及区域图案填充算法。
种子填充算法原理简述：在开始介绍种子填充算法之前，首先也介绍两个概念，就是“4-连通算法”和“8-连通算法”。
既然是搜索就涉及到搜索的方向问题，从区域内任意一点出发，如果只是通过上、下、左、右四个方向搜索到达区域内的任意像素，则用这种方法填充的区域就称为四连通域，这种填充方法就称为“4-连通算法”。
如果从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下全部八个方向到达区域内的任意像素，则这种方法填充的区域就称为八连通域，这种填充方法就称为“8-连通算法”。
种子填充算法采用的边界定义是区域边界上所有像素均具有某个特定的颜色值，区域内部所有像素均不取这一特定颜色，而边界外的像素则可以具有和边界相同的颜色值。
程序从（x，y）开始，先检测该点的颜色，如果它与边界色和填充色均不相同，就用填充色填充该点，然后检测相邻位置，以确定它们是否边界色和填充色，若不是，就填充该相邻点。
这个过程延续到已经检测完边界范围内的所有像素为止。
扫描线种子填充算法原理简述：当给定种子点(x, y)时，首先分别向左和向右两个方向填充种子点所在扫描线上的位于给定区域的一个区段，同时记下这个区段的范围[xLeft, xRight]，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。
反复这个过程，直到填充结束。
扫描线种子填充算法可由下列四个步骤实现：(1)初始化一个空的栈用于存放种子点，将种子点(x, y)入栈；(2)判断栈是否为空，如果栈为空则结束算法，否则取出栈顶元素作为当前扫描线的种子点(x, y)，y是当前的扫描线；(3)从种子点(x, y)出发，沿当前扫描线向左、右两个方向填充，直到边界。
《计算机图形学实验》报告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;}实验结果：（更改颜色）（更改形状）。
图形填充之种⼦填充算法编译器：VS2013算法：在图形内选择⼀个点为种⼦，然后对这个种⼦四⽅位坐标未着⾊的⼊栈，出栈便着⾊，如此重复，等到栈内为空，则着⾊完成代码：1 #include "stdafx.h"2 #include<stdio.h>3 #include"graphics.h"4 #include<stdlib.h>5 #include<stack>67using namespace std;89//定义结构体存储像素坐标10struct Point11 {12int x;13int y;14 };1516//函数声明17void Boundaryfilling(Point a[], int n);18void judgecolor(int x, int y, stack<int> &sx, stack<int> &sy);1920int main()21 {22int gdriver = DETECT, gmode, n, i;2324 printf("please input number of point:\n");25 scanf_s("%d", &n);2627 Point *p=(Point *)malloc(n*sizeof(Point)); //动态分配内存2829 printf("please input point :\n");30for (i = 0; i < n; i++)31 scanf_s("%d%d", &p[i].x, &p[i].y);3233 initgraph(&gdriver, &gmode, "");3435 setcolor(BLUE);36 setbkcolor(BLACK);3738//画出多边形39for (i = 0; i < n-1; i++)40 line(p[i].x, p[i].y, p[i + 1].x, p[i + 1].y);4142 Boundaryfilling(p, n);4344 system("pause");45 closegraph();4647return0;48 }4950void Boundaryfilling(Point a[], int n)51 {52 stack<int> sx,sy;53int x=0 , y=0 ,x0,y0,i;5455for (i = 0; i < n; i++)56 {57 x += a[i].x;58 y += a[i].y;59 }6061 x = x / (n-1);62 y = y / (n-1);6364 sx.push(x);//x坐标⼊栈65 sy.push(y);//y坐标⼊栈6667while (!sx.empty()) //判断栈是否为空68 {69 x0 = sx.top();70 y0 = sy.top();7172 putpixel(sx.top(), sy.top(), YELLOW); //栈顶元素着⾊73 sx.pop();//栈顶元素出栈74 sy.pop();//栈顶元素出栈7576 judgecolor(x0 - 1, y0, sx, sy);//左边点77 judgecolor(x0 + 1, y0, sx, sy);//右边点78 judgecolor(x0, y0 - 1, sx, sy);//下边点79 judgecolor(x0, y0 + 1, sx, sy);//上边点80 }81 }8283//判断该像素是否没有着⾊84void judgecolor(int x, int y,stack<int> &sx,stack<int> &sy) 85 {86if (getpixel(x, y) == BLACK)87 {88 sx.push(x);89 sy.push(y);90 }91 }结果：。
《计算机图形学》实验报告(实验二：图形填充算法)一、实验目的及要求用两种方法做图形的填充算法！二、理论基础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）在计算机辅助设计中，填充技术可以用于填充图形对象的内部或边界，以增加图形的真实感和细节。
例如，可以使用填充技术填充建筑物的内部、道路的纹理以及地形的颜色。
计算机游戏开发在计算机游戏开发中，填充技术可以用于填充游戏场景的地形、角色的纹理以及特效的颜色。
通过使用填充技术，可以使游戏画面更加精美和逼真。
种子填充算法
填充算法是随机化的有益的近似算法中的经典例子，用它来解决最大问题可以产生出理想的解决方案。
种子填充算法作为该算法的一种，经常被用来解决贪婪的最大化问题或者寻优，在有限的时间内求解传统最大化目标函数的最优解。
种子填充算法是一种常用的函数字符串优化技术，能以有限的步骤实现最大化随机化优化，在计算图形和调度任务中常用种子填充算法。
主要包括：
1.根据求解的问题，选择最优解种子。
种子是随机产生的群体或者求解器方程，用于准确确定最佳参数；
2.利用种子初始化函数字符串，以较小的步骤完成最大化优化，扩展函数字符串；
3.根据优化的状态和步骤，重新选择种子来改变最大化的结果；
4.重复多步优化，可以得到不同的最优解，对于优化准确率很高。
种子填充算法的优势在于准确地得到期望解，比其它采用搜索的近似解决办法更加精确，且由于经过多次记录，每次重播都能产生一样的最优解。
另外，由于每次迭代中用到种子，可以在不影响目标函数的性能情况下改变最终的优化结果。
种子填充算法目前在理论上和实际应用中都得到了广泛的使用，如求解细胞自动机的模拟、排列调度问题、视觉语义地图等，所有这些问题都是可行空间有限，而且受限于时间和空间，在这些情况下种子填充算法可以有效提高解决问题的效率。
![种子填充_计算机图形学教程（第3版）_[共2页]](https://uimg.taocdn.com/fef6ddcda8114431b80dd8d7.webp)
123 如果用软件实现，边填充算法与多边形区域填充算法的执行速度几乎是相同的。
但是，由于边填充算法最适合具有帧缓冲存储器的图形系统，在帧缓冲存储器中应用该算法时，不必建立和维护边表以及对它进行排序，所以边填充算法比较适合用硬件来实现，此时其执行速度必比多边形区域填充要快一个数量级以上。
4.4.3 种子填充以上讨论的多边形区域填充算法是按扫描线的顺序进行的，而种子填充算法采用的是不同的原理。
它的基本思路是：首先假设在多边形区域的内部，至少有一个像素点（称为种子）是已知的，然后算法开始搜索与种子点相邻且位于区域内的其他像素。
如果相邻点不在区域内，那么到达区域的边界；如果相邻点位于区域内，那么这一点就成为新的种子点，然后继续递归地搜索下去。
这种算法比较适用于光栅扫描设备。
区域的连通情况可以分为四连通和八连通两种。
四连通区域是指各像素在水平和垂直4个方向上是连通的，如图4.46（a ）所示。
八连通区域是指各像素在水平、垂直以及4个对角线方向上都是连通的，如图4.46（b ）所示。
在种子填充算法中，如果允许从4个方向搜寻下一个像素点，则该算法称为四向算法；如果允许从8个方向搜寻下一个像素点，则该算法称为八向算法。
一个八向算法可以用在四连通区域的填充上，也可用在八连通区域的填充上；而一个四向算法只能用于填充四连通区域。
无论是四向算法还是八向算法，它们的填充算法的基本思想是相同的。
为简单起见，下面只讨论四向种子填充算法。
1．简单种子填充算法这是对定义区域进行填充的算法，此算法所采用的基本方法是：将（x ，y ）点与边界值相比较，检测该点的像素是否处在区域之内；同时与新值相比，以确定该点是否已被访问过。
这种测试的前提条件是：在初始状态下，区域内没有一个像素已被设置为新值；同时允许新值等于边界值。
如果用堆栈的方法来实现简单种子填充算法，则算法的基本步骤如下。
（1）种子像素压入堆栈。
（2）当堆栈非空时，重复执行以下操作。
计算机图形学四连通区域种子填充算法实验————————————————————————————————作者: ————————————————————————————————日期:ﻩ《计算机图形学实验》报告任课教师:钱文华2０16年春季学期实验:四连通区域种子填充算法实验时间：201６年12月8日实验地点：信息学院22０4实验目的：掌握种子填充算法的原理，并会用种子填充算法和opｅｎｇl并结合使用ｃ+＋语言编写程序绘制多边形。
实验原理:种子填充算法又称为边界填充算法。
其基本思想是:从多边形区域的一个内点开始，由内向外用给定的颜色画点直到边界为止。
如果边界是以一种颜色指定的,则种子填充算法可逐个像素地处理直到遇到边界颜色为止。
内点的检测条件：ｉf(iｎｔerｉoｒCｏloｒ!=bo ｒｄerCoｌor&&interｉorColoｒ!＝ｆiｌlCｏlｏr）。
种子填充算法常用四连通域和八连通域技术进行填充操作。
从区域内任意一点出发，通过上、下、左、右四个方向到达区域内的任意像素。
用这种方法填充的区域就称为四连通域;这种填充方法称为四向连通算法。
从区域内任意一点出发,通过上、下、左、右、左上、左下、右上和右下八个方向到达区域内的任意像素。
用这种方法填充的区域就称为八连通域；这种填充方法称为八向连通算法。
一般来说，八向连通算法可以填充四向连通区域,而四向连通算法有时不能填充八向连通区域。
四向连通填充算法:a）种子像素压入栈中;b)如果栈为空,则转e）；否则转c）;c) 弹出一个像素,并将该像素置成填充色;并判断该像素相邻的四连通像素是否为边界色或已经置成多边形的填充色，若不是,则将该像素压入栈;d)转b）;ｅ）结束。
四连通填充算法利用到了递归的思想。
本实验只包括四连通填充算法程序代码:#ｉncludｅ<ｇlut.h>＃ｉｎｃlｕde<ｓtdｌib．h>＃ｉncｌudｅ<math．h>#include<ｗindowｓ.h＞voidｉniｔ（vｏid）{ glCｌearColor(１．０，１.0,1．0,0.０）；glMatrixMoｄｅ（ＧL_PROJＥCTION）;gｌｕOrtho２D（０．0，30０．0，０.0,30０.0);}voｉd setPixel(inｔx，ｉnｔy,lｏｎｇｆillCoｌor）{ ｇlColor3f（fｉllCoｌoｒ<<16,filｌCoｌor<<８,fillCｏloｒ)；ｇlＢｅgin（ＧL_ＰＯINTＳ);ｇlＶｅｒteｘ2i（x,y）;ｇlEnｄ();}ｖｏｉｄboundaryFill４(iｎt x,ｉnｔy,lｏng fillＣolor,lｏng bordeｒColor）{ unｓｉgneｄchａr paｒams[3];loｎg interioｒCoｌoｒ;glRｅaｄPixels(ｘ，y,1,1,GL_RGB,GＬ＿UNSIＧNＥD_BYＴE,par ａms）;interiorCoｌoｒ=RGB(paraｍs[0],ｐarａms[１］,paｒaｍs[2])；ｉf(inteｒiorＣolor!=boｒderCｏloｒ＆＆inteｒiｏrCoｌｏr!=filｌColor){ setＰixeｌ(x，ｙ,fｉｌlCoｌｏr);ｂoundaryFill4（x＋1,y,filｌＣoｌｏr,ｂordeｒCｏlor);ｂｏunｄaｒyＦｉｌl4(ｘ-1，y，fiｌlＣolor,borderColor); boundaryFilｌ４(x,ｙ+1,ｆｉlｌColｏr,borｄeｒCoｌor)；ｂounｄarｙFill4(x，y-1，ｆｉllColｏr，ｂorｄerＣolor);} }voiｄlineＳegment(voｉd) {long bｏrｄerCｏｌoｒ=RGB（255，0,０);lｏngｆiｌlColoｒ=RGB（０，0，255）;glClｅar（ＧL_COＬOR＿BUFFER_BIT); glCｏloｒ３ｆ(２55，0,0); ｇlＢegｉn（GL_ＬINE＿ＬＯＯP);glVeｒtex2ｉ(0,４0);glVｅｒteｘ2i(2０,0);glＶertex２i(６0,0）；glＶeｒtｅx2ｉ(80，4０）;ｇlVｅｒtex2i(６0,80);gｌVertex２i(20,80);gｌＥnd();boundaryＦill4(６０,60，ｆｉllＣolor,ｂorderColｏr)；gｌFlush()；}voｉｄmain(ｉｎt argc,chａr＊*aｒgv）｛ｇlutIｎｉｔ(&ａr ｇc,aｒｇv);glｕtInitDｉsｐｌaｙMode(GLUＴ＿ＳＩNGLE｜GLUT_ＲGB); glutInitＷindowPｏsiｔion（1５0,10０）;gluｔIｎitWinｄoｗSizｅ(300,３0０）;glutＣreateＷｉｎdow（"种子填充"）；init();glutDisｐlayFｕｎｃ(lｉneＳegｍeｎt);gｌｕtMａinＬｏoｐ(）;}上实验课时机房的实验结果:后来的实验结果:glVｅrteｘ2i（0,40);gｌＶerteｘ２i（20，0);glVerｔex2i（60,０);glVerteｘ2i（８0，４０);gｌＶertｅx2ｉ(60，80);ｇlＶerteｘ2i(２0,80)；ｇlEnｄ();ｂｏｕndaryFｉlｌ4(60,60，ｆｉlｌCｏlor,ｂorderＣoｌor）；以上这段程序改成如下glVerｔex2ｉ(９0，40);glVｅrtｅx２i（１2０, １00）;ｇlVertex2i(90,1６0);glVertｅｘ２i(60, 160);ｇlVertex2i(60, ４０);glEnd()；bouｎｄaryFilｌ4(７0,6０,fiｌｌCｏｌoｒ,bｏｒderCoｌor); 改变参数后：再把ｇlVeｒｔｅx2i（9０，40);glVertｅｘ２i(120, 100）；glＶｅrｔex2i(90,160）;glＶerｔex2i(60, １6０）;glVｅrtex２i（６0, 40）;gｌＥnd（);bｏundaryFill4（70,6０,fiｌlCｏloｒ,boｒdｅrCｏlor）；改成glVeｒtex2i(100, １０0)；glVｅrteｘ2i(２00, 100);gｌVｅｒteｘ2ｉ(1５0,150);/／glVｅrteｘ2ｉ(60, 1６0);／/glVertｅx2i(6０, 40)；glＥnd();ｂoundaryFill4(150，1２0,fiｌlCｏlor，borｄerCoｌoｒ);后的结果如下图:实验总结:通过多组数据的测试，知道了上面算法的正确,普适性。
实验二4-10一、实验题目扫描线种子填充算法是通过扫描线来填充多边形内的水平像素段，处理每条扫描线时仅需将其最右端像素入栈，可以有效提高填充效率。
请使用MFC编程填充图4-60所示的空心体汉字（四连通），填充效果如图4-61所示。
二、实验思想扫描线种子填充算法：先将种子像素入栈，种子像素为栈底像素，如果栈不为空，执行如下4步操作。
（1）栈顶像素出栈。
（2）沿扫描线对出栈像素的左右像素进行填充，直至遇到边界像素为止。
即每出栈一个像素，就对区域内包含该像素的整个连续区间进行填充。
（3）同时记录该区间，将区间最左端像素记为x left，最右端像素记为x right。
（4）在区间〔x left，x right〕中检查与当前扫描线相邻的上下两条扫描线的有关像素是否全为边界像素或已填充像素，若存在非边界且未填充的像素，则把未填充区间的最右端像素取作种子像素入栈。
三、实验代码void CTestView::OnLButtonDown(UINT nFlags, CPoint point)//左键按下函数{// TODO: Add your message handler code here and/or call defaultSeed=point;//选择种子位置CharFill();//进行填充CView::OnLButtonDown(nFlags, point);}void CTestView::CharFill()//文字填充函数{CRect Rect;GetClientRect(&Rect);CClientDC dc(this);COLORREF BoundColor;//边界色int Width=Rect.right-Rect.left;int Hight=Rect.bottom-Rect.top ;int Flag;int x0,y0,x,y;CPoint Point;std::vector<CPoint> FillBuffle;//定义CPoint类型的数组序列对象FillBuffle.reserve(10);//定义数组序列的大小FillBuffle.push_back(CPoint(Seed)); //把种子结点压入数组序列BoundColor=RGB(0,0,0);//定义边界色为黑色while(!FillBuffle.empty())//如果数组序列非空{Point=FillBuffle.front();//弹出数组序列头元素x=Point.x;y=Point.y;FillBuffle.erase(FillBuffle.begin());//清除数组序列内的元素dc.SetPixel(Point,Fillcolor);//绘制像素//判断像素的位置是否在图形内部x0=x+1;//右方判断while(dc.GetPixel(x0,y)!=BoundColor&&dc.GetPixel(x0,y)!=Fillcolor) {x0=x0+1;if(x0>=Width)//到达屏幕最右端{MessageBox("种子超出范围","警告");RedrawWindow();return;}}y0=y+1;//下方判断while(dc.GetPixel(x,y0)!=BoundColor&&dc.GetPixel(x,y0)!=Fillcolor) {y0=y0+1;if(y0>=Hight)//到达屏幕最下端{MessageBox("种子超出范围","警告");RedrawWindow();return;}}RightPoint.x=x0;//右边界内的左邻点x0=x-1;while(dc.GetPixel(x0,y)!=Fillcolor&&dc.GetPixel(x0,y)!=BoundColor){dc.SetPixel(x0,y,Fillcolor);x0=x0-1;if(x0<=0)//到达屏幕最左端{MessageBox("种子超出范围","警告");RedrawWindow();return;}}y0=y-1;while(dc.GetPixel(x,y0)!=BoundColor&&dc.GetPixel(x,y0)!=Fillcolor){y0=y0-1;if(y0<=0)//到达屏幕最上端{MessageBox("种子超出范围","警告");RedrawWindow();return;}}LeftPoint.x=x0+1;//左边界内的右邻点x0=LeftPoint.x;y=y+1;//下一条扫描线while(x0<RightPoint.x){Flag=0;while((dc.GetPixel(x0,y)!=Fillcolor)&&(dc.GetPixel(x0,y)!=BoundColor)) {if(Flag==0)Flag=1;x0++ ;}if(Flag==1){if((x0==RightPoint.x)&&(dc.GetPixel(x0,y)!=Fillcolor)&&(dc.GetPixel(x0,y)!=BoundColor))FillBuffle.push_back(CPoint(x0,y));//进入数组序列else{FillBuffle.push_back(CPoint(x0-1,y));}Flag=0;}PointNext.x=x0;while(((dc.GetPixel(x0,y)==Fillcolor)&&(x0<RightPoint.x))||((dc.GetPixel(x0,y)==BoundColor) &&(x0<RightPoint.x))){x0 ++;}}x0=LeftPoint.x;y=y-2;while(x0<RightPoint.x){Flag=0;while((dc.GetPixel(x0,y)!=Fillcolor)&&(dc.GetPixel(x0,y)!=BoundColor)&&(x0<RightPoint.x)) {if(Flag==0)Flag=1;x0++ ;}if(Flag==1){if((x0==RightPoint.x)&&(dc.GetPixel(x0,y)!=Fillcolor)&&(dc.GetPixel(x0,y)!=BoundColor))FillBuffle.push_back(CPoint(x0,y));else{FillBuffle.push_back(CPoint(x0-1,y));}Flag=0;}PointNext.x=x0;while((dc.GetPixel(x0,y)==Fillcolor&&x0<RightPoint.x)||(dc.GetPixel(x0,y)==BoundColor&&x 0<RightPoint.x)){x0++;}}}FillBuffle.clear();return;}void CTestView::OnMENUFill(){// TODO: Add your command handler code hereRedrawWindow();MessageBox("请在空心字体内部单击鼠标左键!","提示");}四、实验结果截图。
计算机图形学——区域填充算法（基本光栅图形算法）⼀、区域填充概念区域：指已经表⽰成点阵形式的填充图形，是象素的集合。
区域填充：将区域内的⼀点（常称【种⼦点】）赋予给定颜⾊，然后将这种颜⾊扩展到整个区域内的过程。
区域填充算法要求区域是连通的，因为只有在连通区域中，才可能将种⼦点的颜⾊扩展到区域内的其它点。
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)改进算法，减少递归次数，提⾼效率三、扫描线种⼦填充算法基本思想从给定的种⼦点开始，填充当前扫描线上种⼦点所在的⼀区段，然后确定与这⼀段相邻的上下两条扫描线上位于区域内的区段（需要填充的区间），从这些区间上各取⼀个种⼦点依次把它们存起来，作为下次填充的种⼦点。
图形学种子填充算法．/种子填充算法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;int p[5]; //每根扫描线交点int pmin = 0,pmax = 0;for(int i=0;i<=6;i++)//建立边表{edge[i].dx=(float)(spt[i+1].x-spt[i].x)/(spt[i+1].y-spt[i].y); if(spt[i].y<=spt[i+1].y){edge[i].num=i;edge[i].ymin=spt[i].y;edge[i].ymax=spt[i+1].y;edge[i].xmin=(float)spt[i].x;edge[i].xmax=(float)spt[i+1].x;if(spt[i+1].y > pmax)pmax = spt[i+1].y;if(spt[i].y < pmin)pmin = spt[i].y;}else{edge[i].num=i;edge[i].ymin=spt[i+1].y;edge[i].ymax=spt[i].y;edge[i].xmax=(float)spt[i].x;edge[i].xmin=(float)spt[i+1].x;if(spt[i].y > pmax)pmax = spt[i].y;if(spt[i+1].y < pmin)pmin = spt[i+1].y;}}for(int r=1;r<=6;r++) //排序edge(yUpper，xIntersect)，结果为从大到小{for(int q=0;q<=6-r;q++){if(edge[q].ymin<edge[q+1].ymin){newedge[0]=edge[q]; edge[q]=edge[q+1];edge[q+1]=newedge[0];}}}if((s；for(j=k;j<=6;j++)intb=0;for(intscan=pmax-1;scan&；；k=s;；bif(spt[edge[j].num+1].y&；can>edge[j].ymin；if(scan==edge[j].ymax)；elseif(spt[edge[j].；++;p[b]=(int)edge[j].xmax;；for(int scan=pmax-1;scan>=pmin+1;scan--){int b=0;k=s;for(j=k;j<=6;j++){if((scan>edge[j].ymin)&&(scan<=edge[j].ymax))//判断与线段相交{if(scan==edge[j].ymax){if(spt[edge[j].num+1].y<edge[j].ymax){b++;p[b]=(int)edge[j].xmax;}else if(spt[edge[j].num-1].y<edge[j].ymax) {b++;p[b]=(int)edge[j].xmax;}}if((scan>edge[j].ymin)&&(scan<edge[j].ymax)){b++;p[b]=(int)(edge[j].xmax+edge[j].dx*(scan-edge[j].ymax)); } }//pDC->LineTo(spt[edge[0].num].x,spt[edge[0].num].y);if(scan<=edge[j].ymin)//s=j;}if(b>1){for(int u=1;u<b;u++){pDC->MoveTo(p[u]-1,scan);u++;pDC->LineTo(p[u],scan);}}}pDC->SelectObject(old); pDC->SelectObject(old2); }。
CGA填充算法之种⼦填充算法CGA填充算法之种⼦填充算法 平⾯区域填充算法是计算机图形学领域的⼀个很重要的算法，区域填充即给出⼀个区域的边界（也可以是没有边界，只是给出指定颜⾊），要求将边界范围内的所有象素单元都修改成指定的颜⾊（也可能是图案填充）。
区域填充中最常⽤的是多边形填⾊，本⽂讨论种⼦填充算法（Seed Filling） 如果要填充的区域是以图像元数据⽅式给出的，通常使⽤种⼦填充算法（Seed Filling）进⾏区域填充。
种⼦填充算法需要给出图像数据的区域，以及区域内的⼀个点，这种算法⽐较适合⼈机交互⽅式进⾏的图像填充操作，不适合计算机⾃动处理和判断填⾊。
根据对图像区域边界定义⽅式以及对点的颜⾊修改⽅式，种⼦填充⼜可细分为⼏类： ⽐如：①注⼊填充算法（Flood Fill Algorithm）、 ②边界填充算法（Boundary Fill Algorithm）以及 ③为减少递归和压栈次数⽽改进的扫描线种⼦填充算法等等。
所有种⼦填充算法的核⼼其实就是⼀个递归算法，都是从指定的种⼦点开始，向各个⽅向上搜索，逐个像素进⾏处理，直到遇到边界，各种种⼦填充算法只是在处理颜⾊和边界的⽅式上有所不同。
在开始介绍种⼦填充算法之前，⾸先也介绍两个概念，就是“4-联通算法”和“8-联通算法”。
既然是搜索就涉及到搜索的⽅向问题，从区域内任意⼀点出发，如果只是通过上、下、左、右四个⽅向搜索到达区域内的任意像素，则⽤这种⽅法填充的区域就称为四连通域，这种填充⽅法就称为 “4-联通算法”。
如果从区域内任意⼀点出发，通过上、下、左、右、左上、左下、右上和右下全部⼋个⽅向到达区域内的任意像素，则这种⽅法填充的区域就称为⼋连通域，这种填充⽅法就称为“8-联通算法”。
如图1（a）所⽰，假设中⼼的蓝⾊点是当前处理的点，如果是“4-联通算法”，则只搜索处理周围蓝⾊标识的四个点，如果是“8-联通算法”则除了处理上、下、左、右四个蓝⾊标识的点，还搜索处理四个红⾊标识的点。
/种子填充算法
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;
int p[5]; //每根扫描线交点
int pmin = 0,pmax = 0;
for(int i=0;i<=6;i++)//建立边表
{
edge[i].dx=(float)(spt[i+1].x-spt[i].x)/(spt[i+1].y-spt[i].y); if (spt[i].y<=spt[i+1].y){
edge[i].num=i;
edge[i].ymin=spt[i].y;
edge[i].ymax=spt[i+1].y;
edge[i].xmin=(float)spt[i].x;
edge[i].xmax=(float)spt[i+1].x;
if(spt[i+1].y > pmax)
pmax = spt[i+1].y;
if(spt[i].y < pmin)
pmin = spt[i].y;
}
else{
edge[i].num=i;
edge[i].ymin=spt[i+1].y;
edge[i].ymax=spt[i].y;
edge[i].xmax=(float)spt[i].x;
edge[i].xmin=(float)spt[i+1].x;
if(spt[i].y > pmax)
pmax = spt[i].y;
if(spt[i+1].y < pmin)
pmin = spt[i+1].y;
}
}
for(int r=1;r<=6;r++) //排序edge(yUpper，xIntersect)，结果为从大到小
{
for(int q=0;q<=6-r;q++)
{
if(edge[q].ymin<edge[q+1].ymin)
{
newedge[0]=edge[q]; edge[q]=edge[q+1];
edge[q+1]=newedge[0];
}
}
}
for(intscan=pmax-1;scan&；intb=0;；k=s;；for(j=k;j<=6;j++)；if((sc an>edge[j].ymin；if(scan==edge[j].ymax)；if(spt[edge[j].num+1].y&；b+ +;；p[b]=(int)edge[j].xmax;；elseif(spt[edge[j].
for(int scan=pmax-1;scan>=pmin+1;scan--)
{
int b=0;
k=s;
for(j=k;j<=6;j++)
{
if((scan>edge[j].ymin)&&(scan<=edge[j].ymax))//判断与线段相交
{
if(scan==edge[j].ymax)
{
if(spt[edge[j].num+1].y<edge[j].ymax)
{
b++;
p[b]=(int)edge[j].xmax;
}
else if(spt[edge[j].num-1].y<edge[j].ymax) {
b++;
p[b]=(int)edge[j].xmax;
}
}
if((scan>edge[j].ymin)&&(scan<edge[j].ymax))
{
b++;
p[b]=(int)(edge[j].xmax+edge[j].dx*(scan-edge[j].ymax)); }
}
//pDC->LineTo(spt[edge[0].num].x,spt[edge[0].num].y); if(scan<=ed ge[j].ymin)//
s=j;
}
if(b>1)
{
for(int u=1;u<b;u++)
{
pDC->MoveTo(p[u]-1,scan);
u++;
pDC->LineTo(p[u],scan);
}
}
}
pDC->SelectObject(old); pDC->SelectObject(old2); }。
