Ch多边形区域填充.pptx

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(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 4连通区域也可理解成连通区域也可理解成8 8连通区域，但是两连通区域，但是两者的边界不尽相同者的边界不尽相同4连通区连通区域域 号号8连通区连通区域域 号号 号号YTUYTU区域填充算法v内点表示内点表示 -泛填充算法泛填充算法 （Flood-fill AlgorithmFlood-fill Algorithm）v边界表示法边界表示法 -边界填充算法边界填充算法 （Boundary-fill AlgorithmBoundary-fill Algorithm）YTUYTU4-连通 边界填充算法步骤-栈结构实现v输入初值输入初值:种子点坐标种子点坐标(x,y)(x,y)、填充色、边界颜色、填充色、边界颜色 v种子像素入栈种子像素入栈v当栈非空时重复执行如下操作当栈非空时重复执行如下操作(1)(1)栈顶像素出栈；栈顶像素出栈；(2)(2)将出栈像素置成填充色；将出栈像素置成填充色；(3)(3)检查出栈像素的检查出栈像素的4-4-邻接邻接点，点，若其中某个像素点若其中某个像素点 不是边界色不是边界色 且且 未置成填充色未置成填充色，则把该像素入栈。则把该像素入栈。0种子像素入栈种子像素入栈1212BDCA入入栈条条件件:不是不是边界色界色且未置成且未置成填填充色充色 45134531不是边界不是边界色且未置色且未置成填充色成填充色 413431不是边界不是边界色且未置色且未置成填充色成填充色 61331不是边界不是边界色且未置色且未置成填充色成填充色 6371331不是边界不是边界色且未置色且未置成填充色成填充色 7381331不是边界不是边界色且未置色且未置成填充色成填充色 899YTUYTU小结:4-连通 边界填充算法v凡是栈中出现的元素都是等待被填充的凡是栈中出现的元素都是等待被填充的v填充步骤填充步骤出栈出栈置填充色置填充色4 4-邻接点入栈邻接点入栈 (非边界色非边界色,非填充色非填充色)vFlashFlash演示演示 4 4连通边界填充算法连通边界填充算法YTUYTU8-连通 边界填充算法步骤v出栈出栈v置填充色置填充色v8 8-邻接点入栈邻接点入栈 (非边界色非边界色,非填充色非填充色)YTUYTUv简单的边界填充算法简单的边界填充算法栈操作多栈操作多栈的存储空间大栈的存储空间大v沿扫描线填充水平像素段的沿扫描线填充水平像素段的4-4-连通边界填连通边界填充算法充算法 P131 P131 图图5-34 5-34 FlashFlash演示演示出栈出栈置填充色置填充色 -连续像素段连续像素段入栈入栈 -当前扫描线相邻的上下两条扫描线的当前扫描线相邻的上下两条扫描线的最最左像素左像素YTUYTU2.泛填充算法-栈结构 实现v算法输入算法输入:种子点坐标种子点坐标(x,y)(x,y)、填充色、内点颜色、填充色、内点颜色v种子像素入栈；种子像素入栈；v当栈非空时作如下操作：当栈非空时作如下操作：(1)(1)栈顶像素栈顶像素出栈出栈；(2)(2)将出栈像素将出栈像素置成填充色置成填充色；(3)(3)检查出栈像素的检查出栈像素的4-4-邻接点邻接点，若若其中某个像素点，其中某个像素点，内点的颜色且未置成填充色内点的颜色且未置成填充色，则把该像素则把该像素入栈入栈。1243569810117141315121716填充色填充色:绿色绿色内点颜色内点颜色:橙色橙色124356981011714131512171691243569810117141315121716912435698101171413151217164BDCA101481243569810117141315121716BDCA10148412435698101171413151217163BDCA10148512435698101171413151217163BDCA1014851243569810117141315121716310148106212435698101171413151217163101481062124356981011714131512171631014810612435698101171413151217163101481011YTUYTUvFlashFlash演示演示 8 8 连通泛填充算法连通泛填充算法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栈顶元素出栈栈顶元素出栈填充该元素填充该元素填充该元素所在扫描线填充该元素所在扫描线v寻找新的种子入栈寻找新的种子入栈4 4邻接点邻接点 /8/8邻接点邻接点填充色填充色 /边界色边界色 /内点色内点色相邻上下两扫描线最左像素相邻上下两扫描线最左像素YTUYTUv思考题思考题 p132p132v课堂练习课堂练习 区域填充区域填充