Ch543多边形区域填充

1、ytuytu5.4.3 区域填充v区域区域点阵形式的填充图形点阵形式的填充图形, ,是像素的集合是像素的集合v区域的表示区域的表示 边界表示法边界表示法 内点表示内点表示v区域填充算法区域填充算法 边界填充算法边界填充算法 泛填充算法泛填充算法ytuytu区域的表示边边界表示界表示内内点表示点表示ytuytu区域填充算法种种子子- 种子填充算法ytuytu问题v区域填充算法要求区域一定是区域填充算法要求区域一定是_的的连连通通ytuytu4连通区域 和 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

2、(a)p的的4-4-邻接点邻接点图图5-33 5-33 邻接点的定义邻接点的定义ytuytu4连通区域连通区域: 通过通过4 4个方向的运动个方向的运动遍历区域遍历区域8连通区域连通区域: 通过通过8 8个方向的运动个方向的运动遍历区域遍历区域ytuytu图5-32 区域的边界表示和内点表示(b)(b)以内点表示的以内点表示的4-4-连通区域连通区域(d)(d)以内点表示的以内点表示的8-8-连通区域连通区域ytuytu图5-32 区域的边界表示和内点表示(a)(a)以边界表示的以边界表示的4-4-连通区域连通区域(c)(c)以边界表示的以边界表示的8-8-连通区域连通区域ytuytu补充v4

3、 4连通区域也可理解成连通区域也可理解成8 8连通区域，但是两连通区域，但是两者的边界不尽相同者的边界不尽相同4连通区连通区域域 号号8连通区连通区域域 号号 号号ytuytu区域填充算法v内点表示内点表示 - - 泛填充算法泛填充算法 （flood-fill algorithmflood-fill algorithm） v边界表示法边界表示法 - - 边界填充算法边界填充算法 （boundary-fill algorithmboundary-fill algorithm）ytuytu4-连通 边界填充算法步骤 - 栈结构实现v输入初值输入初值: : 种子点坐标种子点坐标(x,y)(x,y)、

4、填充色、边界颜色、填充色、边界颜色 v种子像素入栈种子像素入栈v当栈非空时重复执行如下操作当栈非空时重复执行如下操作(1)(1)栈顶像素出栈；栈顶像素出栈；(2)(2)将出栈像素置成填充色；将出栈像素置成填充色；(3)(3)检查出栈像素的检查出栈像素的4-4-邻接邻接点，点， 若其中某个像素点若其中某个像素点 不是边界色不是边界色 且且 未置成填充色未置成填充色， 则把该像素入栈。则把该像素入栈。0种子像素入栈种子像素入栈1212bdca入入栈条栈条件件: :不是不是边边界色界色且未置成且未置成填填充色充色 45134531不是边界不是边界色且未置色且未置成填充色成填充色 413431不是边界

5、不是边界色且未置色且未置成填充色成填充色 61331不是边界不是边界色且未置色且未置成填充色成填充色 6371331不是边界不是边界色且未置色且未置成填充色成填充色 7381331不是边界不是边界色且未置色且未置成填充色成填充色 899ytuytu小结: 4-连通 边界填充算法v凡是栈中出现的元素都是等待被填充的凡是栈中出现的元素都是等待被填充的v填充步骤填充步骤 出栈出栈 置填充色置填充色 4 4- -邻接点入栈邻接点入栈 ( (非边界色非边界色, , 非填充色非填充色) )vflashflash演示演示 4 4连通边界填充算法连通边界填充算法ytuytu8-连通 边界填充算法步骤v出栈出栈

6、v置填充色置填充色v8 8- -邻接点入栈邻接点入栈 ( (非边界色非边界色, ,非填充色非填充色) )ytuytuv简单的边界填充算法简单的边界填充算法 栈操作多栈操作多 栈的存储空间大栈的存储空间大v沿扫描线填充水平像素段的沿扫描线填充水平像素段的4-4-连通边界填连通边界填充算法充算法 flashflash演示演示 出栈出栈 置填充色置填充色 - - 连续像素段连续像素段 入栈入栈 - - 当前扫描线相邻的上下两条扫描线的当前扫描线相邻的上下两条扫描线的最左像素最左像素ytuytu2. 泛填充算法 - 栈结构 实现v算法输入算法输入: :种子点坐标种子点坐标(x,y)(x,y)、填充色、

7、内点颜色、填充色、内点颜色v种子像素入栈；种子像素入栈； v当栈非空时作如下操作：当栈非空时作如下操作：(1)(1)栈顶像素栈顶像素出栈出栈；(2)(2)将出栈像素将出栈像素置成填充色置成填充色；(3)(3)检查出栈像素的检查出栈像素的4-4-邻接点邻接点， 若其中某个像素点，若其中某个像素点， 内点的颜色且未置成填充色内点的颜色且未置成填充色， 则把该像素则把该像素入栈入栈。1243569810117141315121716填充色填充色: 绿色绿色内点颜色内点颜色: 橙色橙色12435698101171413151217169124356981011714131512171691243569

8、8101171413151217164bdca101481243569810117141315121716bdca10148412435698101171413151217163bdca10148512435698101171413151217163bdca1014851243569810117141315121716310148106212435698101171413151217163101481062124356981011714131512171631014810612435698101171413151217163101481011ytuytuvflashflash演示演示 8 8

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