《区域填充讲义》由会员分享，可在线阅读，更多相关《区域填充讲义（125页珍藏版）》请在金锄头文库上搜索。
1、,第四章 二维图形生成和变换技术 4.1 基本绘图元素 4.2 直线段的生成 4.3 曲线的生成 4.4 区域填充 4.5 二维图形变换 4.6 二维图像剪裁,4.4区域填充,区域是指相互连通的一组像素的集合。区域通常由一个封闭的轮廓来定义，处于一个封闭轮廓线内的所有像素点即构成一个区域。所谓区域填充就是将区域内的像素置成新的颜色值或图案。区域填充是计算机绘图的一种基本操作，相当一部份绘图都用到它。对于区域填充来说，它要解决两个问题： 确定需要填充哪些象素， 确定用什么颜色或图案。,处于一个封闭轮廓线内的所有像素点即构成一个区域,区域填充就是将区域内的像素置成新的颜色值或图案,我们知道多边形是
2、常用基本图形，它是由一组边围成，封闭区域，多边形也可以是凸、凹或是带空洞。多边形区域填充就是将区域内的像素置成新的颜色值或图案。由于任何一个封闭曲线都可以用多边形来逼近，所以多边形填充实用面广。,一、多边形区域填充,1区域内部点判断准则 区域填充首先判断一个象素点是否处于多边形区域内,其判断准则如下：从该点向无穷远处引出一条射线（也称扫描线），若射线与区域边界交点目标数目为奇数，则此点在区域内。若射线与区域边界交点目标数目为偶数，则此点为区域外点。 例如：,A点向右引射线与区域边界共3个交点，为内点,B点向右引射线与区域边界共2个交点，为外点,A,B,此时应注意两点： （1）当扫描线与多边形相
3、交如下情况时:,Y,X,A,I,B,E,D,C,F,A、若两相邻边与扫描线相交于同一点，且两边位于扫描线同侧，则视为两个交点。 如yb：1点向右交点为3个（奇数）是内点 3点向右交点为4个（偶数）是外点 B、若两相邻边与扫描线相交于同一点，且两边位于扫描线异侧，则视为一个交点。 如ya,yb,3,1,ya,（2）当扫描线重合多边形某条边界水平线时，如该水平边线前后两条边线是一上一下的，则该水平边线两个端点作为两个交点，即扫描线与该水平边界线相交了两次。如下图yCB,X,Y,D,C,B,A,E,如该水平边线前后两条边线是同为上或同为下的，则只将该水平边线某一端点作为交点，即扫描线与该水平边界线相
4、交了一次。如yDE,yCB,yDE,2边相关性及边记录很显然，不能利用区域内部点判别准则对显示平面上每个点逐个判别，这样计算量太大。事实上，相对于一个给定多边形区域来说，显示平面上每个象素点内外特性是互相关联的。相邻象素间具有相关属性。在实施多边形填充时，利用扫描线相关性，就无需对扫描线上所有象素点逐个地进行内外特性判断，只需对一条扫描线从左到右求出该扫描线与区域边界交点，这些交点必将扫描线分成内外交替线段，这些交点x值大小依次排列。,X,Y,A,B,C,D,如上图，按x从小到大排列为A B C D 交点AB间线段上象素点必在区域内。 所以关键是求交点。,（1）交点计算 多边形填充首先需要求出
5、扫描线与边界的交点，利用边的相关性可以简单有效地解决这个问题。当一条扫描线yi 与多边形的某一边线有交点时，其相邻扫描线yi+1一般也与该边线相交（除非yi+1超出了该边线所在区间），而且扫描线yi+1与该边线的交点，很容易从前一条扫描线yi与该边的交点递推求得。设某条直线边的方程为 y=mx+b该边两个端点坐标为（x1,y1)、（x2,y2) 且x1x2 则该边斜率为m=(y2-y1)/(x2-x1) 令扫描线yi与该边交点为（xi，yi）扫描线yi1与该边交点（xi1，yi1）,yi,(xi,yi),边线AB,第yi条扫描线与某边线AB的交点是(xi,yi),第yi+1条扫描线与AB的交点
6、为（xi+1, yi+1 ）,则第yi+1条扫描线与AB的交点为yi+1=yi+1, xi+1=xi+1/m 即由前一条扫描线交点Xi，Yi求下 一条扫描线交点Xi1，Yi+1,式中，m是这条边的斜率。,（xi+1, yi+1),边线AC,-1/m,（2）边记录利用边的这种相关性，不必算出边线与各条扫描线的全部交点，只需以边线为单位，对每条边建立一个边记录，其内容包括：该边y的最大值ymax ,该边底端的x坐标xi,从一条扫描线到下一条扫描线间的x增量1/m,以及指示下一个边记录地址的指针,AB,AC,ymax xi 1/m,ymax xi 1/m,3边表ET和活动边表AET （1）边表ET
7、边表是一个包含多边形全部边记录的表，它按y坐标（与扫描线一一对应）递增（或递减）的顺序存放区域边界的所有边。每个y坐标值存放一个或者说几个边记录。当某条扫描线yi碰到多边形边界的新边时（以边线底端为准），则在ET表中相应的y坐标值处写入一个边记录。当同时有多条边进入时，则在ET表中按链表结构写入相应数目的多个记录，这些记录是按边线较低端点的x值增加的顺序排列。当没有新边加入时，表中对应的y坐标值处存储内容为空白。,注意：在ET表中：与x轴平行的边不计入。多边形的顶点分为两大类：一类是局部极值点，如下图中的P1、P3；另一类是非极值点，如下图中的P2、P4、P5。当扫描线与第一类顶点相遇时，应看
8、作两个点；当扫描线与第二类顶点相遇时，应视为一个点。,图4.41多边形边表多边形边表边表,活动边表AET活动边表AET是一个只与当前扫描线相交的边记录链表。随着扫描线从一条到另一条的转换，AET表也应随之变动，利用 yi+1=yi+1, xi+1=xi+1/m可以算出AET表中x域中的新值xi。凡是与这另一条扫描线相交的任何新边都加到AET表中，而与之不相交的边又被从AET表中删除掉了。下图列出了图4.40中多边形在扫描线为4、5、6时的AET表。AET表中的记录顺序仍是按x增大排序的。,6,4多边形区域填充算法过程 （1）根据给出的顶点坐标数据，按y递增顺序建立ET表 （2）根据AET指针，
9、使之为空。 （3）使yi=Ymin （Ymin为顶点坐标中最小y值）。 （4）反复做下述各步，直至yi=Ymax（顶点坐标中y的最大值）或ET与AET为空：将ET表加入到AET中，并保持AET链中的记录按x值增大排序。对扫描线yi依次成对取出AET中xi值，并在每对xi之间填上所要求的颜色或图案。从AET表中删去yi=ymax的记录。对保留下来的AET中的每个记录，用xi+1/m代替xi，并重新按x递增排序。使yi+1，以便进入下一轮循环。,开始y1，将ET表中y1结点加入至AET表，同时保持AET链中记录按x增大排序,由于上例中是66，是顶点，所以中间不填象素颜色。,上例由于而Ymax3和5
10、，所以不必删去，当yi3时，此时 就得将第一个结点即（3，6，2）删去。 对保留下来的AET中的每个记录，用xi+1/m代替xi，并重新按x递增排序。如上例变成(实际求出y=2时新的交点x坐标）,使yi+1，以便进入下一轮循环。即y2再进入以上循环 继续：由y2，ET表中是空，所以不需ET表加入AET表取x4和x6.5,将46.5之间填上象素颜色。由于y=2,不必删去结点。再改变xi的值为使yi 3，重复继续。继续：由y3，将ET表中y3结点加入，即将27之间填上象素颜色。删去结点Ymax3 结点。,再改变xi的值为使yi 4，重复继续。,二、 边填充 边填充算法的基本原理是： （1）对多边形
11、的每条边进行直线扫描转换，即对多边形边界经过的像素打上边标志； （2）对多边形内部进行填充。填充时，对每条扫描线，依从左到右的顺序，逐个访问扫描线上的像素，用一个布尔量来标志当前点是在多边形内部还是外部（一开始设布尔量的值为假，当碰到设有边标志的点时，就把其值取反；对没有边标志的点，则其值保持不变） （3）将其布尔量值为“真”的内部置为图形色，把其布尔量的值为“假”的外部点置为底色即可。,边缘填充算法,求余运算：假定A为一个正整数，则M的余定义为 A M, 记为 。计算机中取A为n位能表示的最大整数。即，A=0xFFFFFFFF 由来：光栅图形中，如果某区域已着上值为M的颜色值做偶数次求余运算
12、，该区域颜色不变；而做奇数次求余运算，则该区域颜色变为值为 的颜色。这一规律应用于多边形扫描转换，就为边缘填充算法。 求余运算可用异或显示模式实现。算法基本思想：对于每条扫描线和每条多边形边的交点，将该扫描线上交点右方的所有象素取余。,算法1（以扫描线为中心的边缘填充算法）1、将当前扫描线上的所有象素着上 颜色； 2、求余：for(i = 0;i = m; i+)在当前扫描线上，从横坐标为Xi的交点向右求余；,算法2（以边为中心的边缘填充算法）1、将绘图窗口的背景色置为 ；2、对多边形的每一条非水平边做：从该边上的每个象素开始向右求余；,边缘填充算法,适合用于具有帧缓存的图形系统。处理后，按扫
13、描线顺序读出帧缓存的内容，送入显示设备。 优点：算法简单 缺点：对于复杂图形，每一象素可能被访问多次，输入/输出的量比扫描线算法大得多。,三、 种子填充 1、种子填充基本思路首先假设在多边形区域的内部，至少有一个像素点（称为种子）是已知的，然后算法开始搜索与种子点相邻且位于区域内的其它像素。如果相邻点不在区域内，那么到达区域的边界；如果相邻点位于区域内，那么这一点就成为新的种子点，然后继续递归地搜索下去。区域的连通情况可以分为四连通和八连通两种 四连通区域：各像素在水平和垂直四个方向上是连通的八连通区域：各像素在水平、垂直以及四个对角线方向上都是连通的。,在种子填充算法中，如果允许从四个方向搜
14、寻下一个像素点，则该算法称为四向算法；如果允许从八个方法搜寻下一个像素点，则该算法称为八向算法。一个八向算法可以用在四连通区域的填充上，也可用在八连通区域的填充上；而一个四向算法只能用于填充四连通区域。无论是四向算法还是八向算法，它们的填充算法基本思想是相同的。为简单起见，下面只讨论四向种子填充算法。,2简单种子填充算法 这是对内定义区域进行填充的算法，此算法所采用的基本方法是：将（x,y）点与边界值相比较，检测该点的像素是否处在区域之内；同时与新值相比，以确定该点是否已被访问过。这种测试的前提条件是：在初始状态下，区域内没有一个像素已被设置为新值；同时允许新值等于边界值。 如果用堆栈的方法来
15、实现简单种子填充算法，则算法的基本步骤如下： （1）种子像素压入堆栈。 （2）当堆栈非空时，重复执行以下操作。从堆栈中推出一个像素，并将该像素置成所要的值； 对于每个与当前像素邻接的四连通像素，进行上述两部份的测试；若所测试的像素在区域内且又未被填充过，则将该像素压入堆栈；,上述简单种子填充算法操作过程非常简单，却要进行深度的递归，这不仅要花费许多时间，降低了算法的效率，而且还要花费许多空间要构造堆栈结构。因此出现了改进的扫描线种子填充算法。,3扫描线种子填充算法 扫描线种子填充算法适用于边界定义的四连通区域。区域可凹可凸，还可以包括一个或多个孔。在边界定义区域外或与其邻接的区域中像素的值或颜
16、色不同于填充区域或多边形的值或颜色。 其基本思想是以种子所在扫描线进行从左到右填充直至边界为止,借助于堆栈，算法可分为以下五步实现： 初始化。将算法设置的堆栈置为空。将给定的种子（x,y）压入堆栈。 出栈。如果堆栈为空，算法结束。否则从包含种子像素的堆栈中取出栈顶元素（x,y）作为种子像素。区间填充。沿当前扫描线对种子像素的左右像素进行填充（像素值为new_color），直至遇到边界像素为止，从而填满包含种子像素的区间。 (4) 定范围。以xl和xR分别表示步骤（）区间内最左和最右的两个像素。 （5） 进栈。在xRxxL中，检查与当前扫描线相邻的上下两条扫描线是否全为边界像素(boundary_color)或者前面已经填充过的像素（new_color），是则转到步骤(2),否则在xRxxl中把每一个区间的最右像素作为种子像素压入堆栈，再转到步骤（2）继续执行。,
