第四章多边形灌装.pptVIP

第四章;有效边表填充算法 边缘填充算法 四邻接点种子填充算法 八邻接点种子填充算法 扫描线种子填充算法;4.1　多边形的扫描转换 4.2 有效边表填充算法 4.3 边缘填充算法 4.4 区域填充算法 4.5 本章小结 习题 4;4.1　多边形的扫描转换 ; 多边形是由折线段组成的封闭图形。它由有序顶点的点集Pi（i＝0，…，n-1）及有向边的线集Ei（i＝0，…，n-1）定义，n为多边形的顶点数或边数，且Ei＝PiPi+1，i＝0，…，n-1。这里Pn＝P0，保证了多边形的闭合。多边形可以分为凸、凹多边形以及环。 ; 用多边形的顶点序列来描述。特点是直观、占内存少，易于进行几何变换，但由于没有明确指出哪些像素在多边形内，所以不能直接进行填充，需要对多边形进行扫描转换后才能逐条扫描线填充。 ;⑶多边形的扫描转换;4.1.3 多边形着色模式 ;实际光强;球面的马赫带;对一条扫描线的填充一般分为以下4个步骤 求交：计算扫描线与多边形各边的交点； 排序：把扫描线上所有交点按递增顺序进行排序； 配对：将第一个交点与第二个交点，第三个交点与第四个交点等等进行配对，每对交点代表扫描线与多边形的一个相交区间。 着色：把区间内的像素置为填充色。;4.2　有效边表填充算法 ;;P6;;4.2.3 有效边与有效边表 ;2.有效边表;4.2.4 桶表与边表 ;class CBucket { public: CBucket(); virtual ~CBucket(); public: int ScanLine; //扫描线 CAET *p; //桶上的边表指针 CBucket *next; };;（3）对于每一条扫描线，如果新增多条边，则按x|ymin坐标递增的顺序存放在一个链表中，若x|ymin 相等，则按照1/k由小到大排序，这样就形成边表。;4.3 边缘填充算法; 假定边的顺序为E0、E1、E2、E3、E4、E5和E6。这里，边的顺序并不影响填充结果，只是方便编写循环结构而已。填充过程如图所示。;边缘填充算法原理;void CTestView::FillPolygon(CDC *pDC) { COLORREF BClr=RGB(255,255,255);//背景色 COLORREF FClr=GetClr;//填充色 int ymin,ymax;//边的最小y值与最大y值 double x,y,k;//x,y当前点，k斜率的倒数 for(int i=0;i7;i++)//循环多边形所有边 { int j=(i+1)%7; k=(P[i].x-P[j].x)/(P[i].y-P[j].y);//计算1/k if(P[i].yP[j].y)//得到每条边y的最大值与最小值 { ymin=Round(P[i].y); ymax=Round(P[j].y); x=P[i].x;//得到x|ymin } else { ymin=Round(P[j].y); ymax=Round(P[i].y); x=P[j].x; } ;P[i]; for(y=ymin;yymax;y++)//沿每一条边循环扫描线 { //对每一条扫描线与边的交点的右侧像素循环 for(int m=Round(x);mMaxX;m++) //MaxX为包围盒的右边界 { if(FClr==pDC-GetPixel(m,Round(y))) pDC-SetPixelV(m,Round(y),BClr); else pDC-SetPixelV(m,Round(y),FClr); } x+=k; } } };4.4 区域填充算法;4.4.3 四连通域与八连通域 ; ;2.算法原理;四邻接点填充算法;void CTestView::FillPolygon(CDC *pDC)//填充多边形 { COLORREF BoundaryClr=RGB(0,0,0);//边界色 COLORREF PixelClr;//当前像素的颜色 pHead=new CStackNode;//建立栈头结点 pHead-next=NULL;//栈的头结点总是为空 Push(Seed); //种子像素入栈 while(NULL!=pHead-next)//如果栈不