Ch543多边形区域填充.ppt

5.4.3 区域填充 v区域 点阵形式的填充图形,是像素的集合 v区域的表示 边界表示法 内点表示 v区域填充算法 边界填充算法 泛填充算法 区域的表示 边边界表示内点表示 区域填充算法 种子 - 种子填充算法 问题 v区域填充算法要求区域一定是_的 连连通 4连通区域 和 8连通区域 4 4p4 4 (b)p的8-邻接点 888 8 8 p8 88 (a)p的4-邻接点 图5-33 邻接点的定义 4连通区域: 通过4个方向的运动 遍历区域 8连通区域: 通过8个方向的运动 遍历区域 图5-32 区域的边界表示和内点表示 (b)以内点表示的 4-连通区域 (d)以内点表示的 8-连通区域 图5-32 区域的边界表示和内点表示 (a)以边界表示的 4-连通区域 (c)以边界表示的 8-连通区域 补充 v4连通区域也可理解成8连通区域，但是两 者的边界不尽相同 4连通区 域 号 8连通区 域 号 号 区域填充算法 v内点表示 - 泛填充算法 （Flood-fill Algorithm） v边界表示法 - 边界填充算法 （Boundary -fill Algorithm） 4-连通 边界填充算法步骤 - 栈结构实现 v输入初值: 种子点坐标(x,y)、填充色、边界颜色 v种子像素入栈 v当栈非空时重复执行如下操作 (1)栈顶像素出栈； (2)将出栈像素置成填充色； (3)检查出栈像素的4-邻接点， 若其中某个像素点 不是边界色 且 未置成填充色， 则把该像素入栈。 0 种子像素入栈 1 2 1 2 B D CA 入栈栈条件: 不是边边界色 且未置成填 充色 4 5 13 4 5 3 1 不是边界 色且未置 成填充色 4 13 4 3 1 不是边界 色且未置 成填充色 6 133 1 不是边界 色且未置 成填充色 6 3 7 133 1 不是边界 色且未置 成填充色 7 3 8 133 1 不是边界 色且未置 成填充色 8 9 9 小结: 4-连通 边界填充算法 v凡是栈中出现的元素都是等待被填充的 v填充步骤 出栈 置填充色 4-邻接点入栈 (非边界色, 非填充色) vFlash演示 4连通边界填充算法 8-连通 边界填充算法步骤 v出栈 v置填充色 v8-邻接点入栈 (非边界色,非填充色) v简单的边界填充算法 栈操作多 栈的存储空间大 v沿扫描线填充水平像素段的4-连通边界填 充算法 P131 P131 图图5-34 5-34 Flash演示 出栈 置填充色 - 连续像素段 入栈 - 当前扫描线相邻的上下两条扫描线的最 左像素 2. 泛填充算法 - 栈结构 实现 v算法输入:种子点坐标(x,y)、填充色、内点颜色 v种子像素入栈； v当栈非空时作如下操作： (1)栈顶像素出栈； (2)将出栈像素置成填充色； (3)检查出栈像素的4-邻接点， 若 其中某个像素点， 内点的颜色且未置成填充色， 则把该像素入栈。 12 4356 9810 117 14131512 1716填充色: 绿色 内点颜色: 橙色 12 4356 9810 117 14131512 1716 9 12 4356 9810 117 14131512 1716 9 12 4356 9810 117 14131512 1716 4 B D CA 10 14 8 12 4356 9810 117 14131512 1716 B D CA 10 14 8 4 12 4356 9810 117 14131512 1716 3 B D CA 10 14 8 5 12 4356 9810 117 14131512 1716 3 B D CA 10 14 8 5 12 4356 9810 117 14131512 1716 3 10 14 8 10 6 2 12 4356 9810 117 14131512 1716 3 10 14 8 10 6 2 12 4356 9810 117 14131512 1716 3 10 14 8 10 6 12 4356 9810 117 14131512 1716 3 10 14 8 10 11 vFlash演示 8 连通泛填充算法 对比 边界填充算法 (1)栈顶像素出栈； (2)将出栈像素置成填充 色； (3)检查出栈像素的 4-邻接点， 若其中某个像素点 不是边界色 且未置成填充色， 则把该像素入栈。 泛填充算法 (1)栈顶像素出栈； (2)将出栈像素置成填充 色； (3)检查出栈像素的 4-邻接点， 若其中某个像素点 是内点的颜色 且未置成填充色， 则把该像素入栈。 小结 区域填充算法 v边界填充算法(8连通, 4连通) v泛填充算法(8连通, 4连通) 简单种子填充算法 基于扫描线的种子填充算法 小结 算法步骤 v初