第五章基本图形生成算法 5.4区域填充 5.4.1多边形填充 根据如下分析,得到如下步骤: 对每条扫描线分为4步(以扫描线6为例) (1)求交点,即计算该扫描线与多边形各边的交点 (2)排序,由于交点不一定由左到右求出,因此 将求出的交点按x坐标值排序 (3)交点配对,1与2,3与4,……,每对表示一个区 间 (4)区间填充
11 第五章 基本图形生成算法 5.4 区域填充 5.4.1 多边形填充 根据如下分析，得到如下步骤： 对每条扫描线分为4步 (以扫描线6为例) (1) 求交点，即计算该扫描线与多边形各边的交点 (2) 排序，由于交点不一定由左到右求出，因此 将求出的交点按x 坐标值排序 (3) 交点配对，1与2，3与4，… …，每对表示一个区 间 (4) 区间填充
第五章基本图形生成算法 5.4区域填充 5.4.1多边形填充 例:对下图的多边形进行填充 (8)数据结构 0次 0次 ①“新边表”(有序边表) 结点结构 △xY LINK+ 8765432 当前扫描线扫描线「最高扫 与边的交点间x增量描线号 0 01/234567891011 1次 2次
12 第五章 基本图形生成算法 5.4 区域填充 5.4.1 多边形填充 （8）数据结构 ① “新边表”(有序边表) 9 0 1 2 3 4 5 6 7 8 9 10 0 1 8 7 6 4 5 3 2 11 0次 0次 1次 2次 1 2 3 4 例：对下图的多边形进行填充
第五章基本图形生成算法 5.4区域填充 13 5.4.1多边形填充 新边表如下: 8765432 528 5-1.57 扫描 1108 线号 207 5321 533|∧ 0
13 第五章 基本图形生成算法 5.4 区域填充 5.4.1 多边形填充 扫描 线号 8 ^ 7 ^ 6 5 ^ 4 ^ 3 2 1 0 ^ 5 2 8 11 0 8 ^ 2 0 7 ^ 5 -3 2 5 3 3 ^ 5 -1.5 7 ^ 新边表如下：
第五章基本图形生成算法 5.4区域填充 5.4.1多边形填充 (2)排序,并更新活化边表 (2,3.5,7,11) 207 3.5-1.57 728 11 5|-1.57 1108 074-1108(21) 1) 1108 (2,11) 0714-833(2,8) 5-3 5|33
14 第五章 基本图形生成算法 5.4 区域填充 5.4.1 多边形填充
第五章基本图形生成算法 5.4区域填充 15 5.4.1多边形填充 算法步骤: (1)初始化:构造边表ET,将AET表置空; (2)将第一个不空的ET表中的边与AET表合并; (3)由AET表中取出交点对进行填充。填充之后删除 y=ym的边; (4)y1+1=y;+1根据x+=x1+1/m计算并修改AET表,同时 合并ET表中y=y+桶中的边,按次序插入到AET表中 ,形成新的AET表; (5)AET表不为空则转(3),否则结束。 注:算法见P182
15 第五章 基本图形生成算法 5.4 区域填充 5.4.1 多边形填充 算法步骤： (1)初始化：构造边表ET，将AET表置空； (2)将第一个不空的ET表中的边与AET表合并； (3)由AET表中取出交点对进行填充。填充之后删除 y=ymax的边； (4)yi+1 =yi +1,根据xi+1 =xi +1/m计算并修改AET表，同时 合并ET表中y=yi+1桶中的边，按次序插入到AET表中 ，形成新的AET表； (5)AET表不为空则转(3)，否则结束。 注：算法见P182