第二章 二维基本图形的生成与二维区域的填充

1、2021-7-251 第二章 二维基本图形的生成与区 域填空 重重点：点：掌握二维图元直线、圆、区域 填充、字符的生成算法。 难难点：点：理解二维图元生成的算法思想 并且用C语言进行算法的实现。 课时安排：课时安排：授课8学时（直线、圆：3学时； 区域填充：4学时；字符：1学时）； 上机4学时（直线、圆：2学时；区域填充： 2学时）。 2021-7-252 第二章 二维基本图形的生成与区域 填空 图元生成算法的要求：准确、亮度均匀、速 度快。 前面已经知道，矢量显示（随机扫描显示器） 和光栅显示是两种完全不同的图形显示技术。 2021-7-253 第二章 二维基本图形的生成与区域 填空 目前，

2、光栅显示技术占主要地位。 原因是： 1、光栅显示可以用颜色或图案来填充一 个区域； 2、光栅显示以象素为单位进行读写和存 储，可以实现对物体细节的描述； 3、图形的任意部分均可以被移动和复制。 2021-7-254 第二章 二维基本图形的生成与区域 填空 在这一章里，主要介绍在光栅输出设备上， 根据物体的坐标描述构造二维几何图形的方法。 在光栅显示器上，象素是屏幕的最小显示单 位，因此二维图形的构造就是找出最靠近所描述 几何图形的那些象素，将它们置入规定的颜色并 放入帧缓存。 我们知道，一幅图是由点、直线、曲线、多 边形填充区域以及字符串等组成。下面将讨论这 些基本图元的生成技术和算法。 20

3、21-7-255 2.1 直线的扫描转换 一、数学直线 在数学上，理想的直线是一条由无穷多个无 限小的连续的点组成。 数学直线 2021-7-256 2.1 直线的扫描转换 二、光栅平面显示的直线 但在光栅显示平面上，我们只能用二 维光栅格网上尽可能靠近这条直线的象素 点的集合来表示它。每个象素具有一定的 尺寸，是显示平面上可被访问的最小单位， 它的坐标x和y只能是整数，也就是说相邻 像素的坐标值是阶梯的而不是连续的。 2021-7-257 2.1 直线的扫描转换 光栅直线 2021-7-258 2.1 直线的扫描转换 三、直线的扫描转换 直线的扫描转换，就是要找出显示平面上最佳逼近理 想直线

4、的那些象素的坐标值，并将这些象素置成所要求的 颜色。 直线的扫描转换 由于一幅图中可能包含成千上万条直线，所以要求绘 制算 法应该： 1、最接近数学上的直线； 2021-7-259 2.1 直线的扫描转换 2、沿着线段分布的象素应均匀 不均匀的例子如下图所示，对同样长 的线段，如果进行图中的扫描转换，就会 因为斜率的不同，产生的象素个数不相等， 这样将导致象素亮度分布不均匀。 3、画线速度尽可能的快 2021-7-2510 2.1.1 生成直线的DDA算法 数值微分法即DDA法(Digital Differential Analyzer)，是一种基于直线的 微分方程来生成直线的方法 一、直线D

5、DA算法描述： 设(x1，y1)和(x2，y2)分别为所求直线 的起点和终点坐标，由直线的微分方程得 = m =直线的斜率 (21) 2021-7-2511 2.1.1 生成直线的DDA算法 可通过计算由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)是递推的。 2021-7-2512 2.1.1 生成直线的DDA算法 二、直线DDA算法思想： 选定x2x1和y2y1中较大者作为步进方

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

7、1，y1)， (x2，y2) 2、已知画线的颜色：color 3、计算两个方向的变化量：dx=x2x1 dy=y2y1 4、求出两个方向最大变化量的绝对值： steps=max(|dx|，|dy|) 2021-7-2515 2.1.1 生成直线的DDA算法 5、计算两个方向的增量(考虑了生成方向)： xin=dx/steps yin=dy/steps 6、设置初始象素坐标：x=x1,y=y1 7、用循环实现直线的绘制： for(i=1；i=steps；i+) putpixel(x，y，color)；/*在(x，y)处， 以color色画点*/ x=x+xin； y=y+yin； 2021-7-

8、2516 2.1.1 生成直线的DDA算法 四、直线DDA算法特点： 该算法简单，实现容易，但由于在循环 中涉及实型数的运算，因此生成直线的速度 较慢。 五、直线DDA算法程序： 下面给出考虑不同斜率、不同方向直线 的DDA画线算法程序： 2021-7-2517 2.1.1 生成直线的DDA算法 void DDAline(int x0,int y0,int x1,int y1,int color) int x; float dx,dy,y,k; dx=x1-x0,dy=y1-y0; k=dy/dx,y=y0; for(x=x0;x=x1;x+) putpixel(x，int(y+0.5)，co

9、lor); /在(x，y)处， 以color色画点 y=y+k; 2021-7-2518 2.1.2 生成直线的Bresenham算法 从上面介绍的DDA算法可以看到，由于在循 环中涉及实型数据的加减运算，因此直线的生成 速度较慢。 在生成直线的算法中，Bresenham算法是最 有效的算法之一。Bresenham算法是一种基于误 差判别式来生成直线的方法。 一、直线Bresenham算法描述： 它也是采用递推步进的办法，令每次最大变 化方向的坐标步进一个象素，同时另一个方向的 坐标依据误差判别式的符号来决定是否也要步进 一个象素。 2021-7-2519 2.1.2 生成直线的Bresenh

10、am算法 我们首先讨论m=y/x，当0m1且 x1x2时的Bresenham算法。从DDA直线算 法可知这些条件成立时，公式(2-2)、(2-3) 可写成： xi+1=xi+1 (26) yi+1=yi+m (27) 有两种Bresenham算法思想，它们各 自从不同角度介绍了Bresenham算法思想， 得出的误差判别式都是一样的。 2021-7-2520 2.1.2 生成直线的Bresenham算法 二、直线Bresenham算法思想之一 由于显示直线的象素点只能取整数值 坐标，可以假设直线上第i个象素点坐标为 (xi，yi)，它是直线上点(xi，yi)的最佳近似， 并且xi=xi(假设m

11、d2，说明直线上 理论点离(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。 2021-7-2525 2.1.2 生成直线的Bresenham算法 将式(2-11)中的下标i改写成i+1，得到： pi+1=2yxi+1-2xyi+1+c (212) 将式(2-12)减去(2-11)，并利用xi+1=xi+1， 可得： pi+1= pi+2y-2x(yi+1-yi)

12、(213) 再假设直线的初始端点恰好是其象素点的 坐标，即满足： y1=mx1+b (214) 2021-7-2526 2.1.2 生成直线的Bresenham算法 由式(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 2021-7-2527 2.1.2 生成直线的Bresenham算法 从式(2-16)可以看出，第i+1步的判别

13、变量pi+1 仅与第i步的判别变量pi、直线的两个端点坐标分 量差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)呢？ 2021-7-2528 2.1.2 生成直线的Bresenham算法 设A为CD边的中点，正确的选择：

14、 若B点在A点上方，选择D点； 否则，选C点。 用误差式描述为： (xi+1)=BC-AC=(yi+1-yir)-0.5 (28) 2021-7-2529 2.1.2 生成直线的Bresenham算法 求递推公式： (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 (2 10) 当(xi+1)0时，选C点，y(i+1)r = yir (xi+2)= yi+1+myir-0.5=(xi+1)+m (2 11) 2

15、021-7-2530 2.1.2 生成直线的Bresenham算法 初始时： (xs+1)=BC-AC=m-0.5 (212) 2021-7-2531 2.1.2 生成直线的Bresenham算法 为了运算中不含实型数，同时不影响不等式 的判断，将方程两边同乘一正整数。 令方程两边同乘2x，即p=2x，则： 初始时： p = 2y-x (213)递推式： 当p0时： p=p+2(yx)； y+； x+； 否则： p=p+2y； x+； (214) 2021-7-2532 2.1.2 生成直线的Bresenham算法 四、直线Bresenham算法实现 条件：0m1且x1x2 1、输入线段的两个

16、端点坐标和画线颜色： x1，y1，x2，y2，color； 2、设置象素坐标初值：x=x1，y=y1； 3、设置初始误差判别值：p=2y-x； 4、分别计算：x=x2-x1、y=y2-y1； 2021-7-2533 2.1.2 生成直线的Bresenham算法 5、循环实现直线的生成： for(x=x1；x=0) y=y+1； p=p+2(y-x)； else p=p+2y； 2021-7-2534 2.1.2 生成直线的Bresenham算法 五、直线Bresenham算法完善 现在我们修正(2-16)公式，以适应对任何方向 及任何斜率线段的绘制。如下图所示，线段的方 向可分为八种，从原点出

17、发射向八个区。由线段 按图中所示的区域位置可决定xi+1和yi+1的变换规 律。 容易证明：当线段处于、区时， 以|x|和|y|代替前面公式中的x和y，当线 段处于、区时，将公式中的|x|和 |y|对换，则上述两公式仍有效。 2021-7-2535 2.1.2 生成直线的Bresenham算法 在线段起点区分线段方向 2021-7-2536 2.1.2 生成直线的Bresenham算法 七、直线Bresenham算法特点 由于程序中不含实型数运算，因此速度快、效率高， 是一种有效的画线算法。 八、直线Bresenham算法程序 void Bresenhamline (int x1,int y1

18、,int x2,int y2,int color) int x, y, dx, dy, s1, s2, p, temp, interchange, i; x=x1; y=y1; dx=abs(x2-x1); dy=abs(y2-y1); if(x2x1) s1=1; else s1=-1; 2021-7-2537 2.1.2 生成直线的Bresenham算法 if(y2y1) s2=1; else s2=-1; if(dydx) temp=dx; dx=dy; dy=temp; interchange=1; else interchange=0; p=2*dy-dx; 2021-7-2538

19、2.1.2 生成直线的Bresenham算法 for(i=1;i=0) if(interchange= =0) y=y+s2; else x=x+s1; p=p-2*dx; if(interchange= =0) x=x+s1; else y=y+s2; p=p+2*dy; 2021-7-2539 2.1 直线的生成习题 1.DDA法生成直线的基本原理是 什么？ 2021-7-2540 2.2 圆的生成 这里仅讨论圆心位于坐标原点的圆的扫 描转换算法，对于圆心不在原点的圆，可 先用平移变换，将它的圆心平移到原点， 然后进行扫描转换，最后再平移到原来的 位置。 有几种较容易的方法可以得到圆的扫

20、描转换，但是效率都不高。例如：直角坐 标法和极坐标法： 1、直角坐标法 圆的直角坐标方程为 x2+y2=R2 若取x作为自变量，解出y，得到 2021-7-2541 2.2 圆的生成 (217) 我们可以先扫描转换四分之一的圆周。 让自变量x从0到R以单位步长增加，在每一 步时可解出y，然后调用画点函数即可逐点 画出圆。但这样做，由于有乘方和平方根 运算，并且都是浮点运算，算法效率不高。 而且当x接近R值时(圆心在原点)，在圆周上 的点（R，0）附近，由于圆的斜率趋于无 穷大，使得圆周上有较大的间隙。 2021-7-2542 2.2 圆的生成 2、极坐标法 假设圆周上一点P（x，y）处的半径与

21、x轴的夹角为， 则圆的极坐标方程为 x=Rcos (218) y=Rsin 利用下面将要介绍的圆周上点的对称性，那么自变量 的取值范围就是(0，45)。这个方法涉及三角函数计算 和乘法运算，计算量较大。因此，也不是一种有效的方法。 2021-7-2543 2.2.1 圆的八分对称性 圆心位于原点的圆有四条对称轴x=0、 y=0、x=y和x=y，见下图。从而若已知圆 弧上一点P(x，y)，就可以得到其关于四条 对称轴的七个对称点，这种性质称为八分 对称性。因此只要能画出八分之一的圆弧， 就可以利用对称性的原理得到整个圆弧。 下面的函数CirclePoints()用来显示P(x，y) 及其七个对称

22、点。 2021-7-2544 2.2.1 圆的八分对称性 void CirclePoints(x,y,color) int x,y,color; putpixel(x,y,color); putpixel(x,y,color); putpixel(x,y,color); putpixel(x,y,color); putpixel(y,x,color); putpixel(y,x,color); putpixel(y,x,color); putpixel(y,x,color); 2021-7-2545 2.2.1 圆的八分对称性 圆的八分对称性 注意：注意： 当圆心不在原点时，只须在putpix

23、el()函数中 加上平移量x0、y0（圆心坐标）即可。 2021-7-2546 2.2.1 圆的八分对称性 例如 当 x0=300，y0=200时，则： 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，color)； putpixel(x0-y，y0+x，color)； putpixel(x0-y，y0-x，color)； 2021-7-

24、2547 2.2.2 中点算法生成圆 中点画圆算法在一个方向上取单位间隔，在 另一个方向的取值由两种可能取值的中点离圆的 远近而定。实际处理中，用决策变量的符号来确 定象素点的选择，因此算法效率较高。 一、中点画圆算法描述 设要显示圆的圆心在原点(0，0)，半径为R， 起点在(0，R)处，终点在( , )处，顺时针 生成八分之一圆，利用对称性扫描转换全部圆。 为了应用中点画圆法，我们定义一个圆函数 F(x，y)=x2+y2-R2 (219) 2021-7-2548 2.2.2 中点算法生成圆 任何点(x，y)的相对位置可由圆函数的 符号来检测： 0点(x，y)位于数学圆外 2021-7-254

25、9 2.2.2 中点算法生成圆 如下图所示，图中有两条圆弧A和B，假定当 前取点为Pi(xi，yi)，如果顺时针生成圆，那么下 一点只能取正右方的点E(xi+1，yi)或右下方的点 SE(xi+1，yi-1)两者之一。 中点画线算法 2021-7-2550 2.2.2 中点算法生成圆 假设M是E和SE的中点，则： 1、当F(M)0时，M在圆外(圆弧B)， 表明SE点离圆更近，应取SE点； 3、当F(M)=0时，在E点与SE点之中随 便取一个即可，我们约定取SE点。 2021-7-2551 2.2.2 中点算法生成圆 二、中点画圆算法思想 因此，我们用中点M的圆函数作为决策变量di， 同时用增量

26、法来迭代计算下一个中点M的决策变 量di+1。 (221) 下面分两种情况来讨论在迭代计算中决策变 量di+1的推导。 1、见图（a），若di0，则选择E点，接着下 一个中点就是 ，这时新的决策变 量为： (222) 2021-7-2552 2.2.2 中点算法生成圆 （a）(di0) 中点画线算法 2021-7-2553 2.2.2 中点算法生成圆 式(222)减去(221)得： di+1=di+2xi+3 (223) 2、见图（b），若di0，则选择SE点，接 着下一个中点就是 ，这时 新的决策变量为： (224) 2021-7-2554 2.2.2 中点算法生成圆 （b）(di0) 中点

27、画线算法 式(224)减去(221)得： di+1=di+2(xi-yi)+5 (225) 2021-7-2555 2.2.2 中点算法生成圆 我们利用递推迭代计算这八分之一圆弧上 的每个点，每次迭代需要两步处理： （1）用前一次迭代算出的决策变量的符号 来决定本次选择的点。 （2）对本次选择的点，重新递推计算得出 新的决策变量的值。 剩下的问题是计算初始决策变量d0，如下图 所示。对于初始点(0，R)，顺时针生成八分之一 圆，下一个中点M的坐标是 ，所以： 2021-7-2556 2.2.2 中点算法生成圆 (226） 生成圆的初始条件和圆的生成方向 2021-7-2557 2.2.2 中点

28、算法生成圆 三、中点画圆算法实现 1、输入：圆半径r、圆心(x0，y0)； 2、确定初值：x=0，y=r、d=5/4-r； 3、While(x=y) 利用八分对称性，用规定的颜色color画八个象素 点(x，y)； 若d0 y=y-1； d=d+2(x-y)+5； 否则 d=d+2x+3； x=x+1； 2021-7-2558 2.2.2 中点算法生成圆 四、中点画圆算法完善 在上述算法中，使用了浮点数来表示决策变量 d。为了简化算法，摆脱浮点数，在算法中全部使 用整数，我们使用e=d-1/4代替d。显然，初值 d0=5/4-r对应于e0=1-r。决策变量d0对应于e- 1/4。算法中其它与d

29、有关的式子可把d直接换成e。 又由于e的初值为整数，且在运算过程中的迭代值 也是整数，故e始终是整数，所以e-1/4等价于 e0。因此，可以写出完全用整数实现的中点画 圆算法。 要求：写出用整数实现的中点画圆算法程序， 并上机调试，观看运行结果。 2021-7-2559 2.2.2 中点算法生成圆 五、中点画圆算法程序 void MidpointCircle(int x0,int y0,int r,int color) int x,y; float d; x=0; y=r; d=5.0/4-r; 2021-7-2560 2.2.2 中点算法生成圆 while(x=y) putdot(x0,y0

30、,x,y,color); if(d0) d+=x*2.0+3; else d+=2.0*(x-y)+5; y-; x+; 2021-7-2561 2.2.2 中点算法生成圆 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,color); putpixel(x0-y,y0+x,color);

31、putpixel(x0-y,y0-x,color); 2021-7-2562 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； 2021-7-2563 2.2.3 正负算法生成圆 二、正负画圆算法

32、思想 现以下图的AB弧为例，来说明正负画 圆法(顺时针生成圆)。 2021-7-2564 2.2.3 正负算法生成圆 假设当前点为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)的递推公

33、式： 2021-7-2565 2.2.3 正负算法生成圆 (1) 当F(xi，yi)0时，向右走，取xi+1=xi+1， yi+1=yi，则 F(xi+1，yi+1)=F(xi+1，yi) =(xi+1)2+yi2-R2 =(xi2+yi2-R2)+2xi+1 = F(xi，yi)+2xi+1 (2-28) 2021-7-2566 2.2.3 正负算法生成圆 (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

34、(2-29) 2021-7-2567 2.2.3 正负算法生成圆 初始时，x=0，y=R，故 F(0，R)=(02+R2)-R2=0 (2-30) 公式(2-28)、(2-29)和(2-30)就构成正负画 圆算法的核心。 给象素坐标(x，y)及F赋初始值后，进 入循环画点； 画点后，根据F的符号进行F值的递推 和下一个点的获取，直到xy为止。 同前面介绍的一样，利用圆的八分对 称性，循环一次，画八个点。 2021-7-2568 2.2.3 正负算法生成圆 三、正负画圆算法实现 注意：初值不同、圆的生成方向不同 时，当前点和下一个点的获取原则是不同 的，见下图。 例如，初始点(R，0)，逆时针生

35、成圆， 从图（b）可知： 若当前点Pi在圆内，则下一点Pi+1(xi， yi+1)，即向上上走一步； 若当前点Pi在圆外，则下一点Pi+1(xi-1， yi)，即向左左走一步； 2021-7-2569 2.2.3 正负算法生成圆 (a) 顺时针生成圆(b) 逆时针生成圆 2021-7-2570 2.2.3 正负算法生成圆 四、正负画圆算法特点 物理意义清楚，程序中只含整数运算， 因此算法速度快。 五、正负画圆算法程序 / 顺时针生成圆 void PNARC(int x0,int y0,int r,int color) int x=0,y=r,f=0; 2021-7-2571 2.2.3 正负算

36、法生成圆 while(x=y) putdot(x0,y0,x,y,color); if(f=0) f=f+2*x+1; x+; else f=f-2*y+1; y-; 2021-7-2572 2.2 圆的生成习题 1. 用自己的语言描述中点画圆算法。 2021-7-2573 2.3 区域填充 前面介绍的直线和圆都属于线划图，然而， 光栅显示的一个重要特点是能进行面着色，区域 填充就是在一个闭合区域内填充某种颜色或图案。 区域填充一般分两类：多边形填充和种子填 充。 一、多边形填充 1、填充条件 多边形的顶点序列(Pi，i=0，1，n)、填 充色。 2、多边形内点的判别准则 对多边形进行填充，关

37、键是找出多边形内的 象素。在顺序给定多边形顶点坐标的情况下，如 何判明一个象素点是处于多边形的内部还是外部 呢？ 2021-7-2574 2.3 区域填充 从测试点引出一条伸向无穷远处的射 线(假设是水平向右的射线)，因为多边形是 闭合的，那么： 若射线与多边形边界的交点个数为奇 数时，则该点为内点(例：图中测试点4引出 的射线)； 反之，交点个数为偶数时，则该点为 外点。(例：测试点2引出的射线)。 2021-7-2575 2.3 区域填充 多边形内点的判别准则和奇异点 2021-7-2576 2.3 区域填充 3、奇异点的处理 上述的判别准则，在大多数情况下是 正确的，但当水平扫描线正好通

38、过多边形 顶点时，要特别注意。例如，图中过顶点 的射线1、射线6，它们与多边形的交点个 数为奇数，按照判别准则它们应该是内点， 但实际上却是外点。 而图中过顶点的射线3、射线5，对于 判别准则的使用又是正确的。 2021-7-2577 2.3 区域填充 综合以上情况，我们将多边形的顶点分为两 大类： (1) 局部极值点：如图中的点P1、P2、P4和P6。 对于这些点来说，进入该点的边线和离开该点的 边线位于过该点扫描线的同一侧。 (2)非极值点：如图中的点P3、P5。对于这些点 来说，进入该点的边线和离开该点的边线位于过 该点扫描线的两侧。 处理奇异点规则： （1）对于局部极值点，应看成两个点

39、； （2）对于非极值点，应看成一个点。 2021-7-2578 2.3 区域填充 4、逐点判别算法步骤： (1)求出多边形的最小包围盒：从Pi(xi，yi)中求 极值，xmin、ymin、xmax、ymax。 (2)对包围盒中的每个象素引水平射线进行测试。 (3)求出该射线与多边形每条边的有效交点个数。 (4)如果个数为奇数：该点置为填充色。 (5)否则：该点置为背景色。 逐点判别算法虽然简单，但不可取，原因是 速度慢。它割断了各象素之间的联系，孤立地考 虑问题，由于要对每个象素进行多次求交运算， 求交时要做大量的乘除运算，从而影响了填充速 度。 2021-7-2579 2.3 区域填充 二、

40、种子填充 种子填充是将区域内的一点(种子)赋予 给定的颜色，然后将这种颜色扩展到整个 区域内的过程。 1、填充条件 区域内一点的坐标即种子坐标、边界 色、填充色。 2、连通方式 区域是互相连通着的象素的集合，连 通方式可分为四连通和八连通。 2021-7-2580 2.3 区域填充 四连通：从区域内一点出发，可通过四个 方向：上、下、左、右到达该区域内部的 任意象素。 八连通：区域内部从一个象素到达另一个 象素的移动路径，除了上、下、左、右四 个方向外，还允许沿着对角线方向。 2021-7-2581 2.3 区域填充 注意： （1） 八连通区域中，既然区域内的两 个象素可以通过对角线相通，那么

41、，区域 边界上的象素则不能通过对角线相连，否 则填充就会溢出到区域外，因此，八连通 区域的边界线必须是四连通的，见下图(a)； （2）而四连通区域，其边界象素是四连 通和八连通的都可以，见下图(b)。 2021-7-2582 2.3 区域填充 (a) 八连通区域四连通边界(b) 四连 通区域八连通(或四连通)边界 2021-7-2583 2.3 区域填充 3、内点(x,y)的检测条件 (1) if(getpixel(x,y)!=边界色 y= ymax;y+) 合并当前扫描线y的ET表； 将y桶中每个记录按x项升序排列； 在当前y值下，将两两记录的x值之间 的象素进行填充； 删除y=ymax的边

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

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

44、充的新区段，如果存在 的话，则把每个新区段在xleftxxright范围内 的最右边的象素，作为新的种子象素依次 压入堆栈。 d.检查相邻的下扫描线的xleftxxright区间 内，是否存在需要填充的新区段，如果存 在的话，则把每个新区段在xleftxxright范 围内的最右边的象素，作为新的种子象素 依次压入堆栈。 2021-7-25100 2.3.2 扫描线种子填充算法 四、扫描线种子填充算法特点 1、该算法考虑了扫描线上象素的相关性，种子 象素不再代表一个孤立的象素，而是代表一个尚 未填充的区段。 2、进栈时，只将每个区段选一个象素进栈（每 个区段最右边或最左边的象素），这样解决了堆

45、 栈溢出的问题。 3、种子出栈时，则填充整个区段。 4、这样有机的结合：一边对尚未填充象素的登 记（象素进栈），一边进行填充（象素出栈）， 既可以节省堆栈空间，又可以实施快速填充。 2021-7-25101 2.3.3 边标志填充算法 在光栅显示平面上，多边形是封闭的， 它是用某一边界色围成的一个闭合区域， 填充是逐行进行的，即用扫描线逐行对多 边形求交，在交点对之间填充。边标志填 充算法就是在逐行处理时，利用边界色作 为标志来进行填充的。例如某扫描线从左 到右扫描时碰到边界色，立刻改变标志的 状态，接下来再根据标志的状态决定某象 素点是否填充。 2021-7-25102 2.3.3 边标志填

46、充算法 一、边标志填充算法思想 扫描线具有连贯性，这种连贯性只有 在扫描线与多边形相交处才会发生变化， 而每次的变化结果：无非是在前景色和背 景色之间相互“切换”。 边标志填充算法正是基于这一发现， 先在屏幕上生成多边形轮廓线，然后逐条 扫描处理。处理中：逐点读取象素值，若 为边界色，则对该象素值进行颜色切换。 2021-7-25103 2.3.3 边标志填充算法 二、边标志填充算法实现 1、用边界色画出多边形轮廓线，也就是 将多边形边界所经过的象素打上边标志。 2、为了缩小范围，加快填充速度，须找 出多边形的最小包围盒：xmin、ymin、xmax、 ymax。如下图所示。 2021-7-2

47、5104 2.3.3 边标志填充算法 边标志填充算法 3、逐条扫描线进行处理，对每条扫描线依从左往右的顺 序，逐个访问该扫描线上的象素。每遇到边界象素，标志 取反。然后，按照标志是否为真，决定象素是否为填充色。 2021-7-25105 2.3.3 边标志填充算法 三、边标志填充算法特点 该算法思想简单，实现容易。既不需 要求交点、交点排序、边的登记，也不需 要使用链表、堆栈等数据结构。 四、边标志填充算法程序 EdgeMarkFill(int p2,int n,int boundarycolor,int newcolor) 2021-7-25106 2.3.3 边标志填充算法 int i,

48、x,y,flag,xmin,xmax,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; 2021-7-25107 2.3.3 边标志填充算法 for(y=ymin;y=ymax;y+) flag=-1; for(x=xmin;x=xmax;x+) if(getpixel(x,y)=boundarycolor) flag=(-1) *fl

49、ag; if(flag=1) putpixel(x,y, newcolor); 2021-7-25108 2.3.3 边标志填充算法 五、边标志填充算法错误处理 1、该算法虽然简单，但程序运行后会出 现局部错误。从下图可以发现，对于多边 形顶点为局部极值点时，扫描线与多边形 的相交次数不再是偶数，而是奇数，填充 时会出现“抽丝”现象。即某扫描线上不 该填充的区段填上色，而应该填充的区段 却没有填上色。 解决的办法：判断多边形顶点的性质， 如果是局部极值点，那么扫描线碰上它则 不改变标志。 2021-7-25109 2.3.3 边标志填充算法 2、特别当心多边形边界的扫描转换。在 这里就不能考虑

50、：不同的斜率产生的直线 要亮度均匀，如下图(a)所示。否则当扫描 线y遇到斜率小于1的边界线时，碰到几个 边界点，会引起标志的无序改变，将导致 填充的错误。 解决的办法：对于不同斜率的边界， 都要使用斜率大于1的直线扫描转换方法： 每次y方向增长一步，x方向增长1/m步距， 以保证扫描线y遇到斜率小于1的边界时， 只能遇到一个点。请看下图(b)。 2021-7-25110 2.3.3 边标志填充算法 在边标志填充算法中要注意多边形边界的 扫描转换 2021-7-25111 2.3.4 图案填充 前面介绍的区域填充算法，都是把区域 内部的象素全部置成同一种颜色。但在实 际应用中，有时需要用图案来

51、填充平面区 域。这可以将前面的填充算法中写象素的 那部分代码稍加修改来实现: 在确定了区域内点后，不是马上对该 象素填色，而是先将该象素映射到图案位 图的对应位置。根据图案该位置的象素值， 决定填充颜色。 2021-7-25112 2.3.4 图案填充 一、图案填充方式： 1、透明方式: 若是以透明方式填充图案，则当图案位 图的对应位置为1时，用前景色写象素，否 则，不改变该象素的值。 2、不透明方式: 而若是以不透明方式填充图案，则当图 案位图的对应位置为1时，用前景色写象素， 否则，用背景色写象素。 2021-7-25113 2.3.4 图案填充 二、图案定位法： 1、相对定位法: 把图案

52、原点与填充区域边界或内部的 某点对齐。这样，当被填充的多边形移动 时，图案也跟着移动，看起来比较自然。 对于多边形，可取边界上最左边的顶 点，而对于圆和椭圆这样具有光滑边界的 区域，则最好取区域内部某一点，如取中 心与图案原点对齐。 2021-7-25114 2.3.4 图案填充 2、绝对定位法： 把图案原点与屏幕原点对齐。该方法 可以将整个屏幕看成被要填充的图案布满， 只是要填充的区域是透明的，可以让图案 显露出来，其它区域对此图案却是不透明 的，图案被全部挡住。 这种方法比较简单，并且在相邻区域 用同一图案填充时，可以达到无缝连接的 效果。但它有一个潜在的毛病，即当区域 移动时，图案不会跟

53、着移动。其效果是区 域内的图案变了。 2021-7-25115 2.3.4 图案填充 三、图案填充算法实现 下面讨论在第二种绝对定位法下用不透明方 式对平面区域填充图案： 假设填充图案是一个MN的位图，用MN 的数组存放。M、N一般比需要填充区域的尺寸小 得多（88、1616、3232），所以图案总是 设计成周期性的，使之能通过重复使用来构成任 意尺寸的图案。当确定了区域内点p（x,y）后， 则图案位图上的对应位置为p（x%M，y%N）， 其中%为C语言整除取余运算符,然后取出图案位 图该位置的象素进行填充。 2021-7-25116 2.3.4 图案填充 四、图案填充算法程序 / 采用不透明

54、方式绝对定位法填充图案的程序伪代码: maskpixel(int x,int y,int newcolor,int backgroundcolor) int xx,yy; int maskcode88= 0,0,0,0,1,0,0,0,/*砖缝图案*/ 0,0,0,0,1,0,0,0, 0,0,0,0,1,0,0,0, 1,1,1,1,1,1,1,1, 1,0,0,0,0,0,0,0, 1,0,0,0,0,0,0,0, 1,0,0,0,0,0,0,0, 1,1,1,1,1,1,1,1 ; 2021-7-25117 2.3.4 图案填充 xx=x%8; /*多边形区域内点坐标x映射到图案 坐标x

55、x*/ yy=y%8; /*多边形区域内点坐标y到图案坐标 yy*/ if(maskcodeyyxx) putpixel(x,y, newcolor); /* newcolor 为前景色 */ else putpixel(x,y, backgroundcolor); /* backgroundcolor为背景色*/ 2021-7-25118 2.4.1 点阵字符 我们讨论的字符是指字母、数字、汉字、标 点等符号。计算机中，字符由一个数字编码唯一 标识，对于一个字符来说，它所对应的编码是由 它所属的字符集决定。 1、ASCII码 目前，国际上普遍采用的字符编码是ASCII码 （American

56、Standard Code for Information Interchange）美国信息交换标准代码。它是用七 位二进制数进行编码，共能表示128个字符，其 中编码031表示控制字符（不可显示），编码 32127表示英文字母、数字、标点符号等可显 示字符。 一个字符的ASCII码用一个字节（8位）表示， 其最高位不用或者作为奇偶校验位。 2021-7-25119 2.4.1 点阵字符 2、国标码 我国除了采用ASCII码外，还制定了汉字编码 的国家标准字符集:中华人民共和国国家标准信息 交换编码，代号为“GB231280”。该字符集共 收录常用汉字6763个，图形符号682个。 它规定所有

57、汉字和图形符号组成一个9494 的矩阵，在此方阵中，每一行称为“区”，用区 码来标识；每一列称为“位”，用位码来标识， 一个符号由一个区码和一个位码共同标识。 区码和位码分别需要7个二进制位，同样，为 了方便，各采用一个字节表示。所以在计算机中， 汉字（符号）国标码占用两个字节。 2021-7-25120 2.4.1 点阵字符 3、两种编码的区别 那么，给定一个字节，如何来确定它代表的是ASCII 码，还是国标码的区码和位码呢？通常采用字符中冗余的 最高位来标识： 最高位为0时，表示ASCII码； 最高位为1时，表示汉字编码的区码（高位字节）或 位码（低位字节）。 4、机内码 机内码： 计算机内表示字符的编码 1、西文字符 西文字符的机内码就是ASCII码。2、中文字符 国标码为：2020H+区位码的十六进制表示 机内码为：8080H+国标码 即：A0A0H+区位码的十六进制表示 2021-7-25121 2.4.1 点阵字符 3、举例 “啊”字的区位码为1601， 转换为十六进制表示应为1001H（区码16转为10H， 位码01转为01H）。 于是，“啊”字的机内码为： A0A0H+1001H=B0A1H 4、附加说明 除了机内码外，还有一个概念，即汉字输入码。 汉字输入码是为了方便人工输入汉字而