第四章 区域填充_应用.ppt

所有的边和扫描线求交，效率很低。因为一条扫描线往往只和少数几条边相交。 如何判断多边形的一条边与扫描线是否相交？ 与当前扫描线相交的边称为活性边（active edge)，把它们按与扫描线交点x坐标递增的顺序存入一个链表中，边的活化链表 （ AEL, Active edge table)。它记录了多边形边沿扫描线的交点序列。 只需对当前扫描线的活动边表作更新，即可得到下一条扫描线的活动边表。 4.2.5数据结构与实现步骤 如何计算下一条扫描线与边的交点。 直线方程：ax+by+c = 0 当前交点坐标：(xi, yi) 下一交点坐标：(xi+1,yi+1) xi+1= ((-byi+1)-c)/a = ((-byi+1)-c)/a =xi-b/a 活动边表中需要存放的信息： x：当前扫描线与边的交点 dx＝-b/a：从当前扫描线到下一条扫描线之间的x增量 ymax：边所交的最高扫描线 4.2.5数据结构与实现步骤 增加哪一条边呢？ 为了方便边的活化链表的更新，建立另一个表-边表，存放在该扫描线第一次出现的边。 存放的信息： x：扫描线与该边的初始交点 dx：x的增量 ymax：该边的最大y值 4.2.5数据结构与实现步骤 即算法中采用较灵活的数据结构。它由边的分类表ET（Edge Table）和边的活化链表AEL（Active Edge List）两部分组成。 表结构ET和AEL中的基本元素为多边形的边。边的结构由以下四个域组成： ymax 边的上端点的y坐标； x 在ET中表示边的下端点的x坐标，在AEL中则表示边与扫描线的交点的坐标； Δx 边的斜率的倒数； next 指向下一条边的指针。 4.2.5数据结构与实现步骤 边的分类表ET是按边的下端点的y坐标对非水平边进行分类的指针数组。下端点的y坐标的值等于i的边归入第i类。有多少条扫描线，就设多少类。同一类中，各边按x值（x值相等时，按Δx的值）递增的顺序排列成行。 图4-2-16 4.2.5数据结构与实现步骤 举例 已知多边形P=(P0P1P2P3P4P5P6P0)；其各边坐标分别为 [（2，5）（2，10）（9，6）（16，11）（16，4）（12，2）（6，2）] 建立其边表和边的活化链表 图4-2-17 4.2.5数据结构与实现步骤 边表 图4-2-18 4.2.5数据结构与实现步骤 y=3 Y=8 活动边表 图4-2-19 4.2.5数据结构与实现步骤 这样，当建立了边的分类表ET后，扫描线算法可按下列步骤进行： （1）取扫描线纵坐标y的初始值为ET中非空元素的最小序号。 （2）将边的活化链表AEL设置为空。 （3）按从下到上的顺序对纵坐标值为y的扫描线（当前扫描线） 执行下列步骤，直到边的分类表ET和边的活化链表都变成空为止。 算法实现步骤 4.2.5数据结构与实现步骤 1）如边分类表ET中的第y类元素非空，则将属于该类的所有边从ET中取出并插入边的活化链表中，AEL中的各边按照x值（当x值相等时，按Δx值）递增方向排序。 2）若相对于当前扫描线，边的活化链表AEL非空，则将AEL中的边两两依次配对，即1，2边为一对，3，4边为一对，依次类推。每一对边与当前扫描线的交点所构成的区段位于多边形内，依次对这些区段上的点（象素）按多边形属性着色。 3）将边的活化链表AEL中满足y=ymax的边删去。 4）将边的活化链表AEL剩下的每一条边的x域累加Δx，即x:=x+Δx。 5）将当前的扫描线的纵坐标值y累加1，即y:=y+1。 4.2.5数据结构与实现步骤 扫描线算法： 特点：算法效率比逐点填充法高很多。 缺点：对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现。 问题： 如何处理多边形的水平边？ 如何修改扫描线算法，使它能处理边自交的多边形？ 扫描线算法总结 4.2.6边缘填充算法 ▼求余运算：假定A为一个正整数，则M的余定义为A – M, 记为 。计算机中取A为n位能表示的最大整数。即，A=0xFFFFFFFF ▼由来：光栅图形中，如果某区域已着上值为M的颜色值做偶数次求余运算，该区域颜色不变；而做奇数次求余运算，则该区域颜色变为值为 的颜色。这一规律应用于多边形扫描转换，就为边缘填充算法。 ▼算法基本思想：对于每条扫描线和每条多边形边的交点，将该扫描线上交点右方的所有象素取余。 1、将当前扫描线上的 所有象素着上 颜色； 2、求余： for(i =