填充算法学习.pptxVIP

5.4 多边形的扫描转换与区域填充 一个有界区域内填充指定的颜色的填充方法有： （1）x扫描线填充算法 （3）种子填充算法 (3) 扫描线种子填充算法 （4）边缘填充算法 各算法的前提条件不同 ;5.4.1 多边形的扫描转换;多边形的扫描转换： 把多边形的顶点表示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并赋予特定的灰度和颜色，通常称这种转换为多边形的扫描转换。 常用算法：x-扫描线算法;x-扫描线算法 思想：按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间像素。 目标：利用相邻像素之间 的的连贯性，提高算法效率。 条件：需提供多边形各 顶点的坐标及填充色;算法步骤： (1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。 (2)从y=ymin到y=ymax，每次用一条扫描线进行填充。 (3)对一条扫描线填充的过程可分为四个步骤： a.求交点 b.排序 c.交点配对 d.区间填色;(1) 边的相关性及边记录 算法首先要求出扫描线与边界的交点 已知扫描线yi与AB边的交点是（xi,yi）则： yi+1=yi+1, xi+1=xi+1/k (1) m是这条边的斜率 ; 因此，利用这种边的相关性，我们不需算出边线与各扫描线的全部交点，只需以边为单位，对每条边建立一个边记录即可： 边记录 x|ymin ymax 1/k next;边表(ET表);有效边表AET(Active Edge)： 是一个只与当前扫描线相交的边记录链表。 用式(1)可算法AET表中x域的新值xi。 AET表中的记录顺序仍是按x增大排序的。 ;;（3）多边形扫描线算法过程 1）??? 由顶点坐标数据建立ET表 2）??? 定义AET指针，使之为空 3）??? 使yi=Ymin 4）??? 反复做下述各步，直到ET与AET为空 a.?????? 将 ET表加入到AET表中 b.?????? 对扫描线yi依次成对取出AET中的xi值，并对 xi之间填上所要求的颜色或图案 c.?????? 从AET表中删去yi=Ymaxr的记录 d.??? ? 对保留下来的AET中的每个记录用xi+1/k代替 xi, 重新按x递增排序 e. 使yi+1, 进入下一轮循环 ; 扫描线与多边形顶点相交问题: 当扫描线与多边形顶点相交时，若不加以特殊处理，交点配对时会发生错误。 解决的方法是：当扫描线与多边形的顶点相交进，若共享顶点的两条边分别落在扫描线的两侧，交点只算一个,否则交点算零个或两个。 ;第13页/共26页;解决顶点交点计为1时的情形：; 算法特点: ?优点：算法效率高。 ?缺点：对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现。 ;5.4.2 边缘填充算法 思想：按任意顺序处理多边形的每条边：先求该边与扫描线的交点，然后将每一条扫描线上交点右方的所有像素取补。 多边形的所有边处理完毕后，填充可完成 ;算法特点： 优点：简单，适合于硬件实现 缺点：对复杂图形，每一像素可能被访问多次，输入输出量大。 ? 改进算法： 栅栏填充算法 ;5.4.3 区域填充(种子填充算法);区域连通方式对填充结果的影响;3 种子填充算法 思想：从区域内的一个点（种子）开始，由内向外将填充色扩展到整个区域内的过程。 条件： 要求给出边界颜色特征及区域内的一个点 基本思想：从多边形内部任一点（像素）出发，按照“右上左下”的顺序判断相邻像素，若不是边界像素且没被填充过，则对其填充，并重复上述过程，直至所有像素填充完毕。 ?;;;对边界和内点表示的八连通区域的填充，只要将上述算法的对四个像素点填充改为八个像素点即可。 四连通区域种子填充算法的缺点是有时不能通过狭窄区域区域，因而不能填满多边形。八连通算法的缺点是有时会填出多边形的边界。由于填不满比涂出更容易补救，因此四连通算法比八连通算法用得更多。;小结: 本课学习区域填充的常规方法，包括种子填充算法、多边形扫描线算法、边缘填充算法。重点掌握区域连通方式对填充结果的影响多边形扫描线算法中边表ET与活动边表AET的使用。;作业：;谢谢您的观看！