计算机图形学常用算法及代码大全(共40页).doc

《计算机图形学常用算法及代码大全(共40页).doc》由会员分享，可在线阅读，更多相关《计算机图形学常用算法及代码大全(共40页).doc（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上2.1.1 生成直线的DDA算法数值微分法即DDA法(Digital Differential Analyzer)，是一种基于直线的微分方程来生成直线的方法。一、直线DDA算法描述：设(x1，y1)和(x2，y2)分别为所求直线的起点和终点坐标，由直线的微分方程得= m =直线的斜率(21)可通过计算由x方向的增量x引起y的改变来生成直线：xi+1=xi+x(22)yi+1=yi+y=yi+xm(23)也可通过计算由y方向的增量y引起x的改变来生成直线：yi+1=yi+y(24)xi+1=xi+x=xi+y/m(25)式(22)至(25)是递推的。二、直线DDA算法思

2、想：选定x2x1和y2y1中较大者作为步进方向(假设x2x1较大)，取该方向上的增量为一个象素单位(x=1)，然后利用式(21)计算另一个方向的增量(y=xm=m)。通过递推公式(22)至(25)，把每次计算出的(xi+1，yi+1)经取整后送到显示器输出，则得到扫描转换后的直线。之所以取x2x1和y2y1中较大者作为步进方向，是考虑沿着线段分布的象素应均匀，这在下图中可看出。另外，算法实现中还应注意直线的生成方向，以决定x及y是取正值还是负值。三、直线DDA算法实现：1、已知直线的两端点坐标：(x1，y1)，(x2，y2)2、已知画线的颜色：color3、计算两个方向的变化量：dx=x2x1

3、 dy=y2y14、求出两个方向最大变化量的绝对值： steps=max(|dx|，|dy|)5、计算两个方向的增量(考虑了生成方向)： xin=dx/steps yin=dy/steps6、设置初始象素坐标：x=x1,y=y17、用循环实现直线的绘制：for(i=1；i0)?static_cast(fNum+0.5):static_cast(fNum-0.5)/*!* brief DDA画线函数* param pDC in窗口DC* param BeginPt in直线起点* param EndPt in直线终点* param LineCor in直线颜色* return 无*/void C

4、DrawMsg:DDA_DrawLine(CDC *pDC,CPoint &BeginPt,CPoint &EndPt,COLORREF LineCor)long YDis = (EndPt.y - BeginPt.y);long XDis = (EndPt.x-BeginPt.x);long MaxStep = max(abs(XDis),abs(YDis); / 步进的步数float fXUnitLen = 1.0f; / X方向的单位步进float fYUnitLen = 1.0f; / Y方向的单位步进fYUnitLen = static_cast(YDis)/static_cast(

5、MaxStep);fXUnitLen = static_cast(XDis)/static_cast(MaxStep);/ 设置起点像素颜色pDC-SetPixel(BeginPt.x,BeginPt.y,LineCor); float x = static_cast(BeginPt.x);float y = static_cast(BeginPt.y);/ 循环步进for (long i = 1;iSetPixel(FloatToInteger(x),FloatToInteger(y),LineCor);2.1.2 生成直线的Bresenham算法从上面介绍的DDA算法可以看到，由于在循环中

6、涉及实型数据的加减运算，因此直线的生成速度较慢。在生成直线的算法中，Bresenham算法是最有效的算法之一。Bresenham算法是一种基于误差判别式来生成直线的方法。一、直线Bresenham算法描述：它也是采用递推步进的办法，令每次最大变化方向的坐标步进一个象素，同时另一个方向的坐标依据误差判别式的符号来决定是否也要步进一个象素。我们首先讨论m=y/x，当0m1且x1x2时的Bresenham算法。从DDA直线算法可知这些条件成立时，公式(2-2)、(2-3)可写成：xi+1=xi+1(26)yi+1=yi+m(27)有两种Bresenham算法思想，它们各自从不同角度介绍了Bresen

7、ham算法思想，得出的误差判别式都是一样的。二、直线Bresenham算法思想之一：由于显示直线的象素点只能取整数值坐标，可以假设直线上第i个象素点坐标为(xi，yi)，它是直线上点(xi，yi)的最佳近似，并且xi=xi(假设md2，说明直线上理论点离(xi+1，yi+1)象素较近，下一个象素点应取(xi+1，yi+1)。(2)当此值为负时，d10，因此pi与(d1-d2)有相同的符号；这里y=y2-y1，m=y/x；c=2y+x(2b-1)。下面对式(2-11)作进一步处理，以便得出误差判别递推公式并消除常数c。将式(2-11)中的下标i改写成i+1，得到：pi+1=2yxi+1-2xyi

8、+1+c(212)将式(2-12)减去(2-11)，并利用xi+1=xi+1，可得：pi+1= pi+2y-2x(yi+1-yi)(213)再假设直线的初始端点恰好是其象素点的坐标，即满足：y1=mx1+b(214)由式(2-11)和式(2-14)得到p1的初始值： p1=2y-x(215)这样，我们可利用误差判别变量，得到如下算法表示：初始 p1=2y-x(216)当pi0时： yi+1=yi+1,xi+1=xi+1，pi+1=pi+2(y-x)否则：yi+1=yi,xi+1=xi+1， pi+1=pi+2y从式(2-16)可以看出，第i+1步的判别变量pi+1仅与第i步的判别变量pi、直线

9、的两个端点坐标分量差x和y有关，运算中只含有整数相加和乘2运算，而乘2可利用算术左移一位来完成，因此这个算法速度快并易于硬件实现。三、直线Bresenham算法思想之二：由于象素坐标的整数性，数学点(xi，yi)与所取象素点(xi，yir)间会引起误差(i)，当xi列上已用象素坐标(xi，yir)表示直线上的点(xi，yi)，下一直线点B(xi+1，yi+1)，是取象素点C(xi+1，yir )，还是D(xi1，y(i+1)r)呢？设A为CD边的中点，正确的选择：若B点在A点上方，选择D点； 否则，选C点。用误差式描述为：(xi+1)=BC-AC=(yi+1-yir)-0.5(28)求递推公式

10、：(xi+2)=(yi+2-y(i+1)r)-0.5 = yi+1+m-y(i+1)r-0.5(29)当(xi+1)0时，选D点，y(i+1)r = yir+1(xi+2)= yi+1+m-yir-1-0.5=(xi+1)+m-1(210)当(xi+1)0时，选C点，y(i+1)r = yir(xi+2)= yi+1+myir-0.5=(xi+1)+m(211)初始时：(xs+1)=BC-AC=m-0.5(212)为了运算中不含实型数，同时不影响不等式的判断，将方程两边同乘一正整数。令方程两边同乘2x，即d=2x，则：初始时：d = 2y-x(213)递推式：当d0时： d=d+2(yx)；y

11、+；x+；否则： d=d+2y；x+； (214)实现代码void Bresenhamline (int x0,int y0,int x1, int y1,int color)int x, y, dx, dy;float k, e;dx = x1-x0, dy = y1- y0, k=dy/dx;e=-0.5, x=x0, y=y0;for (i=0; i=0) y+, e=e-1;或者将e扩大2dx倍；void Bresenhamline (int x0,int y0,int x1, int y1,int color)int x, y, dx, dy;float k, e;dx = x1-x

12、0, dy = y1- y0, k=dy/dx;e=-dx, x=x0, y=y0;for (i=0; i=0) y+, e=e-2dx;四、直线Bresenham算法实现：条件：0m1且x1x21、输入线段的两个端点坐标和画线颜色：x1，y1，x2，y2，color；2、设置象素坐标初值：x=x1，y=y1；3、设置初始误差判别值：p=2y-x；4、分别计算：x=x2-x1、y=y2-y1；5、循环实现直线的生成：for(x=x1；x=0) y=y+1；p=p+2(y-x)；else p=p+2y；五、直线Bresenham算法完善：现在我们修正(2-16)公式，以适应对任何方向及任何斜率线

13、段的绘制。如下图所示，线段的方向可分为八种，从原点出发射向八个区。由线段按图中所示的区域位置可决定xi+1和yi+1的变换规律。容易证明：当线段处于、区时，以|x|和|y|代替前面公式中的x和y，当线段处于、区时，将公式中的|x|和|y|对换，则上述两公式仍有效。在线段起点区分线段方向七、直线Bresenham算法特点：由于程序中不含实型数运算，因此速度快、效率高，是一种有效的画线算法。2.2.2 中点算法生成圆中点画圆算法在一个方向上取单位间隔，在另一个方向的取值由两种可能取值的中点离圆的远近而定。实际处理中，用决策变量的符号来确定象素点的选择，因此算法效率较高。一、中点画圆算法描述设要显示

14、圆的圆心在原点(0，0)，半径为R，起点在(0，R)处，终点在(，)处，顺时针生成八分之一圆，利用对称性扫描转换全部圆。为了应用中点画圆法，我们定义一个圆函数F(x，y)=x2+y2-R2(219)任何点(x，y)的相对位置可由圆函数的符号来检测：F(x，y)0点(x，y)位于数学圆外(220)如下图所示，图中有两条圆弧A和B，假定当前取点为Pi(xi，yi)，如果顺时针生成圆，那么下一点只能取正右方的点E(xi+1，yi)或右下方的点SE(xi+1，yi-1)两者之一。中点画线算法假设M是E和SE的中点，即 ，则：1、当F(M)0时，M在圆外(圆弧B)，表明SE点离圆更近，应取SE点；3、当

15、F(M)=0时，在E点与SE点之中随便取一个即可，我们约定取SE点。 二、中点画圆算法思想因此，我们用中点M的圆函数作为决策变量di，同时用增量法来迭代计算下一个中点M的决策变量di+1。(221)下面分两种情况来讨论在迭代计算中决策变量di+1的推导。1、见图（a），若di0，则选择E点，接着下一个中点就是，这时新的决策变量为：(222)（a）(di0) 中点画线算法式(222)减去(221)得：di+1=di+2xi+3(223)2、见图（b），若di0，则选择SE点，接着下一个中点就是 ，这时新的决策变量为：(224)（b）(di0) 中点画线算法式(224)减去(221)得：di+1=

16、di+2(xi-yi)+5(225)我们利用递推迭代计算这八分之一圆弧上的每个点，每次迭代需要两步处理：（1）用前一次迭代算出的决策变量的符号来决定本次选择的点。（2）对本次选择的点，重新递推计算得出新的决策变量的值。剩下的问题是计算初始决策变量d0，如下图所示。对于初始点(0，R)，顺时针生成八分之一圆，下一个中点M的坐标是 ，所以：(226生成圆的初始条件和圆的生成方向三、中点画圆算法实现1、输入：圆半径r、圆心(x0，y0)；2、确定初值：x=0，y=r、d=5/4-r；3、While(x=y)利用八分对称性，用规定的颜色color画八个象素点(x，y)； 若d0y=y-1；d=d+2(

17、x-y)+5)；否则d=d+2x+3；x=x+1；五、中点画圆算法完善在上述算法中，使用了浮点数来表示决策变量d。为了简化算法，摆脱浮点数，在算法中全部使用整数，我们使用e=d-1/4代替d。显然，初值d=5/4-r对应于e=1-r。决策变量d0对应于e-1/4。算法中其它与d有关的式子可把d直接换成e。又由于e的初值为整数，且在运算过程中的迭代值也是整数，故e始终是整数，所以e-1/4等价于e0。因此，可以写出完全用整数实现的中点画圆算法。要求：写出用整数实现的中点画圆算法程序，并上机调试，观看运行结果。六、中点画圆算法程序void MidpointCircle(int x0,int y0,

18、int r,int color)int x,y;float d;x=0;y=r;d=5.0/4-r;while(x=y)putdot(x0,y0,x,y,color);if(d0)d+=x*2.0+3;elsed+=2.0*(x-y)+5;y-; x+;putdot(x0,y0,x,y,color)putpixel(x0+x,y0+y,color);putpixel(x0+x,y0-y,color);putpixel(x0-x,y0+y,color);putpixel(x0-x,y0-y,color);putpixel(x0+y,y0+x,color);putpixel(x0+y,y0-x,c

19、olor);putpixel(x0-y,y0+x,color);putpixel(x0-y,y0-x,color);2.2.3 正负算法生成圆正负法是利用平面曲线将平面划分成正负区域，对当前点产生的圆函数进行符号判别，利用负反馈调整以决定下一个点的产生来直接生成圆弧。一、正负画圆算法描述设要显示圆的圆心在原点(0，0)，半径为R，初始点的坐标为(0，R)，顺时针生成八分之一圆，令：F(x，y)=x2+y2-R2则圆的方程为：F(x，y)=0 (2-27)当点(x，y)在圆内时，则F(x，y)0；当点(x，y)在圆上时，则F(x，y)=0；二、正负画圆算法思想现以下图的AB弧为例，来说明正负画圆

20、法(顺时针生成圆)。假设当前点为Pi(xi，yi)，取下一个点Pi+1(xi+1，yi+1)的原则是： 1、当F(xi，yi)0时：取xi+1= xi+1，yi+1= yi。即向右走一步，从圆内走向圆外。对应图(a)中的从Pi到Pi+1。2、当F(xi，yi)0时：取xi+1= xi，yi+1= yi-1。即向下走一步，从圆外走向圆内。对应图(b)中的从Pi到Pi+1。由于向圆内或向圆外走取决于F(xi，yi)的正负，因此称为正负法。下面分两种情况求出F(xi，yi)的递推公式：(1) 当F(xi，yi)0时，向右走，取xi+1=xi+1，yi+1=yi，则F(xi+1，yi+1)=F(xi+

21、1，yi)=(xi+1)2+yi2-R2=(xi2+yi2-R2)+2xi+1= F(xi，yi)+2xi+1(2-28)(2) 当F(xi，yi)0时，向下走，取xi+1=xi，yi+1=yi-1，则F(xi+1，yi+1)=F(xi，yi-1)=xi2+(yi-1)2-R2=(xi2+yi2-R2)-2yi+1= F(xi，yi)-2yi+1(2-9)初始时，x=0，y=R，故 F(0，R)=(02+R2)-R2=0 (2-30)公式(2-28)、(2-29)和(2-30)就构成正负画圆算法的核心。给象素坐标(x，y)及F赋初始值后，进入循环画点；画点后，根据F的符号进行F值的递推和下一个

22、点的获取，直到xy为止。同前面介绍的一样，利用圆的八分对称性，循环一次，画八个点。三、正负画圆算法实现注意：初值不同、圆的生成方向不同时，当前点和下一个点的获取原则是不同的，见下图。例如，初始点(R，0)，逆时针生成圆，从图（b）可知：若当前点Pi在圆内，则下一点Pi+1(xi，yi+1)，即向上走一步；若当前点Pi在圆外，则下一点Pi+1(xi-1，yi)，即向左走一步；(a) 顺时针生成圆 (b) 逆时针生成圆五、正负画圆算法特点物理意义清楚，程序中只含整数运算，因此算法速度快。六、正负画圆算法程序/ 顺时针生成圆void PNARC(int x0,int y0,int r,int col

23、or)int x=0,y=r,f=0;while(x=y)putdot(x0,y0,x,y,color);if(f=0)f=f+2*x+1;x+;elsef=f-2*y+1;y-;2.3 区域填充前面介绍的直线和圆都属于线划图，然而，光栅显示的一个重要特点是能进行面着色，区域填充就是在一个闭合区域内填充某种颜色或图案。区域填充一般分两类：多边形填充和种子填充。一、多边形填充1、填充条件多边形的顶点序列(Pi，i=0，1，n)、填充色。2、多边形内点的判别准则对多边形进行填充，关键是找出多边形内的象素。在顺序给定多边形顶点坐标的情况下，如何判明一个象素点是处于多边形的内部还是外部呢？从测试点引出

24、一条伸向无穷远处的射线(假设是水平向右的射线)，因为多边形是闭合的，那么：若射线与多边形边界的交点个数为奇数时，则该点为内点(例：图中测试点4引出的射线)；反之，交点个数为偶数时，则该点为外点。(例：测试点2引出的射线)。多边形内点的判别准则和奇异点3、奇异点的处理：上述的判别准则，在大多数情况下是正确的，但当水平扫描线正好通过多边形顶点时，要特别注意。例如，图中过顶点的射线1、射线6，它们与多边形的交点个数为奇数，按照判别准则它们应该是内点，但实际上却是外点。 而图中过顶点的射线3、射线5，对于判别准则的使用又是正确的。 多边形内点的判别准则和奇异点综合以上情况，我们将多边形的顶点分为两大类

25、： (1) 局部极值点：如图中的点P1、P2、P4和P6。对于这些点来说，进入该点的边线和离开该点的边线位于过该点扫描线的同一侧。(2)非极值点：如图中的点P3、P5。对于这些点来说，进入该点的边线和离开该点的边线位于过该点扫描线的两侧。处理奇异点规则：（1）对于局部极值点，应看成两个点；（2）对于非极值点，应看成一个点。4、逐点判别算法步骤：(1)求出多边形的最小包围盒：从Pi(xi，yi)中求极值，xmin、ymin、xmax、ymax。 (2)对包围盒中的每个象素引水平射线进行测试。 (3)求出该射线与多边形每条边的有效交点个数。 (4)如果个数为奇数：该点置为填充色。 (5)否则：该点

26、置为背景色。 逐点判别算法虽然简单，但不可取，原因是速度慢。它割断了各象素之间的联系，孤立地考虑问题，由于要对每个象素进行多次求交运算，求交时要做大量的乘除运算，从而影响了填充速度。 二、种子填充种子填充是将区域内的一点(种子)赋予给定的颜色，然后将这种颜色扩展到整个区域内的过程。1、填充条件区域内一点的坐标即种子坐标、边界色、填充色。2、连通方式区域是互相连通着的象素的集合，连通方式可分为四连通和八连通。四连通：从区域内一点出发，可通过四个方向：上、下、左、右到达该区域内部的任意象素。八连通：区域内部从一个象素到达另一个象素的移动路径，除了上、下、左、右四个方向外，还允许沿着对角线方向。注意

27、：（1） 八连通区域中，既然区域内的两个象素可以通过对角线相通，那么，区域边界上的象素则不能通过对角线相连，否则填充就会溢出到区域外，因此，八连通区域的边界线必须是四连通的，见下图(a)；（2）而四连通区域，其边界象素是四连通和八连通的都可以，见下图(b)。(a) 八连通区域四连通边界(b) 四连通区域八连通(或四连通)边界3、内点(x,y)的检测条件(1) if(getpixel(x,y)!=边界色 & getpixel(x,y)!=填充色) (2) if(getpixel(x,y)!=背景色)这两个条件任何一个都可以用来检测象素点(x,y)是不是尚未填充。推荐使用条件(1)进行象素点检测。

28、2.3.1 边相关扫描线多边形填充算法2.3.2 扫描线种子填充算法2.3.3 边标志填充算法2.3.4 图案填充2.3.1 边相关扫描线多边形填充算法边相关扫描线填充算法属于多边形填充类。它比逐点判别算法速度提高很多，是一种较经典的多边形填充算法。该算法利用了扫描线的相关性和多边形边的相关性，而不是逐点进行处理。一、边相关扫描线填充算法描述扫描线的相关性：某条扫描线上相邻的象素，几乎都具有同样的内外性质，这种性质只有遇到多边形边线与该扫描线的交点时才会发生改变。见下图(a)。边的相关性：由于相邻扫描线上的交点是与多边形的边线相关的。对同一条边，前一条扫描线yi与该边的交点为xi，而后一条扫描

29、线yi+1=yi+1与该边的交点则为xi+1=xi+1/m，利用这种相关性可以省去大量的求交运算。见下图(b)所示。(a) 扫描线的相关性(b) 边的相关性边相关扫描线填充算法的实现需要建立两个表：边表（ET）和活动边表（AET）。1、边表（ET：Edge Table）用来对除水平边外的所有边进行登记，来建立边的记录。边的记录定义为：扫描线 y 对应的ET表第一项：某边的最大y值（ymax）。注意要进行奇异点处理：对于非极值点应该ymax=ymax-1。第二项：某边的最小的y对应的x值。第三项：某边斜率的倒数:1/m。第四项：指针。用来指向同一条扫描线相交的其它边，如果其它边不存在，则该项置空

30、。2、活动边表（AET：Active Edge Table）ET表建立以后，就可以开始扫描转换了。对不同的扫描线，与之相交的边线也是不同的，当对某一条扫描线进行扫描转换时，我们只需要考虑与它相交的那些边线，为此需要建立一个只与当前扫描线相交的边记录链表，称之为活动边表。二、边相关扫描线填充算法思想1、根据给出的多边形顶点坐标，建立ET表； 求出顶点坐标中最大y值ymax和最小y值ymin。2、初始化AET表指针，使它为空。3、使用扫描线的yj值作为循环变量，使其初值为ymin。 对于循环变量yj的每一整数值，重复作以下事情，直到yj大于ymax，或ET表与AET表都为空为止：(1) 如果ET表

31、中yj桶非空，则将yj桶中的全部记录合并到AET表中。(2) 对AET表链中的记录按x的大小从小到大排序。(3) 依次取出AET表各记录中的xi坐标值，两两配对填充，即将每对xi之间的象素填上所要求的颜色。(4) 如果AET表中某记录的ymax=yj，则删除该记录。(5) 对于仍留在AET表中的每个记录，用xi+1/m代替xi进行修改，这就是该记录的边线与下一条扫描线yj+1的交点。(6) 使yj加1，以便进入下一轮循环。三、边相关扫描线填充算法举例对下图(a)的多边形利用边相关扫描线填充算法进行处理：1、首先建立ET表。注意：在做奇异点处理时，当该边最大y值对应的顶点为非极值点时，边记录的第

32、一项：ymax=ymax-1。例如：P3P4边、P3P2边、P4P5边，见下图(b)。2、接着建立AET表。AET表的建立过程就是有效地进行填充的操作，在这个期间不断地做以下工作：（1）合并ET表；（2）x递增排序；（3）实施填充；（4）删除ymaxyj的边；（5）修改边记录xi=xi+1/m；（6）yj+1进入下一轮循环。结果见下图(c)。(a) 多边形 (b) ET表 (c) AET表四、边相关扫描线填充算法实现1、根据给定的多边形顶点坐标，建立ET 表。2、AET表初始化，每个桶置空。3、for(y=ymin;y= ymax;y+) 合并当前扫描线y的ET表； 将y桶中每个记录按x项升序

33、排列； 在当前y值下，将两两记录的x值之间的象素进行填充； 删除y=ymax的边记录； 修改边记录x=x+1/m； 六、边相关扫描线填充算法特点该算法充分利用多边形的边相关性和扫描线的相关性，使用ET表对多边形的非水平边进行登记；用AET表的建立和更新来支持填充，大大地减少了求交点的计算量，有效地提高了填充速度。2.3.2 扫描线种子填充算法该算法属于种子填充算法，它是以扫描线上的区段为单位进行操作。所谓区段，就是一条扫描线上相连着的若干内部象素的集合。一、扫描线种子填充算法思想扫描线种子填充算法的基本思想是：首先填充当前扫描线上的位于给定区域内的一区段，然后确定与这一区段相邻的上下两条扫描线

34、上位于该区段内是否存在需要填充的新区段，如果存在，则依次把它们保存起来。反复这个过程，直到所保存的各区段都填充完毕。二、扫描线种子填充算法实现借助于堆栈，上述算法实现步骤如下：1、初始化堆栈。2、种子压入堆栈。3、while（堆栈非空） (1)从堆栈弹出种子象素。(2)如果种子象素尚未填充，则：a.求出种子区段：xleft、xright;b.填充整个区段。c.检查相邻的上扫描线的xleftxxright区间内,是否存在需要填充的新区段，如果存在的话，则把每个新区段在xleftxxright范围内的最右边的象素，作为新的种子象素依次压入堆栈。d.检查相邻的下扫描线的xleftxxright区间内

35、，是否存在需要填充的新区段，如果存在的话，则把每个新区段在xleftxxright范围内的最右边的象素，作为新的种子象素依次压入堆栈。四、扫描线种子填充算法特点1、该算法考虑了扫描线上象素的相关性，种子象素不再代表一个孤立的象素，而是代表一个尚未填充的区段。2、进栈时，只将每个区段选一个象素进栈（每个区段最右边或最左边的象素），这样解决了堆栈溢出的问题。3、种子出栈时，则填充整个区段。4、这样有机的结合：一边对尚未填充象素的登记（素进栈），一边进行填充（象素出栈），既可以节省堆栈空间，又可以实施快速填充。2.3.3 边标志填充算法在光栅显示平面上，多边形是封闭的，它是用某一边界色围成的一个闭合

36、区域，填充是逐行进行的，即用扫描线逐行对多边形求交，在交点对之间填充。边标志填充算法就是在逐行处理时，利用边界色作为标志来进行填充的。例如某扫描线从左到右扫描时碰到边界色，立刻改变标志的状态，接下来再根据标志的状态决定某象素点是否填充。一、边标志填充算法思想扫描线具有连贯性，这种连贯性只有在扫描线与多边形相交处才会发生变化，而每次的变化结果：无非是在前景色和背景色之间相互“切换”。边标志填充算法正是基于这一发现，先在屏幕上生成多边形轮廓线，然后逐条扫描处理。处理中：逐点读取象素值，若为边界色，则对该象素值进行颜色切换。二、边标志填充算法实现 1、用边界色画出多边形轮廓线，也就是将多边形边界所经

37、过的象素打上边标志。 2、为了缩小范围，加快填充速度，须找出多边形的最小包围盒：xmin、ymin、xmax、ymax。如下图所示。边标志填充算法3、逐条扫描线进行处理，对每条扫描线依从左往右的顺序，逐个访问该扫描线上的象素。每遇到边界象素，标志取反。然后，按照标志是否为真，决定象素是否为填充色。四、边标志填充算法特点该算法思想简单，实现容易。既不需要求交点、交点排序、边的登记，也不需要使用链表、堆栈等数据结构。五、边标志填充算法程序EdgeMarkFill(int p2,int n,int boundarycolor,int newcolor)int i,x,y,flag,xmin,xmax

38、,ymin,ymax;setcolor(boundarycolor); /*设置画笔色*/ for(i=0 ;in;i+)line(pi0,pi1,p(i+1)%n0,p(i+1)%n)1); /*画出多边形的n条边*/用求极值的算法，从多边形顶点数组p中，求出xmin,xmax,ymin,ymax;for(y=ymin;y=ymax;y+) flag=-1;for(x=xmin;x=xmax;x+) if(getpixel(x,y)=boundarycolor)flag=-flag;if(flag=1)putpixel(x,y, newcolor);六、边标志填充算法错误处理1、该算法虽然简

39、单，但程序运行后会出现局部错误。从下图可以发现，对于多边形顶点为局部极值点时，扫描线与多边形的相交次数不再是偶数，而是奇数，填充时会出现“抽丝”现象。即某扫描线上不该填充的区段填上色，而应该填充的区段却没有填上色。解决的办法：判断多边形顶点的性质，如果是局部极值点，那么扫描线碰上它则不改变标志。2、特别当心多边形边界的扫描转换。在这里就不能考虑：不同的斜率产生的直线要亮度均匀，如下图(a)所示。否则当扫描线y遇到斜率小于1的边界线时，碰到几个边界点，会引起标志的无序改变，将导致填充的错误。解决的办法：对于不同斜率的边界，都要使用斜率大于1的直线扫描转换方法：每次y方向增长一步，x方向增长1/m步距，以保证扫描线y遇到斜率小于1的边界时，只