第五章基本图形生成算法 5.4区域填充 54.1多边形填充 (3)内外点判定—奇偶性原理 从无穷远处向该点引一条射线,如果这条射线与多边形的交点 为奇数时,此点为内点,否则为外点 推导:当射线与多边形相交奇数次后,线上点都是内点,偶数 次相交后线上点都是外点。 特例:顶点是交点。 若射线与多边形顶点相交 a)共享顶点的两条边分别位于扫描线的两边,交点算一个 b)共享顶点的两条边都位于扫描线的下边,交点算零个。 c)共享顶点的两条边都位于扫描线的上边,交点算二个
6 第五章 基本图形生成算法 5.4 区域填充 5.4.1 多边形填充 （3）内外点判定——奇偶性原理 从无穷远处向该点引一条射线，如果这条射线与多边形的交点 为奇数时，此点为内点，否则为外点。 推导：当射线与多边形相交奇数次后，线上点都是内点，偶数 次相交后线上点都是外点。 特例：顶点是交点。 若射线与多边形顶点相交 a）共享顶点的两条边分别位于扫描线的两边，交点算一个。 b）共享顶点的两条边都位于扫描线的下边，交点算零个。 c）共享顶点的两条边都位于扫描线的上边，交点算二个
第五章基本图形生成算法 5.4区域填充 54.1多边形填充 y 请分别回答A~H点中哪 12 些点需要填充?为什 么? 987654321 G 123456789101112g 图5-23x-扫描线算法填充多边形
7 第五章 基本图形生成算法 5.4 区域填充 5.4.1 多边形填充 请分别回答A～H点中哪 些点需要填充？为什 么？
第五章基本图形生成算法 5.4区域填充 5.4.1多边形填充 (4)边界处理 边界上象素的取舍原则: 432 左闭右开 下上开一 012345 屏幕坐标顶点在 (0,0),(40)(4,3),(0,3)的矩 型 01234
8 第五章 基本图形生成算法 5.4 区域填充 5.4.1 多边形填充 （4）边界处理 屏幕坐标顶点在 (0,0),(4,0),(4,3),(0,3)的矩 型 0 1 2 3 4 1 2 3 0 1 2 3 4 5 1 2 3 4 边界上象素的取舍原则： 左闭右开 下闭上开
第五章基本图形生成算法 5.4区域填充 5.4.1多边形填充 (5)确定扫描线y=scan 12 inax ymin≤scan≤ymax 10 98z 原因:所有的边和扫描线求交, 效率很低。因为一条扫描 线往往只和少数几条边相 654321 交 y-Jnin 456789101122 如何判断多边形的一条边与扫 图5-23x-扫描线算法填充多边形 描线是否相交? (ymin, ymax)
9 第五章 基本图形生成算法 5.4 区域填充 5.4.1 多边形填充 （5）确定扫描线y=scan ymin ≤ scan ≤ ymax 原因：所有的边和扫描线求交， 效率很低。因为一条扫描 线往往只和少数几条边相 交。 如何判断多边形的一条边与扫 描线是否相交？ (ymin,ymax)
第五章基本图形生成算法 5.4区域填充 10 5.4.1多边形填充 (6)扫描线的连贯性 当前扫描线与各边的交点顺序,与下一条扫描线与各边 的交点顺序很可能相同或类似。 只需对当前扫描线的活动边表作更新,即可得到下一条 扫描线的活动边表。 (7)边的连贯性 当某条边与当前扫描线相交时,它很可能也与下一条扫 描线相交。 与当前扫描线相交的边称为活动边( active edge),把它 们按与扫描线交点x坐标递增的顺序存入一个链表中,称为 活动边表(AET, Active edge table)
10 第五章 基本图形生成算法 5.4 区域填充 5.4.1 多边形填充 （6）扫描线的连贯性 当前扫描线与各边的交点顺序，与下一条扫描线与各边 的交点顺序很可能相同或类似。 只需对当前扫描线的活动边表作更新，即可得到下一条 扫描线的活动边表。 （7）边的连贯性 当某条边与当前扫描线相交时，它很可能也与下一条扫 描线相交。 与当前扫描线相交的边称为活动边（active edge)，把它 们按与扫描线交点x坐标递增的顺序存入一个链表中，称为 活动边表（AET, Active edge table)