多边形区域填充算法.docx

13. 设五边形的五个顶点坐标为(10, 10)，(15, 5)，(12, 5)，(8, 2)和(4, 5)，利用多边形区域填充算法，编一程序生成一个实心图。解：假设以上五个顶点依次对应编号A-B-C-D-E，首先计算得到ET表：AEDCBymaxx|ymin 1/k next EA1015-1BA 6-10 5 4DE584/3DC 3 2 1 0用于存放AET活动边表该多边形的AET指针的内容为：1 AET为空DE584/3DCAET2DCDEAET3DEDCAET4DCEAAET5DEBABAEAAET6BAEAAET7EAAETBA8AETBAEA9BAEAAET10具体编程实现如下：第1步：(1) 根据输入的五个顶点坐标找到y值最小的点(例如点D，此时y=2)，并找到与D有边关系的两个顶点(此时为E和C)，在y=2处建立ET边表记录(ymax、xi和m值均可通过顶点坐标间的计算得到，例如DE边的建立，特别注意：当D点和E点y坐标值相同时，也即是DE与x轴平行，该边不能计入ET边表)，之后标记D点被访问过；(2) 排除访问过的点以及和该点相关联的边，重复(1)直至将ET表建立完善。[注]边关系的建立可通过邻接矩阵的数据结构实现，权值可以为该矩阵行编号对应点的y坐标值，ET边表采用邻接表的数据结构第2步：根据ET表构建AET表，并逐行完成多边形填充，具体的C++代码如下：(1) 建立头文件base_class.h，主要是边表结点结构体和ET边表类的实现enum ResultCode{Success, Failure};template class Tstruct Enode{Enode() {next=NULL;}Enode(T pymax, float pxi, float pm, Enode *pnext){ymax=pymax; xi=pxi;m=pm; next=pnext;}T ymax, xi; //ymax表示最大的y值，xi表示最底端点的x坐标值float m; //m表示斜率的倒数Enode *next;}; //定义了ET表和AET表中结点的结构体template class Tclass ET{public:ET(int mSize); ~ET();ResultCode Insert(int u, T ymax, float xi, float m);int n; //覆盖该多边形的扫描线的总数，从0开始计数EnodeT **a;}; //定义了边表类template class TETT::ET(int mSize){n=mSize;a=new EnodeT *[n]; for(int i=0;in;i++) a[i]=0;} //ET边表的初始化template class TETT::~ET(){EnodeT *p, *q;delete a[0]; for(int i=1;in;i++){p=a[i]; q=p;while(p){p=p-next;delete q;q=p;}}delete []a;} //析构函数负责回收内存空间template class TResultCode ETT::Insert(int u, T ymax, float xi, float m){if(u0||un-1) return Failure;EnodeT *p=new EnodeT(ymax, xi, m, a[u]);a[u]=p;return Success;} //依次插入结点构建出边表，其中a[1]到a[10]用于构建ET边表 //a[0]用于构建活动AET边表(2) 填充函数po_fill的实现和主函数的实现#include base_class.h#include graphics.h#include iostream.hvoid po_fill(ETint etp, int ep, int color) //多边形填充函数的实现{ int i=1; //i作为控制变量标识扫描线while(iep-1) {if(etp.a[i]!=NULL){Enodeint *p,*r;p=etp.a[i];r=etp.a[0];while(p){ Enodeint *q=new Enodeint(p-ymax,p-xi,p-m,NULL); if(!etp.a[0]) {etp.a[0]=q; r=q;} else { if(r-xi==q-xi) {q-next=r-next; r-next=q; r=q;} if(r-xiq-xi) {etp.a[0]=q; q-next=r;} else { while(q-xir-xi r-next) r=r-next; if(r-ne