●表示内点○表示边界点 图2.3.8区域的内点表示和边界表示 2.3.2.1区域填充的递归算法 以上讨论的多边形填充算法是按扫描线顺序进行的。种子填充算法假设在多边形内有一象素已知,由此 出发利用连通性找到区域内的所有象素 设(xy)为内点表示的4连通区域内的一点, oldcolor为区域的原色,要将整个区域填充为新的颜色 newcolor。内点表示的4连通区域的递归填充算法 void FloodFill4(int x, int y, int oldcolor int newcolor) f(getpixel(x, y)==oldcolor i drawpixel(x,y, newcolor) FloodFill4(x, y+1, oldcolor, newcolor) FloodFill4(x, y-1, oldcolor, newcolor) FloodFil4(X-1,y, oldcolor, newcolor) FloodFill4(+1, y, oldcolor, newcolor) 边界表示的4连通区域的递归填充算法 void BoundaryFill4(nt x, int y int boundarycolor, int newcolor) f int color if(colorl=newcolor & colorl=boundarycolor) i drawpixel(x,y, newcolor) Boundary Fill4(x, y+1, boundarycolor, newcolor) Boundary Fill4 (x, y-1, boundarycolor, newcolor) oundary Fill4 (X-1,y, boundarycolor, newcolor Boundary Fill4 (X+1,y, boundarycolor, newcolor) 对于内点表示和边界表示的8连通区域的填充,只要将上述相应代码中递归填充相邻的4个象素增加到递 归填充8个象素即可 2.3.22区域填充的扫描线算法 区域填充的递归算法原理和程序都很简单,但由于多次递归,费时、费内存,效率不高。为了减少递归 次数,提高效率可以采用采用扫描线算法。算法的基本过程如下:当给定种子点(X,y)时,首先填充种子点 所在扫描线上的位于给定区域的一个区段,然后确定与这一区段相连通的上、下两条扫描线上位于给定区 域内的区段,并依次保存下来。反复这个过程,直到填充结束 区域填充的扫描线算法可由下列四个步骤实现: (1)初始化:堆栈置空。将种子点(x,y)入栈 (2)出栈:若栈空则结束。否则取栈顶元素(X,y),以y作为当前扫描线。 (③)填充并确定种子点所在区段:从种子点(X,y)出发,沿当前扫描线向左、右两个方向填充,直到边界 分别标记区段的左、右端点坐标为x和xr (4)并确定新的种子点:在区间[,xr中检査与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非 边界、未填充的象素,则把每一区间的最右象素作为种子点压入堆栈,返回第(2)步 typedef struct∥记录种子点 int y: I Seed void ScanLineFill4(int x, int y, COLORREF oldcolor, COLORREF newcolor) int xl. xr, i bool spanNeedFill 计算机图形学第二章第25页共27页计算机图形学 第二章 第 25 页 共 27 页 图 2.3.8 区域的内点表示和边界表示 2.3.2.1 区域填充的递归算法 以上讨论的多边形填充算法是按扫描线顺序进行的。种子填充算法假设在多边形内有一象素已知，由此 出发利用连通性找到区域内的所有象素。 设（x,y）为内点表示的 4 连通区域内的一点，oldcolor 为区域的原色，要将整个区域填充为新的颜色 newcolor。内点表示的 4 连通区域的递归填充算法: void FloodFill4(int x,int y,int oldcolor,int newcolor) { if(getpixel(x,y)==oldcolor) { drawpixel(x,y,newcolor); FloodFill4(x,y+1,oldcolor,newcolor); FloodFill4(x,y-1,oldcolor,newcolor); FloodFill4(x-1,y,oldcolor,newcolor); FloodFill4(x+1,y,oldcolor,newcolor); } } 边界表示的 4 连通区域的递归填充算法: void BoundaryFill4(int x,int y,int boundarycolor,int newcolor) { int color; if(color!=newcolor && color!=boundarycolor) { drawpixel(x,y,newcolor); BoundaryFill4 (x,y+1, boundarycolor,newcolor); BoundaryFill4 (x,y-1, boundarycolor,newcolor); BoundaryFill4 (x-1,y, boundarycolor,newcolor); BoundaryFill4 (x+1,y, boundarycolor,newcolor); } } 对于内点表示和边界表示的 8 连通区域的填充，只要将上述相应代码中递归填充相邻的 4 个象素增加到递 归填充 8 个象素即可。 2.3.2.2 区域填充的扫描线算法 区域填充的递归算法原理和程序都很简单，但由于多次递归，费时、费内存，效率不高。为了减少递归 次数，提高效率可以采用采用扫描线算法。算法的基本过程如下：当给定种子点(x,y)时，首先填充种子点 所在扫描线上的位于给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区 域内的区段，并依次保存下来。反复这个过程，直到填充结束。 区域填充的扫描线算法可由下列四个步骤实现： (1)初始化：堆栈置空。将种子点（x，y）入栈。 (2)出栈：若栈空则结束。否则取栈顶元素（x，y），以 y 作为当前扫描线。 (3)填充并确定种子点所在区段：从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到边界。 分别标记区段的左、右端点坐标为 xl 和 xr。 (4)并确定新的种子点：在区间[xl，xr]中检查与当前扫描线 y 上、下相邻的两条扫描线上的象素。若存在非 边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。 typedef struct{ //记录种子点 intx; int y； } Seed; void ScanLineFill4(int x,int y,COLORREF oldcolor,COLORREF newcolor) { int xl,xr,i; bool spanNeedFill;