5.4 多边形的扫描转换与区域填充5.4.1 5.4.1 多边形的扫描转换多边形的扫描转换5.4.2 5.4.2 边缘填充算法边缘填充算法5.4.3 5.4.3 区域填充区域填充5.4.4 5.4.4 其他相关概念其他相关概念YTUYTU5.4.1 多边形的扫描转换多边形的表示方法多边形的表示方法 flash flash 演示演示多边形顶点表示多边形顶点表示多边形点阵表示多边形点阵表示YTUYTU多边形的扫描转换1.1.像素逐点判断法像素逐点判断法2.2.x-x-扫描线算法扫描线算法3.3.改进的有效边表算法改进的有效边表算法4.4.边缘填充算法边缘填充算法5.5.栅栏填充算法栅栏填充算法6.6.边界标志算法边界标志算法扫扫描描线线YTUYTU1. 像素逐点判断法v检查光栅的每一像素是否位于多边形内检查光栅的每一像素是否位于多边形内YTUYTU改进: 包围盒技术v包围盒包围盒: : 包含该多边形的最小矩形包含该多边形的最小矩形 v只有包围盒内的那些点需要检查只有包围盒内的那些点需要检查YTUYTU多边形的空间连贯性扫描线上的相邻像素几乎都有相同的特性扫描线上的相邻像素几乎都有相同的特性 YTUYTU2. x-扫描线算法图5-23 x-扫描线算法填充多边形xy213 4 5 6 7 8 9111234567891011121012ymax=12ymin=1算法步骤：算法步骤：1.ymin和和ymax2.填充每条扫描线填充每条扫描线a.求交求交 (all)b.排序排序c.交点配对交点配对d.填色填色YTUYTUvX-X-扫描线算法可填充凸的、凹的和带孔的扫描线算法可填充凸的、凹的和带孔的多边形区域多边形区域YTUYTU存在问题：交点的取舍xy213 4 5 6 7 8 9111234567891011121012图图5-24 5-24 与多边形顶点相交的交点的处理与多边形顶点相交的交点的处理p5p0p1p2p3p4p6*奇点：奇点： 当扫描线与多边当扫描线与多边形形P的边界的交的边界的交点是点是P的顶点时，的顶点时，则称该交点为奇则称该交点为奇点点 YTUYTU图5-25 与扫描线相交的多边形顶点的交点数0111102220极极值值点点偶偶数数化化处处理理下下闭闭上上开开的的原原则则1Flash演示演示x-扫描线算法扫描线算法YTUYTUX扫描线算法的缺点算法步骤：算法步骤：1.ymin和和ymax2.填充每条扫描线填充每条扫描线a.求交求交 (all) 每条扫描线需要和多边形每条扫描线需要和多边形 的的所有边所有边所有边所有边 求交求交a.排序排序b.交点配对交点配对c.填色填色 图5-23 x-扫描线算法填充多边形xy213 4 5 6 7 8 9111234567891011121012YTUYTU3.改进的有效边表算法(Y连贯性算法)xy213 4 5 6 7 8 9111234567891011121012填充每条扫描线填充每条扫描线求交求交排序排序交点配对交点配对填色填色YTUYTU多边形边的连贯性、扫描线的连贯性p5xy213 4 5 6 7 8 9111234567891011121012p0p1p2p3p4p6xi+1 = xi+1/kyi+1 = yi+11 11/k1/k(xi,yi)(xi+1,yi+1)p4p534YTUYTUxy213 4 5 6 7 8 9111234567891011121012改进的有效边表算法 改进原理: 求交v利用扫描线的连贯性利用扫描线的连贯性 和多边形边的连贯性和多边形边的连贯性 获得交点坐标获得交点坐标, ,每条条扫描线仅对有效边每条条扫描线仅对有效边 求交求交v有效边有效边活性边活性边Active EdgeActive Edge与当前扫描线相交的边与当前扫描线相交的边YTUYTU数据结构v有效边有效边 (Active Edge)(Active Edge)v有效边表有效边表 (Active Edge Table)(Active Edge Table)v边表边表 (Edge Table)(Edge Table)YTUYTUxymax1/knext当前扫描线当前扫描线与边的交点与边的交点边的最大扫边的最大扫描线值描线值斜斜率率链表指针链表指针y32.471/34.553/47.051/29.091/2xy213 4 5 6 7 8 9111234567891011121012e1e2e3e4e1e2e3e4递递增增有效边表改进的有效边表算法填充每条扫描线填充每条扫描线1.1.求交求交 构造有效边表构造有效边表 AETAET2.2.排序排序3.3.交点配对交点配对4.4.填色填色xy213 4 5 6 7 8 91112345678910111210 12YTUYTU有效边表中包含了扫描线与边的交点信息xy213456789111234567891011121012e1e2e3e4e5e6e7y=61.47 -1/310.512 1/2e3e6x xy ymaxmax1/k1/k nextnext当前扫描线当前扫描线与边的交点与边的交点y=6y=6时的时的 有效边表有效边表YTUYTU如何构造每条扫描线的AET?x xy ymaxmax1/k1/knextnextp5xy213 4 5 6 7 8 9111234567891011121012p0p1p2p3p4p6YTUYTUflash X扫描线算法与AETx213 4 5 6 7 8 9111012y123456789101112e1e2e3e4e5e6e7YTUYTU边表 (Edge Table)最大扫描线数最大扫描线数: 12xy213 4 5 6 7 8 9111234567891011121012e1e2e3e4e5e6e7123456789101112e1e7e2e3e4e5e6水平边除外水平边除外桶桶纵向链表纵向链表YTUYTU1e3e4e5e612 2/5712-1x|yx|yminminy ymaxmax1/k1/knextnext795e2123456789101112e1e7边表边表节点节点xy213 4 5 6 7 8 9111234567891011121012e1e2e3e4e5e6e7YTUYTUx|yx|yminminy ymaxmax1/k1/knextnext边低端点低端点处的的x x值边表边表节点节点x xy ymaxmax1/k1/knextnext当当前前扫描描线与与边的交点的交点有效有效边表边表节点节点YTUYTU边表中不包含水平边2YTUYTU边表中不包含水平边YTUYTU当扫描线与多当扫描线与多边形的顶点相边形的顶点相交时交时, 交点计交点计为为1 时的问题时的问题xy213456789111234567891011121012e1e2e3e4e5e6e7y=717 -1/31 12 2/511 9 1/2e3e2e6y=7y=7时的有效的有效边表表解决顶点交点计为1时的情形图图5-28 5-28 将多边形的某些边将多边形的某些边缩短缩短以以分离分离那些应计为那些应计为1 1个交点个交点的顶点的顶点（a)原图（b)缩短ymax的边（c)缩短ymin的边扫描线y扫描线y+1扫描线y-1YTUYTUxy213456789111234567891011121012e1e2e3e4e5e6e7分离分离顶点顶点y=71 12 2/511 9 1/2e2e6y=7y=7时的有的有效效边表表图5.27 (c) 边表 P126分离分离计为1 1个个交点交点的的顶点点x|yx|yminminy ymaxmax1/k1/k nextnextYTUYTU例: 改进的AET算法xy213 4 5 6 7 8 9111234567891011121012P4P1P0P2P3P5P6FlashFlash演示演示YTUYTUxy213 4 5 6 7 8 9111234567891011121012P1P0P2P3P4P5P6YTUYTUy=5 1.7 6 -1/3653/410 91/265 -1/2y=136 -1/3353/4891/285 -1/2y=2 2.7 6 -1/33.8 53/48.5 91/27.5 5 -1/2y=3 2.3 6 -1/34.5 53/4991/275 -1/2y=426 -1/35.3 53/49.5 91/26.5 5 -1/2y=6 1.3 6 -1/310.591/2y=71 12 2/51191/2y=8 1.4 12 2/57 12-111.591/2795y=9 1.8 12 2/56 12-11291/212 95y=10 2.2 12 2/55 12-1改进的有效边表算法详细步骤1.1.初始化初始化: : 构造边表构造边表ETET, ,AETAET表置空；表置空；2.2.获得初始有效边表获得初始有效边表 将第一个不空的将第一个不空的ETET表中的边与表中的边与AETAET表合并表合并 xy213 4 5 6 7 8 9111234567891011121012e1e2e3e4e5e6e7YTUYTUe3e4e5e6x|yminymax1/knext1234536-1/3353/485-1/2891/2xy213 4 5 6 7 8 9111234567891011121012e1e2e3e4e5e6e736-1/3353/485-1/2891/2y=1AETxymax1/knextETa)a)由由AETAET表中取出交表中取出交点对进行填充点对进行填充b)填充之后将填充之后将y=ymax的边删除的边删除c)c)b)b)形成下一条扫描形成下一条扫描线的线的AETAET表表3.按按从下到上从下到上的顺序对纵坐标值为的顺序对纵坐标值为y的的扫描线扫描线执执行下列步骤行下列步骤 a) ,b) ，直到边表直到边表ET和有效边表和有效边表AET都变成空为止都变成空为止xy213 4 5 6 7 8 9111234567891011121012e1e2e3e4e5e6e71 11/k1/k(xi,yi)(xi+1,yi+1)p4p534计算并修改计算并修改AETAET表表 yi+1=yi+1=yi+1yi+1, xi+1=xi+1/, xi+1=xi+1/k k 同时合并同时合并ETET表中表中y=yi+1 y=yi+1 桶中的边，按次序桶中的边，按次序(x(x值从大到小值从大到小) ) 插入到插入到AETAET表中表中b) 形成下一条扫描形成下一条扫描线的线的AET表；表；注意v请按照题目中关于顶点的分离要求构造边请按照题目中关于顶点的分离要求构造边表表! !v默认默认: : 不分离不分离YTUYTU作业与练习v课堂练习课堂练习1: P149 5.101: P149 5.10v课堂练习课堂练习2: AET 2: AET v作业作业 5.11 p1495.11 p149YTUYTU