案例8 四邻接点种子填充算法

计算机图形学实践教程（VisualC++版）（第2版）孔令德太原工业学院计算机工程系2017.1.10案例8四邻接点种子填充算法知识点四邻接点种子填充算法。判断种子像素位于多边形之内的方法。种子像素四邻接点的访问方法。堆栈操作函数。案例描述请使用四邻接点种子算法填充示例多边形。在1024×768的显示分辨率下，将多边形顶点放大为P0（50,100），P1(-150,300)，P2(-250,50)，P3(-150,-250)，P4(0,-50),P5(100,-250),P6(300,150)。效果图图8-1效果图原理算法（1）调用颜色对话框读取填充色。（2）绘制示例多边形区域。（3）设置默认边界色为黑色，默认种子色为蓝色。（4）鼠标选择种子的像素的坐标（x0,y0）位置，执行x=x0±1与y=y0±1操作，判断x或y是否到达客户区边界。如果x或y到达客户区边界，给出“种子不在图形之内”的警告信息，重新选择种子像素的位置。（5）将位于多边形区域之内的种子像素入栈。（6）如果栈不为空，将栈顶的像素点出栈，用种子色绘制出栈像素。（7）按左、上、右、下顺序搜索出栈像素的四个邻接点像素。如果相邻像素的颜色不是边界色并且不是种子色，将其入栈，否则丢弃。（8）重复步骤（6），直到栈为空。程序代码（1）建立栈结点类CStackNode栈结点用于动态存储多边形内区域内的像素，PixelPoint为像素的坐标。classCStackNode{public:CStackNode();virtual~CStackNode();public:CP2PixelPoint;CStackNode*pNext;};程序代码（2）入栈函数voidCTestView::Push(CP2point){pTop=newCStackNode;pTop-PixelPoint=point;pTop-pNext=pHead-pNext;pHead-pNext=pTop;}程序代码（3）出栈函数voidCTestView::Pop(CP2&point){if(pHead-pNext!=NULL){pTop=pHead-pNext;pHead-pNext=pTop-pNext;point=pTop-PixelPoint;deletepTop;}}程序代码（4）填充函数voidCTestView::FillPolygon(CDC*pDC){COLORREFBoundaryClr=RGB(0,0,0);//边界色COLORREFPixelClr;//当前像素的颜色pHead=newCStackNode;//建立栈头结点pHead-pNext=NULL;//栈头结点的指针域总为空Push(Seed);//种子像素入栈CP2PopPoint;Pop(PopPoint);pDC-SetPixelV(Round(PopPoint-PixelPoint.x),Round(PopPoint-PixelPoint.y),SeedClr);PointLeft.x=PopPoint-PixelPoint.x-1;//搜索出栈结点的左方像素PointLeft.y=PopPoint-PixelPoint.y;PixelClr=pDC-GetPixel(Round(PointLeft.x),Round(PointLeft.y));if(BoundaryClr!=PixelClr&&SeedClr!=PixelClr)Push(PointLeft);//左方像素入栈程序代码（4）填充函数PointTop.x=PopPoint-PixelPoint.x;PointTop.y=PopPoint-PixelPoint.y+1;//搜索出栈结点的上方像素PixelClr=pDC-GetPixel(Round(PointTop.x),Round(PointTop.y));if(BoundaryClr!=PixelClr&&SeedClr!=PixelClr)Push(PointTop);//上方像素入栈PointRight.x=PopPoint-PixelPoint.x+1;//搜索出栈结点的右方像素PointRight.y=PopPoint-PixelPoint.y;PixelClr=pDC-GetPixel(Round(PointRight.x),Round(PointRight.y));if(BoundaryClr!=PixelClr&&SeedClr!=PixelClr)Push(PointRight);//右方像素入栈PointBottom.x=PopPoint-PixelPoint.x;PointBottom.y=PopPoint-PixelPoint.y-1;//搜索出栈结点的下方像素PixelClr=pDC-GetPixel(Round(PointBottom.x),Round(PointBottom.y));if(BoundaryClr!=PixelClr&&SeedClr!=PixelClr)Push(PointBottom);//下方像素入栈}}总结本案例设计了CStackNode类用于执行堆栈操作。种子填充算法一般要求填充色与边界色不同。种子算法将太多的像素入栈，当图形较大时，栈内的数据量庞大，填充效率很低。改进方法是使用扫描线种子填充算法，这样入栈与出栈的像素只有扫描线的起点与终点像素，填充效率得到明显改善。