Ch多边形区域填充实用.pptx
YTU区域填充算法种种子子-种子填充算法第1页/共37页YTU问题区域填充算法要求区域一定是_的连通通第2页/共37页YTU4连通区域 和 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 邻接点的定义第3页/共37页YTU4连通区域连通区域:通过通过4 4个方向的运动个方向的运动遍历区域遍历区域8连通区域连通区域:通过通过8 8个方向的运动个方向的运动遍历区域遍历区域第4页/共37页YTU图5-32 区域的边界表示和内点表示(b)(b)以内点表示的4-4-连通区域(d)(d)以内点表示的8-8-连通区域第5页/共37页YTU图5-32 区域的边界表示和内点表示(a)(a)以边界表示的4-4-连通区域(c)(c)以边界表示的8-8-连通区域第6页/共37页YTU补充4连通区域也可理解成8连通区域，但是两者的边界不尽相同4连通区域 号8连通区域 号 号第7页/共37页YTU区域填充算法内点表示 -泛填充算法 （Flood-fill Algorithm）边界表示法-边界填充算法（Boundary-fill Algorithm）第8页/共37页YTU4-连通 边界填充算法步骤-栈结构实现输入初值:种子点坐标(x,y)、填充色、边界颜色 种子像素入栈当栈非空时重复执行如下操作(1)栈顶像素出栈；(2)将出栈像素置成填充色；(3)检查出栈像素的4-邻接点，若其中某个像素点 不是边界色 且 未置成填充色，则把该像素入栈。第9页/共37页0种子像素入栈第10页/共37页1212BDCA入入栈条条件件:不是不是边界色界色且未置成且未置成填填充色充色 第11页/共37页45134531不是边界色且未置成填充色 第12页/共37页413431不是边界色且未置成填充色 第13页/共37页61331不是边界色且未置成填充色 6第14页/共37页371331不是边界色且未置成填充色 7第15页/共37页381331不是边界色且未置成填充色 899第16页/共37页YTU小结:4-连通 边界填充算法凡是栈中出现的元素都是等待被填充的填充步骤出栈置填充色4-邻接点入栈(非边界色,非填充色)Flash演示 4连通边界填充算法第17页/共37页YTU8-连通 边界填充算法步骤出栈置填充色8-邻接点入栈(非边界色,非填充色)第18页/共37页YTU简单的边界填充算法栈操作多栈的存储空间大沿扫描线填充水平像素段的4-连通边界填充算法 P131 图5-34 Flash演示出栈置填充色-连续像素段入栈-当前扫描线相邻的上下两条扫描线的最左像素第19页/共37页YTU2.泛填充算法-栈结构 实现算法输入:种子点坐标(x,y)、填充色、内点颜色种子像素入栈；当栈非空时作如下操作：(1)栈顶像素出栈；(2)将出栈像素置成填充色；(3)检查出栈像素的4-邻接点，若其中某个像素点，内点的颜色且未置成填充色，则把该像素入栈。第20页/共37页1243569810 117141315121716填充色:绿色内点颜色:橙色第21页/共37页1243569810 1171413151217169第22页/共37页1243569810 1171413151217169第23页/共37页1243569810 1171413151217164BDCA10148第24页/共37页1243569810 117141315121716BDCA101484第25页/共37页1243569810 1171413151217163BDCA101485第26页/共37页1243569810 1171413151217163BDCA101485第27页/共37页1243569810 1171413151217163101481062第28页/共37页1243569810 1171413151217163101481062第29页/共37页1243569810 117141315121716310148106第30页/共37页1243569810 1171413151217163101481011第31页/共37页YTUFlash演示 8 连通泛填充算法第32页/共37页YTU对比边界填充算法(1)栈顶像素出栈；(2)将出栈像素置成填充色；(3)检查出栈像素的 4-邻接点，若其中某个像素点 不是边界色 且未置成填充色，则把该像素入栈。泛填充算法(1)栈顶像素出栈；(2)将出栈像素置成填充色；(3)检查出栈像素的 4-邻接点，若其中某个像素点 是内点的颜色 且未置成填充色，则把该像素入栈。第33页/共37页YTU小结 区域填充算法边界填充算法(8连通,4连通)泛填充算法(8连通,4连通)简单种子填充算法基于扫描线的种子填充算法第34页/共37页YTU小结 算法步骤初始:种子入栈栈顶元素出栈填充该元素填充该元素所在扫描线寻找新的种子入栈4邻接点/8邻接点填充色/边界色/内点色相邻上下两扫描线最左像素第35页/共37页YTU思考题 p132课堂练习 区域填充第36页/共37页YTU感谢您的欣赏！第37页/共37页
