《第4章多边形填充PPT课件》由会员分享，可在线阅读，更多相关《第4章多边形填充PPT课件（33页珍藏版）》请在金锄头文库上搜索。
1、第第第第4 4章多边形填充章多边形填充章多边形填充章多边形填充4.4 区域填充4.4.1 4.4.1 填充原理填充原理 对于用点阵方法表示的区域，如果其内部像素具有同一种颜色，而边界像素具有另一种颜色，可以使用种子填充算法种子填充算法进行填充。4.4.1 4.4.1 填充原理填充原理 种子填充算法是从区域内种子填充算法是从区域内任一个任一个种子像种子像素位置开始，由素位置开始，由内向外内向外将种子像素的颜色扩将种子像素的颜色扩展到整个区域内的填充过程。展到整个区域内的填充过程。4.4.1 4.4.1 填充原理填充原理 种子填充算法基于连通域内像素的种子填充算法基于连通域内像素的连贯性连贯性，以
2、递归方式确定区域内部点与边界点，而不涉及以递归方式确定区域内部点与边界点，而不涉及区域外部的点，从而有效地提高了算法的效率。区域外部的点，从而有效地提高了算法的效率。 4.4.2 4.4.2 四邻接点与八邻接点四邻接点与八邻接点 （a）四邻接点 区域内部任意一个种子像素，其左、上、右、区域内部任意一个种子像素，其左、上、右、下这下这4 4个像素个像素称为称为四邻接点四邻接点。 4.4.2 4.4.2 四邻接点与八邻接点四邻接点与八邻接点 （b）八邻接点 区域内部任意一个种子像素，其左、上、右、区域内部任意一个种子像素，其左、上、右、下以及左上、右上、右下、左下这下以及左上、右上、右下、左下这8
3、 8个像素个像素称为称为八八邻接点邻接点。4.4.3 4.4.3 四连通域与八连通域四连通域与八连通域 种子填充算法要求区域内部必须是种子填充算法要求区域内部必须是连通连通的，才的，才能将种子像素的颜色扩展到区域内部的所有像素点。能将种子像素的颜色扩展到区域内部的所有像素点。1.1.四连通域定义四连通域定义 从区域内部任意一个种子像素点出发，通过访问其左、上、右、下这4个邻接点可以遍历区域内的所有像素点，该区域称为四连通域称为四连通域。 4.4.3 4.4.3 四连通域与八连通域四连通域与八连通域 2.2.八连通域定义八连通域定义从区域内部任意一个种子像素点出发，通过访问其左、左上、上、右上、
4、右、右下、下、左下这8个邻接点可以遍历区域内的所有像素，该区域称为八连称为八连通域。通域。 四连通域及四连通约束边界四连通域及四连通约束边界 四连通域及八连通约束边界四连通域及八连通约束边界 4.4.3 4.4.3 四连通域与八连通域四连通域与八连通域 八连通域及四连通约束边界八连通域及四连通约束边界 八连通域及八连通约束边界八连通域及八连通约束边界 4.4.3 4.4.3 四连通域与八连通域四连通域与八连通域 四邻接点种子填充八连通域四邻接点种子填充八连通域 八邻接点种子填充八连通域八邻接点种子填充八连通域4.4.3 4.4.3 四连通域与八连通域四连通域与八连通域 边边界界表表示示：把位于
5、给给定定区区域域的的边边界界上上的象素一一列举出来的方法。区域的边界点有相同颜色。其其填填充充算算法法有有扫扫描描线线填填充充算算法法或或边边界界填填充充算算法法（Boundary-fill Algorithm）。区域两种表示形式：区域两种表示形式：内内点点表表示示：枚举出给给定定区区域域内内所有象素的表示方法。即区域内的所有象素有相同的颜色。其其填填充充算算法法常常为为种种子子填填充充或或泛泛填填充充算算法法（递递归算法）归算法）区域两种表示形式：区域两种表示形式：4.4.4 4.4.4 种子填充算法种子填充算法 1.算法定义算法定义 从种子像素点开始，使用四邻接点方式搜索从种子像素点开始，
6、使用四邻接点方式搜索下一像素点的填充算法下一像素点的填充算法称为称为四邻接点种子填充算四邻接点种子填充算法法。 从种子像素点开始，使用八邻接点方式搜索从种子像素点开始，使用八邻接点方式搜索下一像素点的填充算法下一像素点的填充算法称为八称为八邻接点种子填充算邻接点种子填充算法。法。4.4.4 4.4.4 种子填充算法种子填充算法 2. 算法原理算法原理 种子填充算法一般需要使用堆栈数据结构来种子填充算法一般需要使用堆栈数据结构来实现。实现。class Stack_nodepublic:Stack_node();Virtual Stack_node();Cpoint PixelPoint;Stac
7、k_node *Next1.1.边界表示的四连通区域种子填充算法边界表示的四连通区域种子填充算法 基本思想：从多边形内部任一点像素出发，按照“左上右下左上右下”的顺序判断相邻像素，若不是边界像素且没有被填充过，则对其填充，并重复上述过程，直到所有像素填充完毕。1.1.边界表示的四连通区域种子填充算法边界表示的四连通区域种子填充算法 使用栈结构来实现该算法，种子像素入栈，当栈非空时，重复执行如下操作：（1）栈顶像素出栈；（2）将出栈像素置成多边形填充的颜色；（3）按“左上右下”的顺序检查与出栈像素相邻的四个像素，若其中某个像素不在边界上且未置成多边形色，则把该像素入栈。void Boundary
8、Fill( int x, int y, int bcolor, int ncolor ) color = GetPixel(x,y)； if (color!=bcolor)&(color!=ncolor) PutPixel( x, y, ncolor)； BoundaryFill(x-1, y, bcolor, ncolor)； BoundaryFill(x, y+1, bcolor, ncolor)； BoundaryFill(x+1, y, bcolor, ncolor)； BoundaryFill(x, y-1, bcolor, ncolor)； 边界表示的四连通区域内的一点定义区域边界
9、的颜色区域要填充的颜色边界表示的四连通区域的递归填充算法如下：边界表示的四连通区域的递归填充算法如下：1算法功能：算法功能：按顺序重新着色按顺序重新着色顺序：顺序：上下左右上下左右思考：如果是左上右思考：如果是左上右下顺序呢？请填写右下顺序呢？请填写右下图序号下图序号23465其它颜色1其它颜色124634567891011121314151617181920 2122232425262728 2930 3132 3334 3536373839404142434445P递归填充算法（上下左右）：递归填充算法（上下左右）：Void Fill(int x,int y,int bcolor, int
10、 ncolor) int color； color = GetPixel(x,y)； if (color!=bcolor)&(color!=ncolor) PutPixel( x, y, ncolor)； Fill(x, y+1, bcolor, ncolor)； Fill(x, y -1, bcolor, ncolor)； Fill(x -1, y, bcolor, ncolor)； Fill(x +1, y, bcolor, ncolor)； 思考：如果换成左上右下的顺序呢？思考：如果换成左上右下的顺序呢？2.2.内点表示的四连通区域种子填充算法内点表示的四连通区域种子填充算法 基本思想：
11、从多边形内部任一点像素出发，基本思想：从多边形内部任一点像素出发，按照按照“左上右下左上右下”的顺序判断相邻像素，如果的顺序判断相邻像素，如果是是区域内区域内的像素，则对其填充，并重复上述过的像素，则对其填充，并重复上述过程，直到所有像素填充完毕，常称为程，直到所有像素填充完毕，常称为漫水法漫水法。 2.2.内点表示的四连通区域种子填充算法内点表示的四连通区域种子填充算法 Void FloodFill (int x,int y,int oldcolor,int newcolor)Void FloodFill (int x,int y,int oldcolor,int newcolor) col
12、or=GetPixel(x,y); color=GetPixel(x,y); if(color=oldcolor) if(color=oldcolor) PutPixel(x,y,newcolor); PutPixel(x,y,newcolor); FloodFill(x-1,y,oldcolor,newcolor); FloodFill(x-1,y,oldcolor,newcolor); FloodFill(x,y+1,oldcolor,newcolor); FloodFill(x,y+1,oldcolor,newcolor); FloodFill(x+1,y,oldcolor,newcol
13、or); FloodFill(x+1,y,oldcolor,newcolor); FloodFill(x,y-1,oldcolor,newcolor); FloodFill(x,y-1,oldcolor,newcolor); 算法实现算法实现栈结构栈结构 种子像素入栈，当栈非空时，重复执行如下操作（1）栈顶像素出栈；（2）将出栈像素置成多边形填充的颜色；（3）按“左上右下”的顺序检查与出栈像素相邻的四个像素，若其中某个像素不在边界上且未置成多边形色，则把该像素入栈。2.2.内点表示的四连通区域种子填充算法内点表示的四连通区域种子填充算法 算法特点算法特点：可以用于填充带有内孔的平面区域。把太多
14、的象素压入堆栈，有些象素会入栈多次，降低算法效率；栈结构占空间2.2.内点表示的四连通区域种子填充算法内点表示的四连通区域种子填充算法 改进改进：减少递归次数，提高效率。通过沿扫描线填充水平象素段，来代替处理4-邻接点和8-邻接点。方法之一：扫描线填充算法2.2.内点表示的四连通区域种子填充算法内点表示的四连通区域种子填充算法 基本思想基本思想： 1、在任意不间断区间（一条扫描线上的一组相邻像素）中，选取一个种子像素，填充当前扫描线上的该段区间。3.3.扫描线种子填充算法扫描线种子填充算法 基本思想基本思想： 2、确定与这一区段相邻的相邻的上下两条扫描线位于区域内的区段，并依次把它们保存起来，
15、反复进行这个过程，直到所保存的每个区段都填充完毕。3.3.扫描线种子填充算法扫描线种子填充算法 算法执行步骤:1）初始化：堆栈置空，将种子点(x，y)入栈。2）出栈：若栈空则结束，否则栈顶元素(x，y)出栈，并以y值作为当前扫描线号。3.3.扫描线种子填充算法扫描线种子填充算法 算法执行步骤:3)填充并确定种子点所在区段：从种子点(x，y)出发，沿当前扫描线向左、向右两个方向逐个像素填充，直到遇到边界像素为止。分别标记区段的左、右端点坐标为xl和xr。3.3.扫描线种子填充算法扫描线种子填充算法 算法执行步骤:4)确定新的种子点：在区间xl,xr中检查与当前扫描线y相邻的上、下两条扫描线上的像素。若存在非边界、未填充的像素，则把每一区间的最右像素作为种子点压人堆栈，返回第(2)步。否则直返回第2)步。 3.3.扫描线种子填充算法扫描线种子填充算法 a）选取种子点入栈）选取种子点入栈1b）选取相邻扫描线上）选取相邻扫描线上的种子点的种子点1 234c）种子出栈填充再选）种子出栈填充再选相邻种子相邻种子43256d）最后一个种子栈出栈）最后一个种子栈出栈11 扫描线种子填充算法在每一填充区间内，只保留其最右端像素作为种子像素入栈，极大地减小了栈空间极大地减小了栈空间，有效地提高了填充速度。 3.3.扫描线种子填充算法扫描线种子填充算法
