有效边表填充算法.docx
- 文档编号:13178324
- 上传时间:2023-06-11
- 格式:DOCX
- 页数:16
- 大小:85.70KB
有效边表填充算法.docx
《有效边表填充算法.docx》由会员分享,可在线阅读,更多相关《有效边表填充算法.docx(16页珍藏版)》请在冰点文库上搜索。
有效边表填充算法
实验二有效边表填充算法
实验题目:
有效边表填充算法学号:
姓名:
班级:
指导老师:
完成日期:
1.实验目的:
设计有效边表结点和边表结点数据结构
设计有效边表填充算法
编程实现有效边表填充算法
2.实验描述:
下图1所示多边形覆盖了12条扫描线,共有7个顶点和7条边。
7个顶点分别为:
P0(7,8),P1(3,12),P2(1,7),P3(3,1),P4(6,5),P5(8,1),P6(12,9)。
在1024×768的显示分辩率下,将多边形顶点放大为P0(500,400),P1(350,600),P2(250,350),P3(350,50),P4(500,250),P5(600,50),P6(800,450)。
图1示例多边形
图2屏幕显示多边形
3.算法设计:
多边形的有效边表填充算法的基本原理是按照扫描线从小到大的移动顺序,计算当前扫描线与多边形各边的交点,然后把这些交点按x值递增的顺序进行排序、配对,以确定填充区间,然后用指定颜色点亮填充区间的所有像素,即完成填充工作。
有效边表填充算法通过访问多边形覆盖区间内的每个像素,可以填充凸、凹多边形和环,已成为目前最为有效的多边形填充算法。
4.源程序:
1)//AET.h和AET..cpp
classAET
{
public:
AET();
virtual~AET();
doublex;
intyMax;
doublek;//代替1/k
AET*next;
}
2)//Bucket.h和Bucket.cpp
classBucket
{
public:
Bucket();
virtual~Bucket();
intScanLine;
AET*p;//桶上的边表指针
Bucket*next;
}
3)//TestView.h
#include"AET.h"//包含有效边表类
#include"Bucket.h"//包含桶类
#defineNumber7//N为闭合多边形顶点数,顶点存放在整型二维数组Point[N]中
classCTestView:
publicCView
{
。
。
。
。
。
。
。
。
。
public:
voidPolygonFill();//上闭下开填充多边形
voidCreatBucket();//建立桶结点桶
voidEt();//构造边表
voidAddEdge(AET*);//将边插入AET表
voidEdgeOrder();//对AET表进行排序
。
。
。
。
。
。
。
。
。
。
protected:
COLORREFGetColor;//调色板
CPointPoint[7];//定义多边形
Bucket*HeadB,*CurrentB;//桶的头结点和当前结点
AETE[Number],*HeadE,*CurrentE,*T1,*T2;//有效边表的结点
4)//TestView.cpp
CTestView:
:
CTestView()
{
//设置多边形的7个顶点
Point[0]=CPoint(550,400);//P0
Point[1]=CPoint(350,600);//P1
Point[2]=CPoint(250,350);//P2
Point[3]=CPoint(350,50);//P3
Point[4]=CPoint(500,250);//P4
Point[5]=CPoint(600,50);//P5
Point[6]=CPoint(800,450);//P6
}
voidCTestView:
:
OnDraw(CDC*pDC)
{
CTestDoc*pDoc=GetDocument();
ASSERT_VALID(pDoc);
pDC->Polygon(Point,7);//绘制多边形
//输出多边形的顶点编号
pDC->TextOut(550,410,"P0");
pDC->TextOut(350,600,"P1");
pDC->TextOut(230,340,"P2");
pDC->TextOut(350,30,"P3");
pDC->TextOut(490,220,"P4");
pDC->TextOut(600,30,"P5");
pDC->TextOut(805,450,"P6");
}
voidCTestView:
:
OnMenuAET()//菜单函数
{
AfxGetMainWnd()->SetWindowText("多边形有效边表填充算法");//显示标题
CColorDialogccd(GetColor);
if(ccd.DoModal()==IDOK)//调用调色板选取前景色
{
GetColor=ccd.GetColor();
}
RedrawWindow();//刷新屏幕
CreatBucket();//初始化桶
Et();//建立边表
PolygonFill();//多边形填充
}
voidCTestView:
:
CreatBucket()//初始化桶
{
intScanMin,ScanMax;//确定扫描线的最小值和最大值
ScanMax=ScanMin=Point[0].y;
for(inti=1;i { if(Point[i].y { ScanMin=Point[i].y;//扫描线的最小值 } if(Point[i].y>ScanMax) { ScanMax=Point[i].y;//扫描线的最大值 } } for(i=ScanMin;i<=ScanMax;i++)//建立桶结点 { if(ScanMin==i)//桶头结点 { HeadB=newBucket;//建立桶的头结点 CurrentB=HeadB;//CurrentB为Bucket当前结点指针 CurrentB->ScanLine=ScanMin; CurrentB->p=NULL;//没有连接边链表 CurrentB->next=NULL; } else//建立桶的其它结点 { CurrentB->next=newBucket;//新建一个桶结点 CurrentB=CurrentB->next;//使CurrentB指向新建的桶结点 CurrentB->ScanLine=i; CurrentB->p=NULL;//没有连接边链表 CurrentB->next=NULL; } } } voidCTestView: : Et()//构造边表 { for(inti=0;i { CurrentB=HeadB;//从桶链表的头结点开始循环 intj=i+1;//边的第二个顶点,Point[i]和Point[j]构成边 if(j==Number)j=0;//保证多边形的闭合 if(Point[j].y>Point[i].y)//终点比起点高 { while(CurrentB->ScanLine! =Point[i].y)//在桶内寻找该边的yMin { CurrentB=CurrentB->next;//移到下一个桶结点 } E[i].x=Point[i].x;//计算AET表的值 E[i].yMax=Point[j].y; E[i].k=double((Point[j].x-Point[i].x))/(Point[j].y-Point[i].y);//代表1/k E[i].next=NULL; CurrentE=CurrentB->p;//获得桶上链接边表的地址 if(CurrentB->p==NULL)//当前桶结点上没有链接边结点 { CurrentE=&E[i];//赋边的起始地址 CurrentB->p=CurrentE;//第一个边结点直接连接到对应的桶中 } else { while(CurrentE->next! =NULL)//如果当前边已连有边结点 { CurrentE=CurrentE->next;//移动指针到当前边的最后一个边结点 } CurrentE->next=&E[i];//把当前边接上去 } } if(Point[j].y { while(CurrentB->ScanLine! =Point[j].y) { CurrentB=CurrentB->next; } E[i].x=Point[j].x; E[i].yMax=Point[i].y; E[i].k=double((Point[i].x-Point[j].x))/(Point[i].y-Point[j].y); E[i].next=NULL; CurrentE=CurrentB->p; if(CurrentE==NULL) { CurrentE=&E[i]; CurrentB->p=CurrentE; } else { while(CurrentE->next! =NULL) { CurrentE=CurrentE->next; } CurrentE->next=&E[i]; } } } CurrentB=NULL; CurrentE=NULL; } voidCTestView: : AddEdge(AET*NewEdge)//插入临时边表函数 { T1=HeadE; if(T1==NULL)//边表为空,将边表置为TempEdge { T1=NewEdge; HeadE=T1; } else { while(T1->next! =NULL)//边表不为空,将TempEdge连在该边之后 { T1=T1->next; } T1->next=NewEdge; } } voidCTestView: : EdgeOrder()//对边表进行排序函数 { T1=HeadE; if(T1==NULL) { return; } if(T1->next==NULL)//如果该边表没有再连边表 { return;//桶结点只有一条边,不需要排序 } else { if(T1->next->x { T2=T1->next; T1->next=T2->next; T2->next=T1; HeadE=T2; } T2=HeadE; T1=HeadE->next; while(T1->next! =NULL)//继续两两比较相连的边表的x值,进行排序 { if(T1->next->x { T2->next=T1->next; T1->next=T1->next->next; T2->next->next=T1; T2=T2->next; } else { T2=T1; T1=T1->next; } } } } voidCTestView: : PolygonFill()//多边形填充函数 { HeadE=NULL; for(CurrentB=HeadB;CurrentB! =NULL;CurrentB=CurrentB->next)//访问所有桶结点 { for(CurrentE=CurrentB->p;CurrentE! =NULL;CurrentE=CurrentE->next)//访问桶中排序前的边结点 { AET*TempEdge=newAET; TempEdge->x=CurrentE->x; TempEdge->yMax=CurrentE->yMax; TempEdge->k=CurrentE->k; TempEdge->next=NULL; AddEdge(TempEdge);//将该边插入临时Aet表 } EdgeOrder();//使得边表按照x递增的顺序存放 T1=HeadE;//根据ymax抛弃扫描完的边结点 if(T1==NULL) { return; } while(CurrentB->ScanLine>=T1->yMax)//放弃该结点,Aet表指针后移(下闭上开) { T1=T1->next; HeadE=T1; if(HeadE==NULL) { return; } } if(T1->next! =NULL) { T2=T1; T1=T2->next; } while(T1! =NULL) { if(CurrentB->ScanLine>=T1->yMax)//跳过一个结点 { T2->next=T1->next; T1->next=NULL; T1=T2->next; } else { T2=T1; T1=T2->next; } } BOOLIn=false;//设置一个BOOL变量In,初始值为假 doublexb,xe;//扫描线的起点和终点 for(T1=HeadE;T1! =NULL;T1=T1->next)//填充扫描线和多边形相交的区间 { if(In==false) { xb=T1->x; In=true;//每访问一个结点,把In值取反一次 } else//如果In值为真,则填充从当前结点的x值开始到下一结点的x值结束的区间 { xe=T1->x-1;//左闭右开 CClientDCdc(this); for(doublex=xb;x<=xe;x++) dc.SetPixel(ROUND(x),CurrentB->ScanLine,GetColor);//填充语句 Sleep (1);//延时1ms,提高填充过程的可视性 In=FALSE; } } for(T1=HeadE;T1! =NULL;T1=T1->next)//边连贯性 { T1->x=T1->x+T1->k;//x=x+1/k } } deleteHeadB; deleteCurrentB; deleteCurrentE; deleteHeadE; } 5.运行结果: (屏幕截图)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 有效 填充 算法