计算机图形学实验报告8-种子点填充

一、实验目标1.了解基于种子填充算法的基本思想；2.掌握基于种子填充算法的算法实现；3.掌握栈的使用。

二、实验内容本次实验主要是实现递归种子填充算法、简单种子填充算法、扫描线种子填充算法以及区域图案填充算法。

种子填充算法原理简述：在开始介绍种子填充算法之前，首先也介绍两个概念，就是“4-连通算法”和“8-连通算法”。

既然是搜索就涉及到搜索的方向问题，从区域内任意一点出发，如果只是通过上、下、左、右四个方向搜索到达区域内的任意像素，则用这种方法填充的区域就称为四连通域，这种填充方法就称为“4-连通算法”。

如果从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下全部八个方向到达区域内的任意像素，则这种方法填充的区域就称为八连通域，这种填充方法就称为“8-连通算法”。

种子填充算法采用的边界定义是区域边界上所有像素均具有某个特定的颜色值，区域内部所有像素均不取这一特定颜色，而边界外的像素则可以具有和边界相同的颜色值。

程序从（x，y）开始，先检测该点的颜色，如果它与边界色和填充色均不相同，就用填充色填充该点，然后检测相邻位置，以确定它们是否边界色和填充色，若不是，就填充该相邻点。

这个过程延续到已经检测完边界范围内的所有像素为止。

扫描线种子填充算法原理简述：当给定种子点(x, y)时，首先分别向左和向右两个方向填充种子点所在扫描线上的位于给定区域的一个区段，同时记下这个区段的范围[xLeft, xRight]，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。

反复这个过程，直到填充结束。

扫描线种子填充算法可由下列四个步骤实现：(1)初始化一个空的栈用于存放种子点，将种子点(x, y)入栈；(2)判断栈是否为空，如果栈为空则结束算法，否则取出栈顶元素作为当前扫描线的种子点(x, y)，y是当前的扫描线；(3)从种子点(x, y)出发，沿当前扫描线向左、右两个方向填充，直到边界。

总结
八邻接点种子填充算法的种子像素可以位于区域的上方 多边形内或下方多边形内，填充过程不同，但都可以获得一 致的填充效果。
（a）多边形
（b）连接点放大效果图 图9-1八连通域
效果图
图9-2 效果图
原理算法
（1）调用颜色对话框读取填充色。 （2）绘制多边形区域。 （3）设置默认边界色为黑色，默认种子色为蓝色。 （4）鼠标选择种子的像素的坐标（x0,y0）位置，执行x=x0±1与 y=y0±1操作，判断x或y是否到达客户区边界。如果x或y到达客户区边 界，给出“种子不在图形之内”的警告信息，重新选择种子像素的位 置。 （5）将多边形区域内的种子像素入栈。 （6）如果栈不为空，将栈顶像素出栈，用种子色绘制出栈像素。 （7）按左、左上、上、右上、右、右下、下、左下顺序搜索出栈像素 的八个邻接点像素。如果相邻像素的颜色不是边界色并且不是种子色 ，将其入栈，否则丢弃。 （8）重复步骤（6），直到栈为空。
程序代码
填充函数 while(pHead->pNext!=NULL)//如果栈不为空 { CP2 PopPoint; Pop(PopPoint); pDC->SetPixelV(Round(PopPoint.x),Round(PopPoint.y),SeedClr); Left.x=PopPoint.x-1;//搜索出栈结点的左方像素 Left.y=PopPoint.y; PixelClr=pDC->GetPixel(Round(Left.x),Round(Left.y)); if(BoundaryClr!=PixelClr && SeedClr!=PixelClr)//不是边界色并且未置成填充色 Push(Left);//左方像素入栈 LeftTop.x=PopPoint.x-1; LeftTop.y=PopPoint.y+1;//搜索出栈结点的左上方像素 PixelClr=pDC->GetPixel(Round(LeftTop.x),Round(LeftTop.y));

CFill.cpp参考代码：
// Fill.cpp : implementation file
#include "stdafx.h"
#include "FloodFill.h"
#include "Fill.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
（1）种子填充算法原理
在多边形内部找到一个已知的象素点作为种子点，由此开始，利用区域的连通性找到多边形内部的 其它所有象素点进行填充。
（i）四向连通区域
①四向连通区域概念：从区域上任一点出发，在不超出区域边界的前提下，可通过4个方向：上、下、左、右的移动组合到达区域中的任意象素点，称此区域为四向连通区域。
{
//有需要填充的区域
if(spanNeedFill==FALSE)
{
spanNeedFill = TRUE;
}
x++;
}
if(spanNeedFill)
{
CPoint rightp(x-1,y);
stack.Push(x-1);
stack.Push(y);
spanNeedFill = FALSE;
virtual ~CStack();
};
#endif // !defined(AFX_STACK_H__D198F788_4ED1_4C09_98E5_433BAB24D864__INCLUDED_)
CStack.cpp参考代码：
// Stack.cpp: implementation of the CStack class.
#if !defined(AFX_STACK_H__D198F788_4ED1_4C09_98E5_433BAB24D864__INCLUDED_) #define AFX_STACK_H__D198F788_4ED1_4C09_98E5_433BAB24D864__INCLUDED_

《计算机图形学》实验报告(实验二：图形填充算法)一、实验目的及要求用两种方法做图形的填充算法！二、理论基础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、四、实验心得及建议由于很多不会，所以这次没能按时当堂完成，下来花了不少时间才弄出来，第二种尤其比较麻烦，在同学的帮助下才做出来了。

return
image[x][y] = value
for i in range(8):
fill(x + dx[i], y + dy[i])
#调用递归函数来填充种子周围的像素
fill(seed[0], seed[1])
这个算法使用了一个递归函数来填充种子周围的像素。在函数中，我们首先检查当前像素是否在图像的边界内，并且是否与种子像素相连。如果是，我们将其值设置为目标值，并递归地填充与当前像素相连的像素。通过调用fill(seed[0], seed[1])，我们可以从种子像素开始填充整个连通区域。
dy = [-1, 0, 1, -1, 0, 1, -1, 0]
#定义四个边界条件
left = 0
right = width - 1
top = 0
bottom = height - 1
#定义递归函数来填充种子周围的像素
def fill(x, y):
if x < left or x > right or y < top or y > bottom or image[x][y] != seed:
八邻接点种子填充算法是一种用于图像处理的算法，用于填充二值图像中的连通区域。以下是一个简单的Python实现：
def seedfill(image, height = image.shape
#定义八个方向的偏移量
dx = [-1, -1, -1, 0, 0, 0, 1, 1]

2.1 深度递归的种子填充算法
2.2 扫描线种子填充算法
2.1 深度递归的种子填充算法
种子填色又称边界填色(Boundary Filling)。 它的功能是，给出多边形光栅化后的边界位置及边 界色代码oundary_color，以及多边形内的一点(x, y)位置，要求将颜色fill_color填满多边形。
动画演示
扫描线种子填充算法特点
1. 该算法考虑了扫描线上象素的相关性，种子象 素不再代表一个孤立的象素，而是代表一个尚 未填充的区段。 2. 进栈时，只将每个区段选一个象素进栈（每个 区段最右边或最左边的象素），这样解决了堆 栈溢出的问题。 3. 种子出栈时，则填充整个区段。 4. 这样有机的结合：一边对尚未填充象素的登记 （象素进栈），一边进行填充（象素出栈）， 既可以节省堆栈空间，又可以实施快速填充。

3. 已知有一个5边形如下。建立新边表 NET，并写出每一条扫描线经过时活性边 表AET中的数据状态。
X ΔX Ymax
第1项存当前扫描线与边的交点坐标x值； 第2项存从当前扫描线到下一条扫描线间x的增量Dx; 第3项存该边所交的最高扫描线号ymax； 第4项存指向下一条边的指针。
假定当前扫描线与多边形某一条边的交点的x 坐标为x，则下一条扫描线与该边的交点不要重计 算，只要加一个增量△x。(连贯性) 设该边的直线方程为：ax+by+c=0； 若y＝yi，x=x i；则当y = y i+1时， x i+1=xi-b/a 其中ΔX= -b/a为常数， 另外使用增量法计算时，我们需要知道一条边 何时不再与下一条扫描线相交，以便及时把它从 活性边表中删除出去。
建立或调整AET(ActiveEdgeList)；

计算机图形学四连通区域种子填充算法实验————————————————————————————————作者: ————————————————————————————————日期:ﻩ《计算机图形学实验》报告任课教师:钱文华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("请在空心字体内部单击鼠标左键!","提示");}四、实验结果截图。

实验四区域填充算法的实现班级 08信计2班学号 20080502082 姓名分数一、实验目的和要求：1、理解区域的表示和类型。

2、能正确区分四连通和八连通的区域3、了解区域填充的实验原理。

4、利用C++实现区域填充的递归算法。

二、实验内容：1假设在多边形内有一像素已知，由此出发利用连通性找到区域内所有像素。

2 取（x，y）为种子点将整个区域填充为新的颜色。

3 进行递归填充。

三、实验结果分析区域填充属性包括填充样式，填充颜色和填充图案的类型。

C语言中定义了某种图形后，即可调用-floodfill函数，对指定区域进行填充. 程序代码#define pi 3.141592#define MAX(a,b) (a>b)? a:b#define MIN(a,b) (a<b)? a:b#include "graphics.h"#include "math.h"struct edge {int ymax;float x;float delat;struct edge * pedge; };struct point{int x;int y;} ;struct et { struct edge * pedge;int n;};struct edge g_aet[10];struct edge dge[10];struct et g_et[10];struct point point1,point2;int ZUO(float x){ if((int)x==x)return (int)x;return (int)x+1;}int YOU(float x){ if((int)x==x)return (int)x-1;return (int)x;}int k=400,l=0;void draw1(){int i,t,j,a,c,p,z; float b;struct edge temp;for(i=k;i<=l;i++){a=0;for(t=0;t<=9;t++){ if(g_et[t].n==i) break;}for(j=0;j<=9;j++){ if(g_aet[j].ymax==0) break;}if(t!=10){ g_aet[j].ymax=g_et[t].pedge->ymax;g_aet[j].x=g_et[t].pedge->x;g_aet[j].delat=g_et[t].pedge->delat;if(g_et[t].pedge->pedge!=0){g_aet[j+1].ymax=g_et[t].pedge->pedge->ymax;g_aet[j+1].x=g_et[t].pedge->pedge->x;g_aet[j+1].delat=g_et[t].pedge->pedge->delat; }}for(j=0;j<=9;j++){ if(g_aet[j].ymax==0) break; }j--;for(t=0;t<=j;t++){ for(z=0;z<=j-1;z++){if(g_aet[z].x>g_aet[z+1].x){ temp.ymax=g_aet[z].ymax;temp.x=g_aet[z].x;temp.delat=g_aet[z].delat;g_aet[z].ymax=g_aet[z+1].ymax;g_aet[z].x=g_aet[z+1].x;g_aet[z].delat=g_aet[z+1].delat;g_aet[z+1].ymax=temp.ymax;g_aet[z+1].x=temp.x;g_aet[z+1].delat=temp.delat;}}}for(j=0;j<=9;j++){ if(g_aet[j].ymax==0) break; }j--;for(p=0;p<=j;p++){ a++;if(a%2!=0)b=g_aet[p].x;else{for(c=ZUO(b);c<=YOU(g_aet[p].x);c++)putpixel(c,i,2);}}for(t=0;t<=j;t++){ if(g_aet[t].ymax==(i+1)){ g_aet[t].ymax=0;g_aet[t].x=0;g_aet[t].delat=0;}g_aet[t].x+=g_aet[t].delat;}for(t=0;t<=j;t++){ for(z=0;z<=j-1;z++){if(g_aet[z].x<g_aet[z+1].x){ temp.ymax=g_aet[z].ymax;temp.x=g_aet[z].x;temp.delat=g_aet[z].delat;g_aet[z].ymax=g_aet[z+1].ymax;g_aet[z].x=g_aet[z+1].x;g_aet[z].delat=g_aet[z+1].delat;g_aet[z+1].ymax=temp.ymax;g_aet[z+1].x=temp.x;g_aet[z+1].delat=temp.delat;}}}}}void generate(){int i,y,n=1,m,q,p;float x;for(i=0;i<=9;i++){if(n==1){ point2.x=point1.x=300;point2.y=point1.y=200;n++;}else{ if(n%2==0){ x=40*cos(i*pi/5)+200;y=40*sin(i*pi/5)+200;}else{ x=100*cos(i*pi/5)+200;y=100*sin(i*pi/5)+200;}if(point1.y==y) { n++; continue;}m=MIN(point1.y,y);if(x==point1.x){ dge[i-1].delat=0;dge[i-1].ymax=MAX(point1.y,y);dge[i-1].x=x;dge[i-1].pedge=0;for(q=0;q<=9;q++){ if(g_et[q].n==m) break;}if(q==10){g_et[i-1].pedge=&dge[i-1];g_et[i-1].n=m;}else{g_et[q].pedge->pedge=&dge[i-1];g_et[i-1].n=0;}}else{dge[i-1].delat=(float)(x-point1.x)/(y-point1.y);dge[i-1].ymax=MAX(point1.y,y);if(point1.y>y) dge[i-1].x=x;else {dge[i-1].x=point1.x; }dge[i-1].pedge=0;for(q=0;q<=9;q++){ if(g_et[q].n==m) break;}if(q==10){ g_et[i-1].pedge=&dge[i-1];g_et[i-1].n=m;}else{g_et[q].pedge->pedge=&dge[i-1];g_et[i-1].n=0;}}p=MAX(point1.y,y);k=MIN(k,m);l=MAX(l,p);point1.x=x;point1.y=y;n++;}}if(point1.y==point2.y) return;else{if(point2.x==point1.x){dge[i-1].delat=0;dge[i-1].ymax=MAX(point1.y,point2.y);dge[i-1].x=point2.x;}else{ dge[i-1].ymax=MAX(point1.y,point2.y);if(point1.y>point2.y) dge[i-1].x=point2.x;else {dge[i-1].x=point1.x;}dge[i-1].delat=(float)(point2.x-point1.x)/(point2.y-point1.y);}}m=MIN(point1.y,point2.y);k=MIN(k,m);l=MAX(l,dge[i-1].ymax);g_et[i-1].n=m;g_et[i-1].pedge=&dge[i-1];}void main(){ int driver=DETECT,mode; int i; registerbgidriver(EGA VGA_driver);initgraph(&driver,&mode,"\\tc");initgraph(&driver,&mode,"\\tc");for(i=0;i<=9;i++){ g_aet[i].ymax=0; g_aet[i].x=0; g_aet[i].delat=0;g_et[i].pedge=0;}generate();draw1();circle(200,200,100); circle(200,200,40);getch();closegraph();}。

计算机图形学——区域填充的扫描线算法一．实验名称：区域填充的扫描线算法二．实验目的：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.此扫描线填充算法能够对多种图案进行填充，展现了算法的实用性。

《计算机图形学》实验报告一、实验目的计算机图形学是一门研究如何利用计算机生成、处理和显示图形的学科。

通过本次实验，旨在深入理解计算机图形学的基本原理和算法，掌握图形的生成、变换、渲染等技术，并能够运用所学知识解决实际问题，提高对图形学的应用能力和编程实践能力。

二、实验环境本次实验使用的编程语言为 Python，使用的图形库为 Pygame。

开发环境为 PyCharm。

三、实验内容1、直线的生成算法DDA 算法（Digital Differential Analyzer）Bresenham 算法DDA 算法是通过计算直线的斜率来确定每个像素点的位置。

它的基本思想是根据直线的斜率和起始点的坐标，逐步计算出直线上的每个像素点的坐标。

Bresenham 算法则是一种基于误差的直线生成算法。

它通过比较误差值来决定下一个像素点的位置，从而减少了计算量，提高了效率。

在实验中，我们分别实现了这两种算法，并比较了它们的性能和效果。

2、圆的生成算法中点画圆算法中点画圆算法的核心思想是通过判断中点的位置来确定圆上的像素点。

通过不断迭代计算中点的位置，逐步生成整个圆。

在实现过程中，需要注意边界条件的处理和误差的计算。

3、图形的变换平移变换旋转变换缩放变换平移变换是将图形在平面上沿着指定的方向移动一定的距离。

旋转变换是围绕一个中心点将图形旋转一定的角度。

缩放变换则是改变图形的大小。

通过矩阵运算来实现这些变换，可以方便地对图形进行各种操作。

4、图形的填充种子填充算法扫描线填充算法种子填充算法是从指定的种子点开始，将相邻的具有相同颜色或属性的像素点填充为指定的颜色。

扫描线填充算法则是通过扫描图形的每一行，确定需要填充的区间，然后进行填充。

在实验中，我们对不同形状的图形进行了填充，并比较了两种算法的适用情况。

四、实验步骤1、直线生成算法的实现定义直线的起点和终点坐标。

根据所选的算法（DDA 或Bresenham）计算直线上的像素点坐标。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

实验四区域填充算法的实现班级 08信计学号 67姓名张洪伟分数一、实验目的和要求：1. 理解区域的表示和类型；2．实现区域填充的扫描线算法；3．WIN-TC 图形编程模板实现编程结果并保存。

二、实验内容：在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描线上的该段区间；然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的每个区段都填充完毕。

1. 确定种子区段：从种子点出发，沿当前扫描线向左右两个方向填充直到边界。

用三元组(y,xLeft,xRight)记录此区段。

2．初始化：将堆栈设为空，将种子区段压入堆栈。

3．出栈：若堆栈为空，算法结束;否则取栈顶元素，以纵坐标为y的扫描线为当前扫描线，[xLeft,xRight]为搜索区间。

4．进栈：分别确定与当前扫描线相邻的上下两条扫描线与区段(y,xLeft,xRight)连通的位于给定区域内的区段。

如果有这样的区段，填充并将它们的信息压入堆栈，返回步骤3。

三、实验结果分析1该实验先用fillellipse(100,100,60,40) 画出实心椭圆，然后用如上算法填充，代码如下：setcolor(5);fillellipse(300,250,60,40);ScanLineFill(300,250,15,5);此算法还能填充带边框的多边形，如下代码填充一个矩形区域，oldColor 为背景色0：rectangle(100,20,200,50);ScanLineFill(125,30,0,5);如下代码填充带孔的四连通区域：bar(100,80,150,180);bar(150,80,200,90);bar(200,80,250,180);bar(150,130,200,180);ScanLineFill(110,150,15,2);对于每一个待填充的区段，只需压栈一次，因此扫描线算法的效率提高了很多。

《计算机图形学实验》报告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：多边形区域扫描线填充或种子填充实验类型：验证、设计所需时间：3学时主要实验内容及要求：实现多边形区域扫描线填充的有序边表算法，并将实现的算法应用于任意多边形的填充，要求多边形的顶点由键盘输入或鼠标拾取，填充要准确，不能多填也不能少填。

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

参考试验步骤：1）分析多边形区域扫描线填充算法的原理，确定算法流程①初始化：构造边表，AET表置空②将第一个不空的ET表中的边插入AET表③由AET表取出交点进行配对（奇偶）获得填充区间，依次对这些填充区间着色④y=y i+1时，根据x=x i+1/k修改AET表所有结点中交点的x坐标。

同时如果相应的ET表不空，则将其中的结点插入AET表，形成新的AET表⑤AET表不空，则转（3），否则结束。

2）编程实现①首先确定多边形顶点和ET/AET表中结点的结构②编写链表相关操作（如链表结点插入、删除和排序等）③根据1）中的算法结合上述已有的链表操作函数实现多边形区域扫描线填充的主体功能④编写主函数，测试该算法源代码：#include<gl/glut.h>#include<iostream>using namespace std;typedef struct dePt{int x;int y;}dePt;void fill(GLint x1,GLint y1,GLint z1){glBegin(GL_POINTS);glVertex3f(x1,y1,0.0f);glEnd();}typedef struct Edge{int yUpper;float xIntersect, dxPerScan;struct Edge *next;}Edge;void insertEdge(Edge *list, Edge *edge){Edge *p,*q=list;p=q->next;while(p!=NULL){if(edge->xIntersect<p->xIntersect)p=NULL;else{q=p;p=p->next;}}edge->next=q->next;q->next=edge;}int yNext(int k, int cnt, dePt*pts){int j;if((k+1)>(cnt-1))j=0;elsej=k+1;while(pts[k].y==pts[j].y)if((j+1)>(cnt-1))j=0;else j++;return (pts[j].y);}void makeEdgeRec(dePt lower, dePt upper,int yComp,Edge *edge,Edge *edges[]) {edge->dxPerScan=(float)(upper.x-lower.x)/(upper.y-lower.y);edge->xIntersect=lower.x;if(upper.y<yComp)edge->yUpper=upper.y-1;elseedge->yUpper=upper.y;insertEdge(edges[lower.y],edge);}void buildEdgeList(int cnt,dePt *pts,Edge *edges[]){Edge *edge;dePt v1,v2;int i,yPrev=pts[cnt-2].y;v1.x=pts[cnt-1].x;v1.y=pts[cnt-1].y;for(i=0;i<cnt;i++){v2=pts[i];if(v1.y!=v2.y){edge=(Edge *)malloc(sizeof(Edge));if(v1.y<v2.y)makeEdgeRec(v1,v2,yNext(i,cnt,pts),edge,edges);elsemakeEdgeRec(v2,v1,yPrev,edge,edges);}yPrev=v1.y;v1=v2;}}void buildActiveList(int scan,Edge *active,Edge *edges[]) {Edge *p,*q;p=edges[scan]->next;while(p){q=p->next;insertEdge(active,p);p=q;}}void fillScan(int scan,Edge *active){Edge *p1,*p2;int i;p1=active->next;while(p1){p2=p1->next;for(i=p1->xIntersect;i<p2->xIntersect;i++)fill((int)i,scan,3);p1=p2->next;}}void deleteAfter(Edge *q){Edge *p=q->next;q->next=p->next;free(p);}void updateActiveList(int scan,Edge *active) {Edge *q=active, *p=active->next;while(p)if(scan>=p->yUpper){p=p->next;deleteAfter(q);}else{p->xIntersect=p->xIntersect+p->dxPerScan; q=p;p=p->next;}}void resortActiveList(Edge *active){Edge *q,*p=active->next;active->next=NULL;while(p){q=p->next;insertEdge(active,p);p=q;}}void scanFill(int cnt,dePt *pts){Edge *edges[1024],*active;int i,scan;for(i=0;i<1024;i++){edges[i]=(Edge *)malloc(sizeof(Edge)); edges[i]->next=NULL;}buildEdgeList(cnt,pts,edges);active=(Edge *)malloc(sizeof(Edge)); active->next=NULL;for(scan=0;scan<1024;scan++)buildActiveList(scan,active,edges);if(active->next){fillScan(scan,active);updateActiveList(scan,active);resortActiveList(active);}}}void ChangeSize(GLsizei w,GLsizei h){GLfloat nRange=400.0f;if(h==0) h=1;glViewport(0,0,w,h);glMatrixMode(GL_PROJECTION);glLoadIdentity();if(w<=h)glOrtho(-nRange,nRange,-nRange*h/w,nRange*h/w,-nRange,nRange);elseglOrtho(-nRange*h/w,nRange*h/w,-nRange,nRange,-nRange,nRange); glMatrixMode(GL_MODELVIEW);glLoadIdentity();}void Display(void){glClear(GL_COLOR_BUFFER_BIT);glLineWidth(5.0);int n,x,y,i;cout<<"请输入多边形顶点数："<<endl;cin>>n;dePt *t=new dePt[n];for(i=0;i<n;i++){cout<<"请输入第"<<i+1<<"个顶点坐标"<<endl;cin>>x>>y;t[i].x=x;t[i].y=y;glVertex2i(t[i].x,t[i].y);} glEnd();glFlush();scanFill(n,t);glFlush();}void SetupRC()glClearColor(1.0f,1.0f,1.0f,1.0f); glColor3f(1.0f,0.0f,0.0f);}实验结果：。

实验报告（种子填充算法）一、实验目的熟悉种子填充算法，并编写程序实现。

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

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

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

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

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

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

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

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

一般来说，八向连通算法可以填充四向连通区域，而四向连通算法有时不能填充八向连通区域。

四向连通填充算法:1、初始化种子点栈。

置种子点栈为空栈，并将给定的种子点入栈；2、出栈。

若种子点栈为空，算法结束；否则，取栈顶元素（x,y ）为种子点；3、区域填充。

从种子点（x,y ）开始沿着坐标为y 的当前扫描线向左右两个方向逐像素进行填色，其颜色值置为F_color ，直至到达区域边界。

分别以left x 和right x 表示该填充区段两端点的横坐标；4、新种子点入栈。

分别确定当前扫描线上、下相邻的两条扫描线上位于区段[]right left x x ,内的区域内的区段。

若这些区段内的像素点颜色值为F_color 或B_color ，则转至2；否则以区段内的右端点为种子点入种子点栈，再转至2。

四向连通填充方法可以用递归函数实现如下：void BoundaryFill4(int x, int y, long FilledColor, long BoundaryColor){long CurrentColor;CurrentColor = GetPixelColor(x,y);if (CurrentColor != BoundaryColor && CurrentColor != FilledColor){SetColor(FilledColor);SetPixel (x,y);BoundaryFill4(x+1, y, FilledColor, BoundaryColor);BoundaryFill4(x-1, y, FilledColor, BoundaryColor);BoundaryFill4(x, y+1, FilledColor, BoundaryColor);BoundaryFill4(x, y-1, FilledColor, BoundaryColor);}}三、实验程序#include <graphics.h>#include <math.h>#include <conio.h>#include <vector>using namespace std;vector<int> x_vector;vector<int> y_vector;void ScanLineFill4 ( int x, int y, int oldcolor, int newcolor){int xl, xr,ox,oy;//扫描线的左边界和右边界,or,oy是x,y点的备份bool spanNeedFill;//将来用于标记，是否有需要填充的点，在扫描的时候x_vector.push_back(x); y_vector.push_back(y);//出栈while (!x_vector.empty()){//y = pt.y; x = pt.x;//x，y是处理的目标点y=y_vector.back(); oy = y; y_vector.pop_back();x=x_vector.back(); ox=x; x_vector.pop_back();while (getpixel (x,y) == oldcolor)// 从种子点开始向右填充{putpixel (x, y, newcolor);x ++;}xr = x -1;//右边界以确定x = ox - 1;//更新x为种子点的左边一个点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)// 把这个需要填充的点入栈{x_vector.push_back(x-1); y_vector.push_back(y);spanNeedFill = FALSE;}while ((getpixel (x, y) != oldcolor) && (x < xr)) //继续向右搜索，为了快速不需要填充的点用这个while循环还跳过x ++;} // 上一条扫描线上检查完毕x = xl; y = y - 2; // 处理下面一条扫描线，种子点是左边界下面那个点while (x < xr){spanNeedFill = FALSE;while (getpixel (x, y) == oldcolor)//向右检查{spanNeedFill = TRUE; x ++;}if (spanNeedFill)//遇到需要填充的点就入栈{x_vector.push_back(x-1); y_vector.push_back(y);spanNeedFill = FALSE;}while ((getpixel (x,y) != oldcolor) && (x < xr))//下载开始之前，先跳过，不需要填充的点，加快速度x ++;}}}int customCode(int argc,char** argv){line(312,20,20,320);line(20,320,500,400);line(500,400,610,300);line(610,300,48,56);line(48,56,312,20);ScanLineFill4(312,200,BLACK,RED);return 0;}int main(int argc,char** argv){int code;int gdriver = DETECT,gmode;initgraph(&gdriver, &gmode, " ");//初始化,窗口大小为639*479cleardevice();//清屏setbkcolor(BLACK);//背景色setcolor(WHITE);//图形色code = customCode(argc,argv);//用户代码getch();//暂停程序closegraph();//退出图形库return code;}/*可用颜色BLACK 0 黑色BLUE 1 蓝色GREEN 2 绿色CYAN 3 青红色RED 4 红色MAGENTA 5 紫红色BROWN 6 棕色LIGHTGRAY 7 浅灰色DARKGRAY 8 深灰色LIGHTBLUE 9 浅兰色LIGHTGREEN 10 浅绿色LIGHTCYAN 11 浅青色LIGHTRED 12 浅红色LIGHTMAGENTA 13 浅紫色YELLOW 14 黄色WHITE 15 白色*/四、测试结果五、实验总结上述算法的优点是非常简单，缺点是需要大量栈空间来存储相邻的点。

一、实验目标1)通过实验，进一步了解和掌握几种常用多边形种子填充算法的基本原理2)熟练掌握种子填充算法和区域图案填充的基本过程3)掌握在C/C++环境下用多边形种子填充算法编程实现指定多边形的填充二、实验内容一、实验内容1. 在给定的程序模板中添加递归种子填充、简单种子填充、扫描线种子填充，区域图案填充的功能，生成新的程序窗口中要有递归种子填充、简单种子填充、扫描线种子填充，区域图案填充的菜单按钮，点击按钮分别出现递归种子填充、简单种子填充、扫描线种子填充，区域图案填充的窗口，点击鼠标左键实现在窗口任意位置填充；2. 在理解递归种子填充、简单种子填充、扫描线种子填充，区域图案填充的原理，使用VC实现递归种子填充、简单种子填充、扫描线种子填充，区域图案填充程序的编写，并最终在MFC上演示出来。

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

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

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

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

1.递归种子填充算法原理种子填充算法是区域填充的一种重要基本方法，它假设在多边形内有一像素已知，由此出发利用连通性找到区域内的所有像素。

递归种子填充算法的基本思想：设（x，y）是内点表示的一区域G内的一点，先取（x，y）点为种子点，测试其颜色，若不等于边界颜色，说明是区域内一点，则将其置为新的颜色newcolor，否则说明该点不在区域G内，则停止填充；然后将该点周围的四个点（四连通）或八个点（八连通）作为新的种子点进行同样的处理，通过这种扩散完成对整个区域的填充。

2.简单种子填充算法原理简单种子填充算法，其基本思想：从多边形区域的一个内点开始，由内向外用给定的颜色画点知道边界颜色为止。

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