四讲二维图形填充课件.ppt

1、内容摘要内容摘要 区域填充有序边表算法边填充算法边标志算法种子填充算法圆域的填充 线宽与线型的处理直线线宽的处理（笔型：线、方形）圆弧线宽的处理（笔型：线、方形）线型的处理内容摘要内容摘要 字符 矢量字符 点阵字符 字型技术 字符裁剪 反走样基础 提高分辩率 简单的区域反走样算法 卷积积分与反走样算法 半色调技术有序边表算法有序边表算法一般多边形的一般多边形的填充过程填充过程，对于一条，对于一条扫描线扫描线Y值，可以分为值，可以分为四个步骤四个步骤：求交点求交点X：计算扫描线与多边形各计算扫描线与多边形各边的交点边的交点X的值；的值；排序：把所有相交点排序：把所有相交点x按递增顺序按递增顺序进

2、行排序；进行排序；交点配对：第一个与第二个，第三交点配对：第一个与第二个，第三个与第四个等等。每对交点就代表个与第四个等等。每对交点就代表扫描线与多边形的一个相交区间；扫描线与多边形的一个相交区间；区间填色：把这些相交区间内的象区间填色：把这些相交区间内的象素置成多边形色，把相交区间外的素置成多边形色，把相交区间外的象素置成背景色。象素置成背景色。特殊顶点处理特殊顶点处理:P1、P3情况情况:相同交点取相同交点取1个个;P2、P5情况情况:相同交点取相同交点取2个个;P4、P6情况情况:相同交点取相同交点取0个个;(下闭上开原则，防止填充扩大化下闭上开原则，防止填充扩大化)填充扩大化问题的解决

3、填充扩大化问题的解决采用采用下闭上开、左闭右开下闭上开、左闭右开原则原则，防止填充扩大化。，防止填充扩大化。例如填充左下角为（例如填充左下角为（1，1），右上角为（），右上角为（3，3）的）的区域，得到的图形如图所区域，得到的图形如图所示九个象素被点亮，而实示九个象素被点亮，而实际区域应是黄区所示。际区域应是黄区所示。采取的措施：在具体实现采取的措施：在具体实现时，只要对扫描线与多边时，只要对扫描线与多边形的相交区间取形的相交区间取“左闭右左闭右开开”。在上述讨论中，当。在上述讨论中，当扫描线与多边形顶点相交扫描线与多边形顶点相交时，所使用的交点取舍的时，所使用的交点取舍的方法，保证了多边形的

4、方法，保证了多边形的“下闭上开下闭上开”，丢弃上方水，丢弃上方水平边以及上方非水平边上平边以及上方非水平边上作为局部最高点的顶点。作为局部最高点的顶点。如左图如左图活性边与活性边表处理方法活性边与活性边表处理方法 一个多边形与若干扫描线。为了计算每条扫描线与多边形各边的交点，最简单的方法是把多边形的所有边放在一为了计算每条扫描线与多边形各边的交点，最简单的方法是把多边形的所有边放在一个表中。在处理每条扫描线时，按顺序从表中取出所有的边，分别与扫描线个表中。在处理每条扫描线时，按顺序从表中取出所有的边，分别与扫描线求交点求交点。这样处理效率很低。这是因为一条扫描线往往只与少数几条边相交，甚至与整

5、个多边这样处理效率很低。这是因为一条扫描线往往只与少数几条边相交，甚至与整个多边形都不相交。若在处理每条扫描线时，不分青红皂白地把所有边都拿来与扫描线求交形都不相交。若在处理每条扫描线时，不分青红皂白地把所有边都拿来与扫描线求交点，则其中绝大多数都是徒劳无用的。如果采用活性边表，则可减少许多计算。点，则其中绝大多数都是徒劳无用的。如果采用活性边表，则可减少许多计算。扫描线依次变化为扫描线依次变化为1,2,3,4,5,6,7,8,.x是边与当前扫描线的交点；是边与当前扫描线的交点；x是该边从当前扫描线到下一扫描线之间是该边从当前扫描线到下一扫描线之间x增量；增量；ymax是边所交的最高扫描线号。

6、是边所交的最高扫描线号。在上述的交点在上述的交点x坐标更新和新边插入之前，必须把那些与当前扫描线相交，而与下一条坐标更新和新边插入之前，必须把那些与当前扫描线相交，而与下一条扫描线不再相交的边，从活性边表扫描线不再相交的边，从活性边表(AET)中删除出去。中删除出去。新边表处理方法新边表处理方法为了方便活性边表的建立与更新，为每一为了方便活性边表的建立与更新，为每一条扫描线建立一个新边表，在该扫描线第条扫描线建立一个新边表，在该扫描线第一次出现的边保留与此。也就是说一次出现的边保留与此。也就是说若某边的较低端点为若某边的较低端点为ymin，则该边就放在扫描线则该边就放在扫描线ymin的新边表中

7、。这样，当按扫描线号从小到大顺的新边表中。这样，当按扫描线号从小到大顺序处理扫描线时，该边在该扫描线第一次出现。新边表的每个结点存放对应边的初始信息，比如序处理扫描线时，该边在该扫描线第一次出现。新边表的每个结点存放对应边的初始信息，比如该扫描线与该边的初始交点该扫描线与该边的初始交点x（即较低端点的即较低端点的x值），值），x的增量的增量 x，以及该边的最大以及该边的最大y值值ymax。图图3-18所示，为左图中各扫描线的新边表。区间填充需设置一个布尔变量所示，为左图中各扫描线的新边表。区间填充需设置一个布尔变量b,在多边形内在多边形内b为真为真,在多在多边形外边形外b为假为假,b的初值为假

8、。当指针从活性边表中第一个结点（交点）到最后一个结点遍历一次的初值为假。当指针从活性边表中第一个结点（交点）到最后一个结点遍历一次时，每访问一个结点，把时，每访问一个结点，把b取反一次。若取反一次。若b为真，则把从当前结点的为真，则把从当前结点的x值开始到下一结点的值开始到下一结点的x值结束值结束的左闭右开区间，用多边形色填充。利用区间连贯性，即同一区间上的象素取同一颜色属性。的左闭右开区间，用多边形色填充。利用区间连贯性，即同一区间上的象素取同一颜色属性。多边形外的点用背景色填充。多边形外的点用背景色填充。边填充算法边填充算法基本思想基本思想：对于每一条扫描：对于每一条扫描线和每一条多边形边

9、的交点线和每一条多边形边的交点(x xi i，y yi i)，将该扫描线上交将该扫描线上交点右方的所有象素取补。对点右方的所有象素取补。对多边形的每条边均作此处理多边形的每条边均作此处理，多边形的顺序随意。右图，多边形的顺序随意。右图为采用最简单的边填充算法为采用最简单的边填充算法填充一个多边形的示意图。填充一个多边形的示意图。边填充算法最适用于具有帧边填充算法最适用于具有帧缓冲存储器的图形系统，按缓冲存储器的图形系统，按任意顺序处理的边。任意顺序处理的边。在处理每条边在处理每条边时，仅访问与该边相交的扫描线上交点右方的象素。当所时，仅访问与该边相交的扫描线上交点右方的象素。当所有的边都被处理

10、之后，按扫描线顺序读出帧缓冲存储器的内容，送入显有的边都被处理之后，按扫描线顺序读出帧缓冲存储器的内容，送入显示设备。可见本算法的优点是简单，缺点是对于复杂图形，每一象素可示设备。可见本算法的优点是简单，缺点是对于复杂图形，每一象素可能被访问多次，输入输出的量比有序边表算法大得多。为了减少边填能被访问多次，输入输出的量比有序边表算法大得多。为了减少边填充算法访问象素的次数，可引入栅栏。所谓栅栏指的是一条与扫描线垂充算法访问象素的次数，可引入栅栏。所谓栅栏指的是一条与扫描线垂直的直线，栅栏位置通常取过多边形直的直线，栅栏位置通常取过多边形顶点、且把多边形分为左右两半。顶点、且把多边形分为左右两半

11、。栅栏填充算法栅栏填充算法基本思想基本思想是：当扫描线与是：当扫描线与多边形边有交点，就将交多边形边有交点，就将交点与栅栏之间的象素取补点与栅栏之间的象素取补。若交点位于栅栏左边，。若交点位于栅栏左边，则将交点之右，栅栏之左则将交点之右，栅栏之左的所有象素取补；若交点的所有象素取补；若交点位于栅栏右边，则将栅栏位于栅栏右边，则将栅栏之右，交点之左的象素取之右，交点之左的象素取补。如图所示，为采用栅补。如图所示，为采用栅栏填充算法填充多边形的栏填充算法填充多边形的示意图。示意图。栅栏填充算法只是减少了被重复访问的象素的数目，栅栏填充算法只是减少了被重复访问的象素的数目，但仍有一些但仍有一些象素会

12、被重复访问。从图中很容易看出这一点。下面介绍的边标志算象素会被重复访问。从图中很容易看出这一点。下面介绍的边标志算法进一步改进了栅栏填充算法，使得算法对每个象素仅访问一次。算法进一步改进了栅栏填充算法，使得算法对每个象素仅访问一次。算法示意图如下页所示。法示意图如下页所示。边标志算法边标志算法基本思想基本思想是：分为两步骤，第一步，对多边形的每条边进行直线扫描变换，亦即对多边形是：分为两步骤，第一步，对多边形的每条边进行直线扫描变换，亦即对多边形边界所经过的象素打上标志；第二步，填充。对每条与多边形相交的扫描线，依从左到右边界所经过的象素打上标志；第二步，填充。对每条与多边形相交的扫描线，依从

13、左到右顺序，逐个访问该扫描线上象素。使用一个布尔量顺序，逐个访问该扫描线上象素。使用一个布尔量inside来指示当前点的状态，若点在多来指示当前点的状态，若点在多边形内，则边形内，则inside为真。若点在多边形外，则为真。若点在多边形外，则inside为假。为假。inside的初始值为假的初始值为假，每当访问，每当访问到象素为被打上边标志的点时，就把到象素为被打上边标志的点时，就把inside取反。对未打标志的象素，取反。对未打标志的象素，inside不变。若访问不变。若访问象素时，象素时，inside为真，则把该象素置为多边形色。用软件实现时，有序边表算法与边标志为真，则把该象素置为多边形

14、色。用软件实现时，有序边表算法与边标志算法的执行速度几乎相同，但由于在帧缓冲存储器中应用边标志算法时，不必建立、维护算法的执行速度几乎相同，但由于在帧缓冲存储器中应用边标志算法时，不必建立、维护边表以及对它进行排序，所以边标志算法更适合于硬件实现，这时它的执行速度比有序边边表以及对它进行排序，所以边标志算法更适合于硬件实现，这时它的执行速度比有序边表算法快到一至两个数量级。表算法快到一至两个数量级。种子填充算法的连通区域种子填充算法的连通区域基本思想是是前面讨论的填充算法都前面讨论的填充算法都是按扫描线的顺序进行象素点的填是按扫描线的顺序进行象素点的填充的，种子填充算法是根据已知的充的，种子填

15、充算法是根据已知的一个多边形区域内部的一个象素点一个多边形区域内部的一个象素点来找到区域内其它的象素点进行填来找到区域内其它的象素点进行填充的。充的。前面讨论的填充算法都是按扫描线前面讨论的填充算法都是按扫描线的顺序进行象素点的填充的，种子的顺序进行象素点的填充的，种子填充算法是根据已知的一个多边形填充算法是根据已知的一个多边形区域内部的一个象素点来找到区域区域内部的一个象素点来找到区域内其它的象素点进行填充的。内其它的象素点进行填充的。一般都采用边界定义区域，即边界区域上所有象素被置为特定值，而区域内部所有的一般都采用边界定义区域，即边界区域上所有象素被置为特定值，而区域内部所有的象素均不取

16、这个值。区域可以分为四连通或八连通两种，如果区域是四连通的，那么象素均不取这个值。区域可以分为四连通或八连通两种，如果区域是四连通的，那么区域内每一个象素可以通过四个方向（上、下、左、右）组合到达，而对八连通区域区域内每一个象素可以通过四个方向（上、下、左、右）组合到达，而对八连通区域，区域内的每个象素可通过上、下、左、右以及四个对角线方向的移动组合到达。，区域内的每个象素可通过上、下、左、右以及四个对角线方向的移动组合到达。八连通算法可以填充四连通区域，而四连通算法不能填充八连通区域。两类连通区域八连通算法可以填充四连通区域，而四连通算法不能填充八连通区域。两类连通区域如图所示。图如图所示。

17、图(b)b)中八连通区域的子区域是四连通的，然而从一个子区域到另一个子中八连通区域的子区域是四连通的，然而从一个子区域到另一个子区域需用八连通算法，若每个子区域看成是分离的二个四连通区域，并且每个区域填区域需用八连通算法，若每个子区域看成是分离的二个四连通区域，并且每个区域填上不同的色彩值，如果用八连通算法会让两个区域均被错误地填上同样的色彩。下面上不同的色彩值，如果用八连通算法会让两个区域均被错误地填上同样的色彩。下面仅讨论四向连通算法仅讨论四向连通算法,只要把搜索方向从四个该为八个只要把搜索方向从四个该为八个,即可得到八向算法。即可得到八向算法。简单种子填充算法简单种子填充算法简单的种子填

18、充算法如下：简单的种子填充算法如下：(1)(1)将种子象素压入栈中；将种子象素压入栈中；(2)(2)当栈非空时当栈非空时从栈中弹出一个象素；从栈中弹出一个象素；将该象素置成所要求的色彩值；将该象素置成所要求的色彩值；检查每个与当前象素邻接的四连通检查每个与当前象素邻接的四连通象素是否是边界色或已置成所要求象素是否是边界色或已置成所要求的色彩值，若是则返回的色彩值，若是则返回(2)(2)，否则将，否则将该象素压入栈中回到该象素压入栈中回到(2)(2)。例例 简单的种子填充算法。简单的种子填充算法。多边形由顶点多边形由顶点P0P0、P1P1、P2P2、P3P3、P4P4构成，见图构成，见图3-23

19、3-23。P0P0（1 1，5 5）、）、P1(5P1(5，5)5)、P2(7P2(7，3)3)、P3(7P3(7，1)1)、P4(1P4(1，1)1)，可设种子点为可设种子点为(3(3，3)3)；四连通的组合方向是上、下、左；四连通的组合方向是上、下、左、右。初始时栈中只有右。初始时栈中只有(3(3，3)3)象素；弹出象素；弹出(3(3，3)3)，由于该象素未置成色彩值且也不是边，由于该象素未置成色彩值且也不是边界色，故填色彩值；同时将界色，故填色彩值；同时将(3(3，4)(34)(3，2)(22)(2，3)3)及及(4(4，3)3)压入栈中；栈中有四个压入栈中；栈中有四个元素；弹出元素；弹

20、出(4(4，3)3)并置上要求的色彩值，再将并置上要求的色彩值，再将(4(4，4)(44)(4，2)(52)(5，3)3)压入栈中；栈中压入栈中；栈中有有6 6个元素；依次类推，象素被选中并填充的次序如图中箭头所示。当栈为空时，算个元素；依次类推，象素被选中并填充的次序如图中箭头所示。当栈为空时，算法终止。分析该算法不难发现，在进行填充过程中堆栈会变得很大，而且在堆栈中还法终止。分析该算法不难发现，在进行填充过程中堆栈会变得很大，而且在堆栈中还常常包含有一些重复的和不必要的信息。为此提出了扫描线种子填充算法。常常包含有一些重复的和不必要的信息。为此提出了扫描线种子填充算法。扫描线种子填充算法扫

21、描线种子填充算法所谓扫描线种子填充算法，是在任意所谓扫描线种子填充算法，是在任意不间断扫描线区间中只取一个种子象不间断扫描线区间中只取一个种子象素。不间断区间即指在一条扫描线上素。不间断区间即指在一条扫描线上一组相邻的元素。一组相邻的元素。算法可分为以下几步算法可分为以下几步：1 1）从包含种子象素的栈中弹出种子从包含种子象素的栈中弹出种子象素；象素；2 2）沿着扫描线对种子象素进行填充，）沿着扫描线对种子象素进行填充，直到遇到边界象素为止，这样就填充直到遇到边界象素为止，这样就填充了种子所在的扫描线中的元素；了种子所在的扫描线中的元素；3 3）区间内最左、最右元素为）区间内最左、最右元素为X

22、leftXleft，Xright;Xright;则在则在Xleft Xleft X X Xright Xright区间中检查区间中检查与当前扫描线相邻的上、下两条扫描与当前扫描线相邻的上、下两条扫描线是否全为边界象素或已填充过的象线是否全为边界象素或已填充过的象素。若不是，则对于素。若不是，则对于Xleft Xleft X X XrighXrigh，把与当前扫描线相邻的上、下把与当前扫描线相邻的上、下两条扫描线中该区间的最右象素作为两条扫描线中该区间的最右象素作为种子压入栈中。种子压入栈中。算法结束条件为栈空。此算法适用于算法结束条件为栈空。此算法适用于用边界定义的区域。用边界定义的区域。圆域

23、的填充圆域的填充上面所讨论的多边形区域的填充原理也可以推广到圆域的填充。对每条扫描线，先计算它与圆域的相交区间，再把区间内象素用指定颜色填充。在实际应用中，除了使用单象素宽的线条，还经常使用指定线宽和线型的直线与弧线。欲产生在实际应用中，除了使用单象素宽的线条，还经常使用指定线宽和线型的直线与弧线。欲产生具有宽度的线，可以顺着扫描所生成的单象素线条轨迹，移动一把具有一定宽度的具有宽度的线，可以顺着扫描所生成的单象素线条轨迹，移动一把具有一定宽度的“刷子刷子”来来获得。获得。“刷子刷子”的形状可以是一条线段或一个正方形。也可以采用区域填充的办法间接地产生的形状可以是一条线段或一个正方形。也可以采

24、用区域填充的办法间接地产生有宽度的线。假设直线斜率有宽度的线。假设直线斜率在在 1 1，11之间，这里可以把刷子置成之间，这里可以把刷子置成垂直垂直方向，刷子的中点对准方向，刷子的中点对准直线一端点，然后让刷子中心往直线的另一端移动，即可直线一端点，然后让刷子中心往直线的另一端移动，即可“刷出刷出“具有一定宽度的线。当直线具有一定宽度的线。当直线斜率不在斜率不在 1 1，11之间时，把刷子置成水平方向。具体实现线刷子时，只要对直线扫描变换算之间时，把刷子置成水平方向。具体实现线刷子时，只要对直线扫描变换算法的内循环稍作修改即可。例如，当直线斜率在法的内循环稍作修改即可。例如，当直线斜率在 1

25、1，11之间时，把每步迭代所得的点的上下之间时，把每步迭代所得的点的上下方半线宽之内的象素全部置成直线颜色。如右上图所示为线宽是方半线宽之内的象素全部置成直线颜色。如右上图所示为线宽是5 5个象素的情形。线刷子的优点个象素的情形。线刷子的优点是算法简单、是算法简单、效率高效率高。但是，线的始末端总是水平或垂直的。因此，当线宽较大时，看起来很。但是，线的始末端总是水平或垂直的。因此，当线宽较大时，看起来很不自然。当比较接近水平的线与比较接近垂直的线汇合时，不自然。当比较接近水平的线与比较接近垂直的线汇合时，汇合处外角将有缺口汇合处外角将有缺口,如左上如左上图所示图所示。斜线与水平（或垂直）线。斜

26、线与水平（或垂直）线不一样粗不一样粗。对于水平线或垂直线，刷子与线条垂直，因而最。对于水平线或垂直线，刷子与线条垂直，因而最粗粗。其。其粗细与指定线宽相等。而对于粗细与指定线宽相等。而对于45 斜线斜线，刷子与线条成，刷子与线条成45 角，粗细仅为指定线宽的角，粗细仅为指定线宽的1/2 0.7倍倍。直线线宽的处理直线线宽的处理 线刷子原理为用正方形刷子绘制的具有宽度的线条。用方形刷子所得的线条比用线刷为用正方形刷子绘制的具有宽度的线条。用方形刷子所得的线条比用线刷子所绘制的线条要粗一些。与线刷子类似，用方刷子绘制的线条始末端也子所绘制的线条要粗一些。与线刷子类似，用方刷子绘制的线条始末端也是水

27、平或垂直的，且线宽与线条方向有关。与线刷子的情形相反，对于水是水平或垂直的，且线宽与线条方向有关。与线刷子的情形相反，对于水平线与垂直线，线宽最小，而对于斜率为平线与垂直线，线宽最小，而对于斜率为 1的线条，线宽最大，为垂直（的线条，线宽最大，为垂直（水平）的水平）的 2 倍。倍。实现正方形刷子最简单的办法是，把方形中心对准单象素实现正方形刷子最简单的办法是，把方形中心对准单象素宽的线条上各个象素，并把方形内的象素全部置成线条颜色。这种简单方宽的线条上各个象素，并把方形内的象素全部置成线条颜色。这种简单方法将会重复地写象素。这是因为对应于相邻象素的方形一般会重迭。为了法将会重复地写象素。这是因

28、为对应于相邻象素的方形一般会重迭。为了避免重复写象素，可以采用与活性边表类似的技术。避免重复写象素，可以采用与活性边表类似的技术。方形刷子的原理方形刷子的原理线刷子还有线刷子还有另一个问题另一个问题：当线宽为偶数个象素：当线宽为偶数个象素时，用上述方法绘制的时，用上述方法绘制的线条要么粗一个象素，线条要么粗一个象素，要么细一个象素。为了要么细一个象素。为了生成有宽度的线，还可生成有宽度的线，还可以用方形的刷子，把边以用方形的刷子，把边宽为指定线宽的正方形宽为指定线宽的正方形的中心沿直线作平行移的中心沿直线作平行移动，即可获得具有线宽动，即可获得具有线宽的线条，如图所示的线条，如图所示方刷子的活

29、性边表技术方刷子的活性边表技术为每条扫描线建一个表，为每条扫描线建一个表，存放该扫描线与线条的相存放该扫描线与线条的相交区间左右端点位置。在交区间左右端点位置。在每个象素使用方形刷子时每个象素使用方形刷子时，用该方形与各扫描线的，用该方形与各扫描线的相交区间端点坐标去更新相交区间端点坐标去更新原表内端点数据，右图为原表内端点数据，右图为刷子移动的相邻两步与有刷子移动的相邻两步与有关扫描线的临时数据结构关扫描线的临时数据结构所保存的对应于各步的区所保存的对应于各步的区间端点坐标。间端点坐标。生成具有宽度的线条还可生成具有宽度的线条还可以采用区域填充的算法。以采用区域填充的算法。先算出线条各角点，

30、再用先算出线条各角点，再用直线段把相邻角点连接起直线段把相邻角点连接起来，最后调用多边形填充算法把所得的四边形进行填色，即得到来，最后调用多边形填充算法把所得的四边形进行填色，即得到具有宽度的线条。用这种方法还可以生成两端粗细不一样的线条具有宽度的线条。用这种方法还可以生成两端粗细不一样的线条圆弧线宽的处理（笔）圆弧线宽的处理（笔）为了生成为了生成具有宽度的圆弧具有宽度的圆弧，可采用与直线情形类似的方法，当采用，可采用与直线情形类似的方法，当采用线刷子线刷子时，在经过曲线斜率为时，在经过曲线斜率为 1 1的点时，必须把线刷子在水平与垂直方向之间的点时，必须把线刷子在水平与垂直方向之间切换。由于

31、线刷子总是置成水平或垂直的，所以在曲线接近水平与垂直的切换。由于线刷子总是置成水平或垂直的，所以在曲线接近水平与垂直的地方，线条更粗一些，而在斜率接近地方，线条更粗一些，而在斜率接近 1 1的点附近，线条更细一些，如右的点附近，线条更细一些，如右上图所示。当采用上图所示。当采用正方形刷子正方形刷子时，无需移动刷子方向。只需顺着单象素的时，无需移动刷子方向。只需顺着单象素的轨迹，把正方形中心对准轨迹上的象素，把方形内的象素全部用线条颜色轨迹，把正方形中心对准轨迹上的象素，把方形内的象素全部用线条颜色填充。用正方形刷子绘制的曲线条，在接近水平与垂直的部分最细，而在填充。用正方形刷子绘制的曲线条，在

32、接近水平与垂直的部分最细，而在斜率为斜率为 1 1的点附近最粗，这恰与线刷子情形相反，如左上图所示。的点附近最粗，这恰与线刷子情形相反，如左上图所示。圆弧线宽的处理圆弧线宽的处理(填充法填充法)绘制具有宽度的绘制具有宽度的圆弧线条也可以圆弧线条也可以采用填充的办法采用填充的办法，先绘制圆弧线，先绘制圆弧线条的内边界和外条的内边界和外边界，然后在内边界，然后在内外边界之间对其外边界之间对其填色。可以让内填色。可以让内外边界都与单象外边界都与单象素弧线轨迹距离半线宽，或把内外边界之一对准单象素素弧线轨迹距离半线宽，或把内外边界之一对准单象素弧线轨迹弧线轨迹,另一边界线离开此线一个线宽距离。如图所示

33、另一边界线离开此线一个线宽距离。如图所示为采用填充方法所得的圆弧线条示意图。为采用填充方法所得的圆弧线条示意图。线型的处理线型的处理在绘图应用中常用到不同线型的线条，以便区分各种不同的意义。在绘图应用中常用到不同线型的线条，以便区分各种不同的意义。实线实线:可见的轮廓线可见的轮廓线;虚线虚线:不可见的轮廓线不可见的轮廓线;点划线点划线:中心线等等。中心线等等。线型可以用一个布尔值的序列来存放。例如，用一个线型可以用一个布尔值的序列来存放。例如，用一个3232位整数可以存位整数可以存放放3232个布尔值。用这样的整数存放线型定义时，线型必须以个布尔值。用这样的整数存放线型定义时，线型必须以323

34、2个象素个象素为周期进行重复。可以把扫描变换算法中的无条件写象素语句改为为周期进行重复。可以把扫描变换算法中的无条件写象素语句改为if(bitstringi%32)WritePixel(xif(bitstringi%32)WritePixel(x，y y，value);value);其中其中i i为循环变量为循环变量，在扫描变换算法的内循环中每处理一个象素递增在扫描变换算法的内循环中每处理一个象素递增1 1，然后除以，然后除以3232取余取余(“%”(“%”为为C C语言中求模运算符语言中求模运算符),),余数变化范围是余数变化范围是0 0 3131。例子例子:bitstring=bitstr

35、ing=11111111110000000000111111111100 11111111110000000000111111111100用这种简单办法实现的线型有个毛病。因为每位对应于算法的一个迭用这种简单办法实现的线型有个毛病。因为每位对应于算法的一个迭代步骤而不是线条上一个长度单位，因此线型中虚实笔划长度与直线代步骤而不是线条上一个长度单位，因此线型中虚实笔划长度与直线倾斜度有关，斜线上的笔划长度比横向或竖向上的笔划更长倾斜度有关，斜线上的笔划长度比横向或竖向上的笔划更长,这在工程这在工程图上是不允许的。所以图上是不允许的。所以,受影响的笔划应该作为单独线段进行计算和扫受影响的笔划应该作

36、为单独线段进行计算和扫描变换描变换,使其长度不随线的倾斜度的变化而变。以实心或透明使其长度不随线的倾斜度的变化而变。以实心或透明矩形矩形交替交替序列画出的粗线序列画出的粗线,各矩形顶点作为所选线型函数精确地计算。然后分别各矩形顶点作为所选线型函数精确地计算。然后分别对单个钜形进行扫描变换。对于垂直或水平的粗线线型，可以用复制对单个钜形进行扫描变换。对于垂直或水平的粗线线型，可以用复制矩形完成。矩形完成。线形和笔型在粗轮廓图元中相互作用，线型用于计算每一个笔画的矩线形和笔型在粗轮廓图元中相互作用，线型用于计算每一个笔画的矩形，而每一个矩形的填充则是用所选择的笔型。形，而每一个矩形的填充则是用所选

37、择的笔型。字符字符讨论的字符是指数字、字母、汉字等符号，用于图形的标注、说明等。国讨论的字符是指数字、字母、汉字等符号，用于图形的标注、说明等。国际上最流行的字符集是际上最流行的字符集是“美国信息交换用标准代码集美国信息交换用标准代码集“（American Standard Code for Information Interchange），），简称简称ASCII码。该字符集规码。该字符集规定了定了127个字符代码。其中代码个字符代码。其中代码031表示控制字符，代码表示控制字符，代码32127表示英文表示英文字母、标点符号、数字符号、各种运算符以及特殊符号。每个字母、标点符号、数字符号、各种

38、运算符以及特殊符号。每个ASCII码用码用一个字节（实际上只要七位二进制）代码表示。一个字节（实际上只要七位二进制）代码表示。我国除采用我国除采用ASCII码外，还另外制订了汉字代码的国家标准字符集。最常码外，还另外制订了汉字代码的国家标准字符集。最常用的字符集是用的字符集是”信息交换用汉字编码字符集基本集信息交换用汉字编码字符集基本集”GB231280。该字符该字符集包含了六千多个常用汉字，以及英文字母、数字和其它图形符号。分成集包含了六千多个常用汉字，以及英文字母、数字和其它图形符号。分成94个区个区94个位。区码和位码各用一个字节（实际上只要七位二进制）来表个位。区码和位码各用一个字节（

39、实际上只要七位二进制）来表示。为了能识别哪些字节表示示。为了能识别哪些字节表示ASCII码，哪些字节表示汉字编码，一般采码，哪些字节表示汉字编码，一般采用多余的一位（最高位）来标识。最高位为用多余的一位（最高位）来标识。最高位为0时，表示时，表示ASCII码，最高位为码，最高位为1时表示汉字编码。为了在终端显示器或绘图仪上输出字符，系统中必须装时表示汉字编码。为了在终端显示器或绘图仪上输出字符，系统中必须装备有相应的字符库。字符库中储存了每个字符的形状信息。字符库分为矢备有相应的字符库。字符库中储存了每个字符的形状信息。字符库分为矢量型和点阵型两种。量型和点阵型两种。在笔式绘图仪上采用矢量型字

40、符比较适合，矢量型字符库采用矢量代码序在笔式绘图仪上采用矢量型字符比较适合，矢量型字符库采用矢量代码序列表示字符的各个笔画，输出一个字符时，系统中的字符处理器解释该字列表示字符的各个笔画，输出一个字符时，系统中的字符处理器解释该字符的每个矢量代码，输出对应的矢量，达到产生字符的目的。在终端显示符的每个矢量代码，输出对应的矢量，达到产生字符的目的。在终端显示器上显示字符一般采用点阵型字符库。点阵型字符库为每个字符定义一个器上显示字符一般采用点阵型字符库。点阵型字符库为每个字符定义一个字符掩膜，即表示该字符的象素图案的一个点阵。字符掩膜，即表示该字符的象素图案的一个点阵。矢量字符矢量字符为了建立一

41、个矢量字符库，必须对每个字符定义一个矢量代码序列，下面以为了建立一个矢量字符库，必须对每个字符定义一个矢量代码序列，下面以AutoCAD系统使用的矢量字符来说明。在系统使用的矢量字符来说明。在AutoCAD中，使用一种称为形（中，使用一种称为形（shape）的图形实体来定义西文字符、汉字甚至一些简单的图形。形定义中使用直线和圆弧的图形实体来定义西文字符、汉字甚至一些简单的图形。形定义中使用直线和圆弧作为基本笔划。作为基本笔划。每个形的定义包括一个标题行和若干个描述行：每个形的定义包括一个标题行和若干个描述行：*形编号，字节数，形名称字节形编号，字节数，形名称字节1字节字节2，0标题行中，形编号

42、是标题行中，形编号是1到到255的整数值。字节数表示形定义描述行中包括结束符的整数值。字节数表示形定义描述行中包括结束符0在内在内的字节数目。形名称用大写字母才可以被调用，否则只作为形的一种解释性信息，的字节数目。形名称用大写字母才可以被调用，否则只作为形的一种解释性信息，不存入存储器，因而不占用存储空间。不存入存储器，因而不占用存储空间。描述行由若干个用逗号隔开的字节组成，并以描述行由若干个用逗号隔开的字节组成，并以0作为形定义的结束字节。带有前缀作为形定义的结束字节。带有前缀0的字节是十六进制。无前缀的字节是十六进制。无前缀0的字节是十进制。描述行中的每个字节包含矢量长度和的字节是十进制。

43、描述行中的每个字节包含矢量长度和方向两种信息。字节的低四位表示矢量方向，高四位表示矢量长度。矢量的方向编方向两种信息。字节的低四位表示矢量方向，高四位表示矢量长度。矢量的方向编码如图所示。注意，图码如图所示。注意，图3-32中所有矢量都具有中所有矢量都具有“相同相同“的长度，即不同方向的矢量的长度，即不同方向的矢量的长度不一样。例如，的长度不一样。例如，45 方向的矢量一个单位长相当于水平方向的方向的矢量一个单位长相当于水平方向的 2 单位长。单位长。图所示的二极管符号的形定义为：图所示的二极管符号的形定义为：*133，11，DIODE040，044，04C，042，04C，040，048，0

44、4C，046，04C，0形描述的第一个字节形描述的第一个字节040中，最高位中，最高位0表示表示本字节为十六进制数。后面两位数本字节为十六进制数。后面两位数4和和0分分别表示字节的高四位和低四位。高四位的别表示字节的高四位和低四位。高四位的4表示矢量长度为表示矢量长度为4，低四位的，低四位的0表示矢量表示矢量方向为水平向右方向。方向为水平向右方向。点阵字符点阵字符在点阵字符库中，每个字符都定义成一个字符掩膜的矩阵。矩阵中的每个在点阵字符库中，每个字符都定义成一个字符掩膜的矩阵。矩阵中的每个元素都是一位二进制数。该位为元素都是一位二进制数。该位为1时，表示字符的笔划经过此位，对应于此时，表示字符

45、的笔划经过此位，对应于此位的象素应置为字符颜色；该位为位的象素应置为字符颜色；该位为0时，表示字符的笔划不经过此位置，对时，表示字符的笔划不经过此位置，对应此位的象素应置为背景色（若当前的写方式是应此位的象素应置为背景色（若当前的写方式是“替换替换“方式）或不改变方式）或不改变（若当前写方式是（若当前写方式是“与与“方式）。一般认为定义西文字符的掩膜矩阵尺寸方式）。一般认为定义西文字符的掩膜矩阵尺寸应不小于应不小于5 7，而定义汉字字符的掩膜矩阵尺寸应不小于，而定义汉字字符的掩膜矩阵尺寸应不小于16 16。在我国广。在我国广泛使用的微机汉字系统，如泛使用的微机汉字系统，如CCDOS等等，都采用

46、等等，都采用16 16点阵汉字作为显示点阵汉字作为显示用字符，而在打印时，采用用字符，而在打印时，采用24 24，40 40甚至甚至72 72的点阵字符。的点阵字符。一个一个5 7西文字符点阵包括西文字符点阵包括35个点，需要个点，需要35位，故需要位，故需要35位二进制数（占四位二进制数（占四个多字节），一个个多字节），一个16 16点阵汉字，需要点阵汉字，需要256位，即位，即32个字节。而一个个字节。而一个72 72点阵汉字需要点阵汉字需要9 72=648个字节。个字节。用于打印的高分辩率点阵字符的掩膜位图，可以是通过用扫描仪输入放大用于打印的高分辩率点阵字符的掩膜位图，可以是通过用扫描

47、仪输入放大的手写美术字符或印刷字符，扫描输入进来的字符可用交互作图程序对位的手写美术字符或印刷字符，扫描输入进来的字符可用交互作图程序对位图的个别象素进行修改，使之完善。用于显示的或用于低分辩率打印机的图的个别象素进行修改，使之完善。用于显示的或用于低分辩率打印机的字符位图可以使用交互绘图程序，通过手工建立。用低分辩率点阵字符产字符位图可以使用交互绘图程序，通过手工建立。用低分辩率点阵字符产生的字符一般比较粗糙，不美观，所以在微机上通常使用几个不同分辩率生的字符一般比较粗糙，不美观，所以在微机上通常使用几个不同分辩率的字符库，以满足不同的需要，例如在的字符库，以满足不同的需要，例如在CCDOS

48、4.0中就使用了中就使用了24种不同的种不同的字符库。字符库。字型技术字型技术当应用对输出字符的要求较高时（如排版印刷），需要使用高质量的点阵字符。然而当应用对输出字符的要求较高时（如排版印刷），需要使用高质量的点阵字符。然而直接使用上一小节所介绍的点阵字符方法将耗费巨大的存储空间。对于直接使用上一小节所介绍的点阵字符方法将耗费巨大的存储空间。对于GB231280所所规定的规定的6763个基本汉字，假设每个汉字是个基本汉字，假设每个汉字是72 72点阵，那么一个字库就需要点阵，那么一个字库就需要4.4兆字节兆字节存储空间！在实际使用时，需要多种字体（如基本体、宋体、仿宋体、黑体、楷体等存储空间

49、！在实际使用时，需要多种字体（如基本体、宋体、仿宋体、黑体、楷体等），而每种字体又需要十种以上字号。因此把每种字体、字号的字符都存储一个对应），而每种字体又需要十种以上字号。因此把每种字体、字号的字符都存储一个对应的点阵，在一般情况是不可行的。的点阵，在一般情况是不可行的。解决这个问题一般采用压缩技术。对字型数据压缩后再存储，使用时，解决这个问题一般采用压缩技术。对字型数据压缩后再存储，使用时，将压缩的数据将压缩的数据还原为字符位图点阵还原为字符位图点阵。压缩方法有多种，最简单的有。压缩方法有多种，最简单的有黑白段压缩黑白段压缩法，这种方法简单，法，这种方法简单，还原快，不失真，但压缩较差，使

50、用起来也不方便，一般用于低级的文字处理系统中还原快，不失真，但压缩较差，使用起来也不方便，一般用于低级的文字处理系统中，二是，二是部件压缩法部件压缩法。这种方法压缩比大，缺点是字型质量不能保证。三是。这种方法压缩比大，缺点是字型质量不能保证。三是轮廓字型法轮廓字型法，这种方法压缩比大，且能保证字符质量，是当今国际上最流行一种方法，基本上也，这种方法压缩比大，且能保证字符质量，是当今国际上最流行一种方法，基本上也被认为是符合工业标准化的方法。轮廓字型法采用直线、或者二三次被认为是符合工业标准化的方法。轮廓字型法采用直线、或者二三次/Bezier曲线曲线的的集合来描述一个字符的轮廓线。轮廓线构成一