射线法检验交点数 X P n A E B B 左闭右开 D D 交点数=偶数(包括0)交点数=奇数 点在多边形之外 点在多边形之内
射线法检验交点数 A B C D E P A B C D E P 交点数=偶数（包括0） 点在多边形之外 交点数=奇数 点在多边形之内 z x 左闭右开
逐点测试效率低不实用怎么办? 包围盒法 凸多边形 凹多边形
包围盒法 凸多边形 凹多边形 逐点测试效率低不实用怎么办？
实区域填充算法分类 ·扫描线填充算法 扫描线顺序 ·种子填充算法 内部一个点出发
实区域填充算法分类 扫描线填充算法 ◼ 扫描线顺序 种子填充算法 ◼ 内部一个点出发
扫描线填充算法 利用图形的空间连贯性 和扫描线的连贯性 扫描线 P4 扫描线2 P2 求交:4,2 012345678910 3,12: 排序:1,2,12 交点配对:(1,12),(3 区间填色
扫描线填充算法 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 ) 区间填色 利用图形的空间连贯性 和扫描线的连贯性
填充扩大化间题 765432 步步步 解决方法 1234567X a取中心扫描线y+0.5 检查交点右方像素的中心是否落在区间内 X下X+0.5≤X 1234 0112345167
填充扩大化问题 解决方法： ◼ 取中心扫描线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