CG03区域填充

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,区域填充的算法,1,多边形填充,2,实面积图形,填充后的多边形称为实面积图形，实面积图形在其封闭的轮廓内具有相同的颜色，这意味着要填充光栅显示器上封闭图形内的每一个像素点。实面积图形既能描述物体的几何轮廓，又能表现物体的表面颜色，与人们观察物体表面的习惯相一致，同时，实面积图形也是描述三维物体、绘制三维真实感图形的基础。,3,多边形的定义,4,1.凸多边形,多边形上任意两顶点间的连线都在多边形之内，凸点对应的内角小于180度，只具有凸点的多边形称为凸多边形。,5,2.凹多边形,多边形上任意两顶点间的连线有不在多边形内部的部分，凹点对应的内角大于180度，有凹点的多边形称为凹多边形。,6,环,多边形内包含有另外的多边形。如果规定每条有向边的左侧为期内部面积区域，则当观察者沿着边界行走时，内部区域总在其左侧，也就是说多边形外轮廓线的环行方向为逆时针，内轮廓线的环行方向为顺时针。这种定义了环行方向的多边形称为环。,7,多边形的表示,8,顶点表示法,多边形的顶点表示法是用多边形的顶点序列来描述。特点是直观、占内存少，易于进行几何变换，但由于没有明确指出哪些像素在多边形内，所以不能直接进行填充，需要对多边形进行扫描转换。,9,点阵表示法,多边形的点阵表示法就是用多边形覆盖的像素点集来描述。特点是便于直接确定实面积图形覆盖的像素点，是多边形填充所需要的表示形式，但是缺少了多边形顶点的几何信息。,10,多边形的扫描转换,将多边形的描述从顶点表示法变换到点阵表示法的过程，称为多边形的扫描转换。即从多边形的顶点信息出发，求出多边形内部的各个像素点信息。,11,多边形的填充,多边形的填充是指从多边形的顶点信息出发，求出其覆盖的每个像素点，置为填充色，而将多边形外部的像素点保留为背景色。多边形填充的主要工作是确定穿越多边形内部的扫描线的覆盖区间。,首先确定多边形覆盖的扫描线条数，对每一条扫描线，计算机扫描线与多边形边界交点区间。然后再将该区间内的像素赋予指定的颜色。,12,区域填充,区域是指一组相邻而又具有相同忏悔的像素，可以理解为多边形的内部。区域的边界色和填充色不一致，填充算法只对区域内部进行填充。种子填充算法是从给定的种子位置开始，按填充颜色点亮种子的相邻像素考虑到颜色不同的边界像素为止。种子填充算法主要有4邻接点简洁和8邻接点算法。,13,区域填充算法,区域填充可以分两步进行，第一步先确定需要填充哪些象素。第二步确定用什么颜色值来填充。,14,1 扫描线多边形域的填充,基本原理：按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。区间的端点可以通过计算扫描线与多边形的界线的交点获得。,15,一个多边形与若干扫描线,y,0,P,4,(11,8),P,6,(2,7),P5(5,5),P,1,(2,2),P,3,(11,3),P,2,(5,1),1,5,10,5,A,B,C,D,G,E,F,基本步骤：,如图所示，扫描线6与多边形的边界线交于四点A、B、C、D。这四点反扫描线分为五个区间0,2,2,3.5,3.5,7,7,11,11,12。其中，2,3.5,7,11两个区间落在多边形内，该区间内的象素应取多边形色。其它区间背景色。,这里的四个交点在计算时未必是按从左到右顺序获得。因此交点序列必需经过排序，才能得到从左到右，按x递增增顺序排列的交点x坐标序列。,（1）,求交：计算扫描线与多边形各边的交点；,（2）,排序：把所有交点按递增顺序进行排序；,（3）,交点配对：第一个与第二个，第三个与第四个等等。每对交点就代表扫描线多边形的一个相交区间；,区间填色：把这些相交的区间内的象素置成多边形颜色，把相交区间外的象素置成背景色。,16,当扫描线与多边形顶点相交时，会出现异常情况。扫描线2与P,1,相交。按前术方法求得交点（x坐标）序列2，2，8。这将导致2，8区间内的象素取背景色，而这个区间的象素正是属于多边形内部，需要填充的。所以，我们所考虑当扫描线与多边形的顶点相交时，相同的交点只取一个。这样，扫描线路与多边形边的交点序列就成为2，8。但是，扫描线7与多边形边的交点序列为2，9，11。这将导致错把2，9区间作为多边形内部来填充。我们发现当两条边在扫描线的两侧时，交点只取一个。当两条边在扫描线同侧的时侯交点算为0个或2个。,一个多边形与若干扫描线,0,P,4,(11,8),P,6,(2,7),P5(5,5),P,1,(2,2),P,3,(11,3),P,2,(5,1),1,5,10,A,B,C,D,G,E,F,7,8,11,17,2.,边界上象素的取舍,对左下角为（1，1），在上角为（3，3）的正方形填充时，若对边界上所有象素均进行填充，就得到图2-8的的结果。被填充的象素复盖的面积为3X3个单位，而方形的实际面积只有2X2个单位。为了克服这个问题，我们,规定落在右/上边界的象素不予填充，而落在左/下边界的象素予以填充。,对区域边界上象素全部填充的结果,x,3,2,1,3,0,1,2,18,有效边和有效边表,有效边：多边形内与当前扫描线相交的边称为有效边。在处理一条扫描线时仅对有效边进行求交运算，可以避免与多边形的所有边求交，提高了算法效率。,有效边表：把有效边按照与扫描线交点x坐标递增的顺序存放在一个链表中，称为有效边表(cactive edge table,AET),x,ymax,1/k,next,19,桶表和边表,边表：从有效边表的建立过程可以看出，有效边表缎带出了扫描线和有效边交点坐标的计算机方法，但是没有给出新边出现的位置坐标。为了确定在哪条扫描线上手稿了新边，就需要构造一个边表(edge table,ET)，用以存放扫描线上多边形各条边出现的信息。,20,桶表和边表的表示法,首先构造一个纵向扫描线链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点称为桶，对应多边覆盖的每一条扫描线。,将每条边的信息链入与该最小,y,坐标,(,y,min,),相对应的桶处。,对于每一条扫描线，如果新增多条边，则按,x|ymin,坐标递增的顺序存放在一个链表中，若,x|ymin,相等，则按照,1/k,由小到大排序，这样就形成了边表。,21,边填充算法,22,基本原理：对于每一条扫描线和每条多边形边的交点（x,1,y,1,）,将该扫描线上交点右方的所有象素取补。如图。,边填充算法示意图,23,使用栅栏,为了减少边填充算法访问象素的次数，可引入栅栏。栅栏指的是一条与扫描线垂直的直线，栅栏位置通常取过多边形顶点、且把多边形分为左右两半。,栅栏填充算法的基本思想是：对于每个扫描线与多边形边的交点，就将交点与栅栏之间的象素取补。若交点位于栅栏左边，则将交点置右，栅栏之左的所有象素取补；若交点位于栅栏的右边，则将交点置左，交点之左的象素取补。栅栏填充算法只是减速少了被重复访问的角素的数目，但仍有一些象素会被重复访问。,24,边标志算法,边标志算法（轮廓填充算法）可使每个象素访问一次。首先对多边形的每条边进行直线扫描转换，即对多边形边界所经过的像素打上标志；然后对每条与多边形相交的扫描线依次从左到右顺序，逐个访问该扫描线像素，使用一个布尔量inside来指示当前点的状态，inside的初始值为False。每当当前的访问像素为打上边标志的点，就将inside取反，对未打标志的像素，inside不变；对inside作必要操作后，若inside为真，是把该像素量按多边形填充。,25,区域填充算法,用点阵方法表示的多边形区域，如果其内部像素具有同一种颜色，而边界像素具有另一种颜色，可以使用种子算法进行填充。,26,四邻接点和八邻接点,四邻接点：对于多边形区域内部任意一个种子像素，其左、上、右、下这4个像素称为四邻接点。,八邻接点：对于多边形区域内部任意一个种子像素，其左、右、上、下以及左上、右上、右下、左下这8个像素称为八邻接点。,27,四连通域和八连通域,种子填充算法要求多边形区域内部必须是连通的，才能将种子像素的颜色扩散到多边形区域内部的所有像素点，一般将多边形区域划分为四连通域和八连通域,可以以,4,邻接点形式遍历区域内的所有像素点的称,4,连通域。,可以以,8,邻接点形式遍历区域内的所有像素点的称,8,连通域。,28,邻接点填充算法,栈顶像素出栈,按填充色绘制出栈像素。,左开始沿顺时针方向，若该像素的颜色不是边界色并且未围成填充色，则把该像素入栈；否则丢充该像素,29,扫描线种子填充算法,栈顶像素出栈,沿扫描线对出栈像素的左右像素进行填充，直到遇到边界像素为止。同时记录填充该区间，其最左端像记为,x,l,，最右端像素记为,x,r,。,30,