案例10 扫描线种子填充算法

扫描线算法（S c a n-L i n e F i l l i n g）扫描线算法适合对矢量图形进行区域填充，只需要直到多边形区域的几何位置，不需要指定种子点，适合计算机自动进行图形处理的场合使用，比如电脑游戏和三维CAD软件的渲染等等。

对矢量多边形区域填充，算法核心还是求交。

《计算几何与图形学有关的几种常用算法》一文给出了判断点与多边形关系的算法――扫描交点的奇偶数判断算法，利用此算法可以判断一个点是否在多边形内，也就是是否需要填充，但是实际工程中使用的填充算法都是只使用求交的思想，并不直接使用这种求交算法。

究其原因，除了算法效率问题之外，还存在一个光栅图形设备和矢量之间的转换问题。

比如某个点位于非常靠近边界的临界位置，用矢量算法判断这个点应该是在多边形内，但是光栅化后，这个点在光栅图形设备上看就有可能是在多边形外边（矢量点没有大小概念，光栅图形设备的点有大小概念），因此，适用于矢量图形的填充算法必须适应光栅图形设备。

2.1扫描线算法的基本思想扫描线填充算法的基本思想是：用水平扫描线从上到下（或从下到上）扫描由多条首尾相连的线段构成的多边形，每根扫描线与多边形的某些边产生一系列交点。

将这些交点按照x坐标排序，将排序后的点两两成对，作为线段的两个端点，以所填的颜色画水平直线。

多边形被扫描完毕后，颜色填充也就完成了。

扫描线填充算法也可以归纳为以下4个步骤：（1）求交，计算扫描线与多边形的交点（2）交点排序，对第2步得到的交点按照x值从小到大进行排序；（3）颜色填充，对排序后的交点两两组成一个水平线段，以画线段的方式进行颜色填充；（4）是否完成多边形扫描？如果是就结束算法，如果不是就改变扫描线，然后转第1步继续处理；整个算法的关键是第1步，需要用尽量少的计算量求出交点，还要考虑交点是线段端点的特殊情况，最后，交点的步进计算最好是整数，便于光栅设备输出显示。

对于每一条扫描线，如果每次都按照正常的线段求交算法进行计算，则计算量大，而且效率底下，如图（6）所示：图（6）多边形与扫描线示意图观察多边形与扫描线的交点情况，可以得到以下两个特点：（1）每次只有相关的几条边可能与扫描线有交点，不必对所有的边进行求交计算；（2）相邻的扫描线与同一直线段的交点存在步进关系，这个关系与直线段所在直线的斜率有关；第一个特点是显而易见的，为了减少计算量，扫描线算法需要维护一张由“活动边”组成的表，称为“活动边表（AET）”。

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

二、实验内容用种子填充算法和扫描线填充算法等任意两种算法实现指定多边形的区域填充。

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

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

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

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

四向连通填充算法：a）种子像素压入栈中；b）如果栈为空，则转e)；否则转c)；c）弹出一个像素，并将该像素置成填充色；并判断该像素相邻的四连通像素是否为边界色或已经置成多边形的填充色，若不是，则将该像素压入栈；d）转b）；e）结束。

扫描线填充算法的基本过程如下：当给定种子点(x,y)时，首先填充种子点所在扫描线上的位于给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。

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

区域填充的扫描线算法可由下列四个步骤实现：(1)初始化：堆栈置空。

将种子点(x,y)入栈。

(2)出栈：若栈空则结束。

否则取栈顶元素(x,y)，以y作为当前扫描线。

(3)填充并确定种子点所在区段：从种子点(x,y)出发，沿当前扫描线向左、右两个方向填充，直到边界。

分别标记区段的左、右端点坐标为xl和xr。

(4)并确定新的种子点：在区间[xl，xr]中检查与当前扫描线y上、下相邻的两条扫描线上的象素。

若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。

四、实验步骤1.复习有关算法，明确实验目的和要求；2.依据算法思想，绘制程序流程图（指定填充多边形）；3.设计程序界面，要求操作方便；4.用C/C++语言编写源程序并调试、执行（最好能用动画显示填充过程）；5.分析实验结果6.对程序设计过程中出现的问题进行分析与总结；7.打印源程序或把源程序以文件的形式提交；8.按格式要求完成实验报告。

扫描线算法（Scan-Line F illing）扫描线算法适合对矢量图形进行区域填充，只需要直到多边形区域的几何位置，不需要指定种子点，适合计算机自动进行图形处理的场合使用，比如电脑游戏和三维CAD软件的渲染等等。

对矢量多边形区域填充，算法核心还是求交。

《计算几何与图形学有关的几种常用算法》一文给出了判断点与多边形关系的算法――扫描交点的奇偶数判断算法，利用此算法可以判断一个点是否在多边形内，也就是是否需要填充，但是实际工程中使用的填充算法都是只使用求交的思想，并不直接使用这种求交算法。

究其原因，除了算法效率问题之外，还存在一个光栅图形设备和矢量之间的转换问题。

比如某个点位于非常靠近边界的临界位置，用矢量算法判断这个点应该是在多边形内，但是光栅化后，这个点在光栅图形设备上看就有可能是在多边形外边（矢量点没有大小概念，光栅图形设备的点有大小概念），因此，适用于矢量图形的填充算法必须适应光栅图形设备。

2.1扫描线算法的基本思想扫描线填充算法的基本思想是：用水平扫描线从上到下（或从下到上）扫描由多条首尾相连的线段构成的多边形，每根扫描线与多边形的某些边产生一系列交点。

将这些交点按照x坐标排序，将排序后的点两两成对，作为线段的两个端点，以所填的颜色画水平直线。

多边形被扫描完毕后，颜色填充也就完成了。

扫描线填充算法也可以归纳为以下4个步骤：（1）求交，计算扫描线与多边形的交点（2）交点排序，对第2步得到的交点按照x值从小到大进行排序；（3）颜色填充，对排序后的交点两两组成一个水平线段，以画线段的方式进行颜色填充；（4）是否完成多边形扫描？如果是就结束算法，如果不是就改变扫描线，然后转第1步继续处理；整个算法的关键是第1步，需要用尽量少的计算量求出交点，还要考虑交点是线段端点的特殊情况，最后，交点的步进计算最好是整数，便于光栅设备输出显示。

对于每一条扫描线，如果每次都按照正常的线段求交算法进行计算，则计算量大，而且效率底下，如图（6）所示：图（6）多边形与扫描线示意图观察多边形与扫描线的交点情况，可以得到以下两个特点：（1）每次只有相关的几条边可能与扫描线有交点，不必对所有的边进行求交计算；（2）相邻的扫描线与同一直线段的交点存在步进关系，这个关系与直线段所在直线的斜率有关；第一个特点是显而易见的，为了减少计算量，扫描线算法需要维护一张由“活动边”组成的表，称为“活动边表（AET）”。

python扫描线填充算法详解本⽂实例为⼤家分享了python扫描线填充算法，供⼤家参考，具体内容如下介绍1.⽤⽔平扫描线从上到下扫描由点线段构成的多段构成的多边形。

2.每根扫描线与多边形各边产⽣⼀系列交点。

将这些交点按照x坐标进⾏分类，将分类后的交点成对取出，作为两个端点，以所填的⾊彩画⽔平直线。

3.多边形被扫描完毕后，填⾊也就完成。

数据结构活性边表：新边表：代码（使⽤数组）import numpy as npfrom PIL import Imagefrom PIL import ImageDrawfrom PIL import ImageFontarray = np.ndarray((660, 660, 3), np.uint8)array[:, :, 0] = 255array[:, :, 1] = 255array[:, :, 2] = 255for i in range(0,660,1):array[i,330]=(0,0,0)for j in range(0,660,1):array[330,j]=(0,0,0)def creat_Net(point, row, y_min,y_max ):Net = [([ ] * y_max ) for i in range(y_max )]point_count = point.shape[0]for j in range(0, point_count):x = np.zeros(10)first = int(min(point[(j+1)%point_count][1] , point[j][1]))x[1] = 1/((point[(j+1)%point_count][1]-point[j][1])/(point[(j+1)%point_count][0]-point[j][0])) # x 的增量 x[2] = max(point[(j+1)%point_count][1] , point[j][1])if(point[(j+1)%point_count][1] < point[j][1]):x[0] = point[(j+1)%point_count][0]else:x[0] = point[j][0]Net[first].append(x)return Netdef draw_line(i,x ,y ):for j in range(int(x),int(y)+1):array[330-i,j+330]=(20,20,20)def polygon_fill(point):y_min = np.min(point[:,1])y_max = np.max(point[:,1])Net = creat_Net(point, y_max - y_min + 1, y_min, y_max)x_sort = [] * 3for i in range(y_min, y_max):x = Net[i]if(len(x) != 0):for k in x :x_sort.append(k)x_image = [] * 3for cell in x_sort:x_image.append(cell[0])x_image.sort()if(len(x_image) >= 3 and x_image[0]==x_image[1] and x_image[2]>x_image[1]):x_image[1] = x_image[2]draw_line(i, x_image[0], x_image[1])linshi = [] * 3for cell in x_sort:if cell[2] > i:cell[0] += cell[1]linshi.append(cell)x_sort = linshi[:]x_image = [] * 3for cell in x_sort:x_image.append(cell[0])x_image.sort()draw_line(i, x_image[0],x_image[1])def main():point = [[55,40], [100,80], [100,160],[55,180], [10,160], [10,80]]point = np.array(point)polygon_fill( point )image = Image.fromarray(array)image.save('saomao.jpg')image.show()if __name__ == "__main__":main()实例：以上就是本⽂的全部内容，希望对⼤家的学习有所帮助，也希望⼤家多多⽀持。

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

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

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

扫描线区域填充算法算法步骤如下：1.找到图形区域的上下边界：-遍历图形的所有边界点，找到最大纵坐标和最小纵坐标，确定扫描线的上下边界。

2.初始化扫描线列表：-从上到下依次生成扫描线，建立一个扫描线列表。

3.计算扫描线与图形的交点：-遍历扫描线列表中的每个扫描线，与图形的所有边界进行求交。

-如果与边界有交点，将交点的横坐标存入一个集合中，集合中的数据按从小到大排序。

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

扫描线区域填充算法算法步骤如下：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);}}。

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;。

种子填充算法
填充算法是随机化的有益的近似算法中的经典例子，用它来解决最大问题可以产生出理想的解决方案。

种子填充算法作为该算法的一种，经常被用来解决贪婪的最大化问题或者寻优，在有限的时间内求解传统最大化目标函数的最优解。

种子填充算法是一种常用的函数字符串优化技术，能以有限的步骤实现最大化随机化优化，在计算图形和调度任务中常用种子填充算法。

主要包括：
1.根据求解的问题，选择最优解种子。

种子是随机产生的群体或者求解器方程，用于准确确定最佳参数；
2.利用种子初始化函数字符串，以较小的步骤完成最大化优化，扩展函数字符串；
3.根据优化的状态和步骤，重新选择种子来改变最大化的结果；
4.重复多步优化，可以得到不同的最优解，对于优化准确率很高。

种子填充算法的优势在于准确地得到期望解，比其它采用搜索的近似解决办法更加精确，且由于经过多次记录，每次重播都能产生一样的最优解。

另外，由于每次迭代中用到种子，可以在不影响目标函数的性能情况下改变最终的优化结果。

种子填充算法目前在理论上和实际应用中都得到了广泛的使用，如求解细胞自动机的模拟、排列调度问题、视觉语义地图等，所有这些问题都是可行空间有限，而且受限于时间和空间，在这些情况下种子填充算法可以有效提高解决问题的效率。