(计算机图形学)多边形区域扫描线填充或种子填充

基于扫描种⼦线算法的多边形区域填充实现 本学期算法课上我们学习了计算⼏何的基础内容，在课后的深⼊了解学习中我发现，计算⼏何仅仅是算法世界⼀个重要分⽀——计算机图形学的基础部分之⼀，计算机图形学还有很多其他⾮常有趣的算法，例如直线⽣成、圆⽣成、椭圆⽣成。

⽽在本学期进⾏java项⽬实践的过程中，我也遇到了⼀个和计算机图形学息息相关的问题，那就是如何实现windows⾃带画图软件中的⼯具油漆桶？⽹上的开源画图代码基本上均只实现了其他简单的绘制⼯具。

为此，在查阅⼤量相关资料后，我学习到，种⼦填充算法可以很好地实现多边形区域填充，并⽤其中效果最好的基于栈的扫描线种⼦填充算法实现了画板中的油漆桶⼯具。

找到特定的算法，搞懂原理并写出算法的程序代码，在这个过程中，我深刻地认识到了算法的⽆处不在，也深切地感受到算法的乐趣，感受到⽤算法解决问题后的成就感。

简要介绍下算法的原理，实现⾮⽮量图形区域填充常⽤的种⼦填充算法根据对图像区域边界定义⽅式以及对点的颜⾊修改⽅式不同可分为注⼊填充算法（Flood Fill Algorithm）和边界填充算法（Boundary Fill Algorithm）。

两者的核⼼都是递归加搜索，即从指定的种⼦点开始，向上、下、左、右、左上、左下、右上和右下全部⼋个⽅向上搜索，逐个像素进⾏处理，直到遇到边界。

两者的区别仅在于Flood Fill Algorithm不强调区域的边界，它只是从指定位置开始，将所有联通区域内某种指定颜⾊的点都替换成另⼀种颜⾊，即实现颜⾊替换的功能；⽽边界填充算法与注⼊填充算法递归的结束条件不⼀样，Boundary Fill Algorithm强调边界的存在，只要是边界内的点，⽆论是什么颜⾊，都替换成指定的颜⾊。

但是在实际项⽬中，使⽤递归算法效率太低，为了消除递归，有⼀种更为常⽤的改进算法，即扫描线种⼦填充算法。

它通过沿竖直扫描线填充像素段，⼀段⼀段地来处理8-联通的相邻点，这样算法处理过程中就只需要将每个竖直像素段的起始点位置压⼊⼀个特殊的栈，⽽不需要像递归算法那样将当前位置周围尚未处理的所有相邻点都压⼊堆栈，从⽽节省了堆栈空间，本实例采⽤的就是结合泛洪填充算法（或者说注⼊填充算法）的扫描线种⼦填充算法。

实验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， 扫描线填充算法⑴ 多边形分为凸多边形、凹多边形、含内环的多边形。

① 凸： ② 凹③ 含内环 任意两顶点间的 任意两顶点间的连线均在多边形 连线有不在多边内 形内的部分a) 基本思想：i. 按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。

b) 对于一条扫描线填充过程可以分为四个步骤：i.（1）求交（2）排序 ii.（3）配对（4）填色12345678② 步骤· 求交：计算扫描线与多边形各边的交点；· 排序：把所有交点按x 值递增顺序排序；· 配对：12，34，…，交点两两配对；· 填色：把交点对的象素置成多边形颜色，把交点对以外的象素置成背景色。

③ 活性边表算法：处理每一条扫描线时，仅计算和它相交的多边形的边· 活性边：当前扫描线与多边形相交的边；· 活性边表：存放扫描线与活性边交点(按X 递增顺序)的一张链表；8节点：第1项存当前扫描线与边的交点坐标x 值；第2项存从当前扫描线到下一条扫描线间x 的增量∆x ；第3项存边所交的扫描线的y max④ 算法· 增量法：令当前扫描线与多边形某一条边的交点的x 坐标为x ，则下一条扫描线与该边的交点不要重计算，只要加一个增量。

该边的直线方程为：ax+by+c=0；若y ＝y i ，x=x i ；则当y = y i+1时，x a b y c x b ai i i i ++=-⋅-=-111(); 其中∆x b a=- 为常数， · 算法过程polyfill (polygon, color)int color;多边形定义 polygondef ;{ for (各条扫描线i ){ 初始化新边表头指针NET [i]；把y min = i 的边放进边表NET [i]; }y = 最低扫描线号；初始化活性边表AET 为空；for (各条扫描线i ){ 把新边表NET [i] 中的边结点用插入排序法插入AET表，使之按x坐标递增顺序排列；遍历AET表，把配对交点区间(左闭右开)上的象素(x, y)，用drawpixel (x, y, color) 改写象素颜色值；遍历AET表，把y max= i 的结点从AET表中删除，并把y max > i 结点的x值递增 x；若允许多边形的边自相交，则用冒泡排序法对AET表重新排序；}} /* polyfill */⑤问题及其求解问题1：扫描线与多边形顶点相交，交点的取舍。

实验二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("请在空心字体内部单击鼠标左键!","提示");}四、实验结果截图。

贵州大学计算机图形学实验报告学院：计算机科学与信息学院专业：软件工程班级：反映）根据扫描线的连贯性可知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的内部点。

所以，对所有的扫描线填充入点到出点之间的点就可填充多边形。

如何具体实现（如何找到入点、出点）？根据区域的连贯性，分为3个步骤：(1)求出扫描线与多边形所有边的交点；(2)把这些交点按x坐标值以升序排列；(3)对排序后的交点进行奇偶配对，对每一对交点间的区域进行填充。

步骤(3)如上图：对y＝8的扫描线，对交点序列按x坐标升序排序得到的交点序列是(2,4,9,13)，然后对交点2与4之间、9与13之间的所有象素点进行填充。

求交点、排序、配对、填色利用链表：与当前扫描线相交的边称为活性边(Active Edge)，把它们按与扫描线交点x坐标递增的顺序存入一个链表中，称为活性边表AEL (AEL， Active Edge List)。

它记录了多边形边沿扫描线的交点序列。

AEL中每个对象需要存放的信息：ymax：边所交的最高扫描线；x：当前扫描线与边的交点；Δx：从当前扫描线到下一条扫描线之间的x增量next：指向下一对象的指针。

伪码：建立ET，置y为ET中非空桶的最小序号；置AEL表为空，且把y桶中ET表的边加入AEL表中；while AEL表中非空do begin对AEL表中的x、Δx按升序排列；按照AEL表中交点前后次序，在每对奇偶交点间的x段予以填充；计算下一条扫描线：y=y+1；if 扫描线y=ymax then 从AEL表中删除这些边；对在AEL表中的其他边，计算与下一条扫描线的交点：x=x +Δx 按照扫描线y值把ET表中相应桶中的边加入AEL表中；endend of algorithm二、区域填充算法：区域可采用两种表示形式:内点表示枚举区域内部的所有像素；内部的所有像素着同一个颜色；边界像素着不同的颜色。

边界表示：枚举出边界上所有的像素；边界上的所有像素着同一颜色；内部像素着不同的颜色。

计算机科学与技术学院2013－2014学年第一学期《计算机图形学》实验报告班级：学号：姓名：教师：成绩：实验项目（2、多边形的扫描转换与区域填充）一、实验目的与要求（1）了解多边形扫描转换的各种算法，掌握多边形的扫描转换与区域填充算法。

（2）进一步掌握在VC集成环境中实现图形算法的方法与过程。

二、实验内容设计菜单程序，利用消息处理函数，完成以下要求：（1）给出凸多边形的若干顶点（3 ~ 5个），实现多边形的“x扫描算法”。

（2）实现种子填充，泛填充算法（四邻法）。

（3）设计程序，实现判断一个点是否在多边形区域内部。

三、重要算法分析（一）边界表示的四连通区域种子填充算法此方法的基本思想是，从多边形内部任一像素出发，按照“左上右下”的顺序判断相邻像素，若不是边界像素且没有被填充过，则对其填充，并且重复上述过程，直到所有像素填充完毕。

(1)从种子点出发，向左判断多边形内部颜色，如果不是填充颜色并且不是边界颜色，则填充，直到遇到边界为止。

(2)从种子点出发，向右判断多边形内部颜色，如果不是填充颜色并且不是边界颜色，则填充，直到遇到边界为止。

(3)将种子点的坐标y值上移一个像素，重复步骤（1）、（2）直到遇到上面边界为止。

(4)将种子点的坐标y值下移一个像素，重复步骤（1）、（2）直到遇到上面边界为止。

（二）判断一个点是否在多边形内部解决方案是将测试点的y坐标与多边形的每一个点进行比较，我们会得到一个测试点所在的行与多边形边的交点的列表。

如果测试点的两边点的个数都是奇数个则该测试点在多边形内，否则在多边形外。

如图1所示，判断点（红点）y值左边与多边形有5个交点，右边与多边形有3个交点，则该点在多边形内部。

图1如图2所示，判断点（红点）y值左边与多边形有2个交点，右边与多边形有2个交点，则该点在多边形外部。

图2但是有一种特殊情况须特别处理一下，当与多边形顶点相交时，需要将改点计算为两个交点，如图3所示：图3四、程序运行截图1.种子四连通域填充法，如图4所示。

算法系列之⼗⼆：多边形区域填充算法－－扫描线种⼦填充算法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）步，就是从当前扫描线的上⼀条扫描线和下⼀条扫描线中寻找新的种⼦点。

实验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);}实验结果：。

2007-11-06 16:20 区域填充的扫描线算法(C源程序)-------计算机图形学实验/** 区域填充的扫描线算法* (适合用于内点表示的4连通区域)*算法的基本过程：* 当给定种子点(x,y)时，首先填充种子点所在的扫描线上的位于给定区域的*一个区段，然后确定与这一区段连通的上下两条扫描线上位于给定区域的区段，并*依次保存下来。

反复这个过程，直到填充结束.** 操作系统: Windows XP* 运行环境：Win-TC* 作者：范雷* 时间: 2007.10.27*/#include "Conio.h"#include "graphics.h" /*for initgr()*/#include "stdio.h" /*for NULL */#define closegr closegraphvoid initgr(void) /* BGI初始化*/{int gd = DETECT, gm = 0; /* 和gd = VGA,gm = VGAHI是同样效果*/ registerbgidriver(EGA VGA_driver);/* 注册BGI驱动后可以不需要.BGI文件的支持运行*/ initgraph(&gd, &gm, "");}enum BOOL{FALSE = 0, TRUE = 1};typedef struct{int y;int xLeft;int xRight;}Span;/*区段*/typedef struct stacknode{Span span;struct stacknode *next;}stacknode;typedef struct{stacknode *top;}linkstack;/*-----------------进栈操作----------------------------------------*/void PushStack(linkstack *s, Span *span)stacknode *p=(stacknode*)malloc(sizeof(stacknode));p->span.y = span->y;p->span.xLeft = span->xLeft;p->span.xRight = span->xRight;p->next=s->top;s->top=p;}/*-----------------出栈操作------------------------------------------*/ void PopStack(linkstack *s,Span *span){int x;stacknode *p=s->top;span->y = p->span.y;span->xLeft = p->span.xLeft;span->xRight = p->span.xRight;s->top=p->next;free(p);}/*-----------------将栈清空------------------------------------------*/ void SetStackEmpty(linkstack *s){stacknode *p=s->top;while( s->top != NULL){free(p);s->top=p->next;}}/*--------------判断栈是否为空----------------------------------------*/ int IsStackEmpty(linkstack *s){if(s->top == NULL)return 1;elsereturn 0;}/*----------------核心程序开始----------------------------------------*/ void ScanLineFill4(int x,int y,int oldColor,int newColor){int xLeft,xRight;int i;enum BOOL isLeftEndSet, spanNeedFill;Span span;linkstack *s=(linkstack*)malloc(sizeof(linkstack));s->top = NULL;/*填充并确定种子点(x,y)所在的区段*/i = x;while(getpixel(i,y) == oldColor)/*向右填充*/{putpixel(i,y,newColor);i++;}span.xRight = i - 1; /*确定区段右边界*/i = x - 1;while(getpixel(i,y) == oldColor)/*向左填充*/{putpixel(i,y,newColor);i--;}span.xLeft = i + 1; /*确定区段左边界*//*初始化*/SetStackEmpty(s);span.y = y;PushStack(s,&span);/*将前面生成的区段压入堆栈*/while( ! IsStackEmpty(s) )/*终止判断*/{/*出栈*/PopStack(s, &span);/*处理上面扫描线*/y = span.y + 1;xRight = span.xRight;i = span.xLeft - 1;isLeftEndSet = FALSE;while(getpixel(i,y) == oldColor)/*向左填充*/{putpixel(i, y, newColor);i--;}if( i != span.xLeft - 1)/*确定区段左边界*/{isLeftEndSet = TRUE;xLeft = i + 1;}i = span.xLeft;while( i < xRight){spanNeedFill = FALSE;while(getpixel(i,y) == oldColor) /*向右填充*/{if( ! spanNeedFill){spanNeedFill = TRUE;if( ! isLeftEndSet){isLeftEndSet = TRUE;xLeft = i;}}putpixel(i,y,newColor);i++;}if( spanNeedFill ){span.y = y;span.xLeft = xLeft;span.xRight = i - 1;PushStack(s, &span); /*将区段压入堆栈*/isLeftEndSet = FALSE;spanNeedFill = FALSE;}/* while(getpixel(i,y) != oldColor) */i++;}/*end of while( i < xRight) *//*处理下面一条扫描线,与处理上面一条扫描线完全类似*/ y = y - 2;xRight = span.xRight;i = span.xLeft - 1;isLeftEndSet = FALSE;while(getpixel(i,y) == oldColor)/*向左填充*/{putpixel(i, y, newColor);i--;}if( i != span.xLeft - 1)/*确定区段左边界*/{isLeftEndSet = TRUE;xLeft = i + 1;}i = span.xLeft;while( i < xRight){spanNeedFill = FALSE;while(getpixel(i,y) == oldColor) /*向右填充*/{if( ! spanNeedFill){spanNeedFill = TRUE;if( ! isLeftEndSet){isLeftEndSet = TRUE;xLeft = i;}}putpixel(i,y,newColor);i++;}if( spanNeedFill ){span.y = y;span.xLeft = xLeft;span.xRight = i - 1;PushStack(s, &span); /*将区段压入堆栈*/isLeftEndSet = FALSE;spanNeedFill = FALSE;}/* while(getpixel(i,y) != oldColor) */i++;}/*end of while( i < xRight) */delay(2000); /*延时*/}/*end of while( ! isStackEmpty() ) */}/*end of ScanLineFill4() *//*---------------------main()------------------------------------------*/ int main(){initgr(); /* BGI初始化*/setbkcolor(3);setcolor(5);moveto(50, 50); /*绘制4连通区域*/lineto(400, 50);lineto(400,300);lineto(150,300);lineto(150,400);lineto(50, 400);lineto(50, 50);ScanLineFill4(150,150,0,14); /*相与后oldColor == 0*/getch(); /* 暂停一下，看看前面绘图代码的运行结果*/ closegr(); /* 恢复TEXT屏幕模式*/return 0;。

实验一 多边形彩色填充一、实验目的学习并掌握Y-X 扫描线算法掌握基于 Win32、Visual C++环境下MFC 编程绘制图形二、实验原理1. 对任一条扫描线，确定该扫描线与多边形边的交点位置，自左向右存储，并对每对内部交点间的帧缓存填写指定颜色2.算法步骤3.扫描线链表123456784. 边表ET ：初始化时建立全局边表（ET）,包含多边形所有边，按边端点的ymin排序存放。

即：若该边的下端点为ymin，则该边就放在扫描线ymin对应的链表中。

每条扫描线交的多边形的边按其下端点的x坐标增序排列。

5. 活跃边表AET：与当前扫描线相交的边称为活性边，按与扫描线交点x坐标递增的顺序存放在一个链表中，称此链表为活性边表(AET)三、实验关键代码CPolyFill::CPolyFill(){m_pEDGEs = NULL;m_pET = NULL;m_pAET = NULL;MinY = 10000;MaxY = -1;MinX = 10000;MaxX = -1;}CPolyFill::~CPolyFill(){if(m_pEDGEs) delete[] m_pEDGEs;if(m_pET) delete[] m_pET;if(m_pAET) delete[] m_pAET;}// 统计多边形各条边的信息，生成Edge结构。

void CPolyFill::BuildEDGEs(){if(m_pEDGEs){delete[] m_pEDGEs; m_pEDGEs = NULL;}m_pEDGEs = new EDGE[m_PtNum];for(int i = 0; i < m_PtNum-1; i++){if (m_Pts[i].y > m_Pts[i+1].y){m_pEDGEs[i].Up = m_Pts[i];m_pEDGEs[i].Down = m_Pts[i+1];}else{m_pEDGEs[i].Up = m_Pts[i+1];m_pEDGEs[i].Down = m_Pts[i];}m_pEDGEs[i].EG.Ymax = m_pEDGEs[i].Up.y ;m_pEDGEs[i].EG.X = m_pEDGEs[i].Down.x;m_pEDGEs[i].EG.Dx = double((m_pEDGEs[i].Up.x - m_pEDGEs[i].Down.x))/(m_pEDGEs[i].Up.y - m_pEDGEs[i].Down.y);}if (m_Pts[0].y > m_Pts[m_PtNum-1].y){m_pEDGEs[m_PtNum-1].Up = m_Pts[0];m_pEDGEs[m_PtNum-1].Down = m_Pts[m_PtNum-1];}else{m_pEDGEs[m_PtNum-1].Up = m_Pts[m_PtNum-1];m_pEDGEs[m_PtNum-1].Down = m_Pts[0];}m_pEDGEs[m_PtNum-1].EG.Ymax = m_pEDGEs[m_PtNum-1].Up.y ;m_pEDGEs[m_PtNum-1].EG.X = m_pEDGEs[m_PtNum-1].Down.x;m_pEDGEs[m_PtNum-1].EG.Dx = double((m_pEDGEs[m_PtNum-1].Up.x - m_pEDGEs[m_PtNum-1].Down.x))/(m_pEDGEs[m_PtNum-1].Up.y - m_pEDGEs[m_PtNum-1].Down.y);}void CPolyFill::Polygon(CPoint *pts, int cnt){m_Pts = pts;m_PtNum = cnt;BuildEDGEs(); // 计算出每条多边形边的斜率，Ymax, Xmin等。