Ch多边形区域填充ppt课件

1、5.4.3 区域填充v区域区域v点阵方式的填充图形点阵方式的填充图形, ,是像素的集合是像素的集合v区域的表示区域的表示v边境表示法边境表示法v内点表示内点表示v区域填充算法区域填充算法v边境填充算法边境填充算法v泛填充算法泛填充算法区域的表示边边境表示境表示内内点表示点表示区域填充算法种种子子- 种子填充算法问题v区域填充算法要求区域一定是区域填充算法要求区域一定是_的的连连通通4连通区域 和 8连通区域4 44 4p p4 44 4(b)p(b)p的的8-8-邻接点邻接点8 88 88 88 88 8p p8 88 88 8(a)p(a)p的的4-4-邻接点邻接点图图5-33 5-33 邻

2、接点的定义邻接点的定义4连通区域连通区域: 经过经过4个方向的运动个方向的运动遍历区域遍历区域8连通区域连通区域: 经过经过8个方向的运动个方向的运动遍历区域遍历区域图5-32 区域的边境表示和内点表示(b)(b)以内点表示的以内点表示的4-4-连通区域连通区域(d)(d)以内点表示的以内点表示的8-8-连通区域连通区域图5-32 区域的边境表示和内点表示(a)(a)以边境表示的以边境表示的4-4-连通区域连通区域(c)(c)以边境表示的以边境表示的8-8-连通区域连通区域补充v4 4连通区域也可了解成连通区域也可了解成8 8连通区域，但是两连通区域，但是两者的边境不尽一样者的边境不尽一样4连

3、通区连通区域域 号号8连通区连通区域域 号号 号号区域填充算法v内点表示内点表示 - - 泛填充算法泛填充算法 Flood-fill AlgorithmFlood-fill Algorithm v边境表示法边境表示法 - - 边境填充算法边境填充算法 Boundary-fill AlgorithmBoundary-fill Algorithm4-连通 边境填充算法步骤 - 栈构造实现v输入初值输入初值: : 种子点坐标种子点坐标(x,y)(x,y)、填充色、边境颜色、填充色、边境颜色 v种子像素入栈种子像素入栈v当栈非空时反复执行如下操作当栈非空时反复执行如下操作v(1)(1)栈顶像素出栈；栈

4、顶像素出栈；v(2)(2)将出栈像素置成填充色；将出栈像素置成填充色；v(3)(3)检查出栈像素的检查出栈像素的4-4-邻接点，邻接点， 假设其中某个像素点假设其中某个像素点 不是边境色不是边境色 且且 未置成填充色，未置成填充色， 那么把该像素入栈。那么把该像素入栈。0种子像素入栈种子像素入栈1212BDCA入入栈条栈条件件: :不是不是边边境色境色且未置成且未置成填填充色充色 45134531不是边境不是边境色且未置色且未置成填充色成填充色 413431不是边境不是边境色且未置色且未置成填充色成填充色 61331不是边境不是边境色且未置色且未置成填充色成填充色 6371331不是边境不是边

5、境色且未置色且未置成填充色成填充色 7381331不是边境不是边境色且未置色且未置成填充色成填充色 899小结: 4-连通 边境填充算法v凡是栈中出现的元素都是等待被填充的凡是栈中出现的元素都是等待被填充的v填充步骤填充步骤v出栈出栈v置填充色置填充色v4-4-邻接点入栈邻接点入栈 ( (非边境色非边境色, , 非填充色非填充色) )vFlashFlash演示演示 4 4连通边境填充算法连通边境填充算法8-连通 边境填充算法步骤v出栈出栈v置填充色置填充色v8-8-邻接点入栈邻接点入栈 ( (非边境色非边境色, ,非填充色非填充色) )v简单的边境填充算法简单的边境填充算法v栈操作多栈操作多v

6、栈的存储空间大栈的存储空间大v沿扫描线填充程度像素段的沿扫描线填充程度像素段的4-4-连通边境填连通边境填充算法充算法 P131 P131 图图5-34 Flash5-34 Flash演示演示v出栈出栈v置填充色置填充色 - - 延续像素段延续像素段v入栈入栈 - - 当前扫描线相邻的上下两条扫描线当前扫描线相邻的上下两条扫描线的最左像素的最左像素2. 泛填充算法 - 栈构造 实现v算法输入算法输入: :种子点坐标种子点坐标(x,y)(x,y)、填充色、内点颜色、填充色、内点颜色v种子像素入栈；种子像素入栈； v当栈非空时作如下操作：当栈非空时作如下操作：v(1)(1)栈顶像素出栈；栈顶像素出

7、栈；v(2)(2)将出栈像素置成填充色；将出栈像素置成填充色；v(3)(3)检查出栈像素的检查出栈像素的4-4-邻接点，邻接点， 假设其中某个像素点，假设其中某个像素点， 内点的颜色且未置成填充色，内点的颜色且未置成填充色， 那么把该像素入栈。那么把该像素入栈。1243569810117141315121716填充色填充色: 绿色绿色内点颜色内点颜色: 橙色橙色124356981011714131512171691243569810117141315121716912435698101171413151217164BDCA101481243569810117141315121716BDCA10

8、148412435698101171413151217163BDCA10148512435698101171413151217163BDCA1014851243569810117141315121716310148106212435698101171413151217163101481062124356981011714131512171631014810612435698101171413151217163101481011vFlashFlash演示演示 8 8 连通泛填充算法连通泛填充算法对比边境填充算法(1)栈顶像素出栈；(2)将出栈像素置成填充色；(3)检查出栈像素的 4-邻接点， 假设其中某个像素点 不是边境色 且未置成填充色， 那么把该像素入栈。泛填充算法(1)栈顶像素出栈；(2)将出栈像素置成填充色；(3)检查出栈像素的 4-邻接点， 假设其中某个像素点 是内点的颜色 且未置成填充色， 那么把该像素入栈。小结 区域填充算法v边境填充算法边境填充算法(8(8连通连通, 4, 4连通连通) )v泛填充算法泛填充算法(8(8连通连通, 4, 4连通连通) )v简单种子填充算法简单种子填充算法v基于扫描线的种子填充算法基于扫描线的种子填充算法小结 算法步骤v初始初始: : 种子入栈种子入栈v栈顶元素出栈栈顶元素出栈v填充该元素填充该元素v填充该元素所在扫