射线法检验交点数 P n A E P B B 左闭右开 D 交点数=偶数(包括0)交点数=奇数 点在多边形之外 点在多边形之内
射线法检验交点数 A B C D E P A B C D E P 交点数=偶数（包括0） 点在多边形之外 交点数=奇数 点在多边形之内 z x 左闭右开
逐点测试效率低不实用怎么办? 包围盒法 凸多边形 凹多边形
包围盒法 凸多边形 凹多边形 逐点测试效率低不实用怎么办？
实区域填充算法分类 扫描线填充算法 扫描线顺序 种子填充算法 a内部一个点出发
实区域填充算法分类 扫描线填充算法 ◼ 扫描线顺序 种子填充算法 ◼ 内部一个点出发
扫描线填充算法 利用图形的空间连贯性 和扫描线的连贯性 扫描线5 扫描线2 Pl 求交:14,l3,2 012345678910x 排序:1,12,13,4 ·交点配对:(1,12),(3,14) ·区间填色
扫描线填充算法 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 y x 8 8 9 10 扫描线5 P4 P1 P2 P3 P5 扫描线2 I1 I2 I3 I4 求交：I4 , I3 , I2 , I1 排序：I1 , I2 , I3 , I4 交点配对：(I1 , I2 ), (I3 , I4 ) 区间填色 利用图形的空间连贯性 和扫描线的连贯性
填充扩大化间题 y765432 y765 解决方法: 1234567x 1234567X 取中心扫描线y+0.5 检查交点右方像素的中心是否落在区间内 ≤x+0.5≤x 76543210 543 2 12345167 0112345167x
填充扩大化问题 解决方法： ◼ 取中心扫描线y+0.5 ◼ 检查交点右方像素的中心是否落在区间内 xl≤x+0.5≤xr 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 y 0 1 2 3 4 5 6 7 x 1 2 3 4 5 6 7 y x P1 P2 P4 P3 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 y 0 1 2 3 4 5 6 7 x 1 2 3 4 5 6 7 y x P1 P2 P4 P3