版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、实验题目:实验二 有效边表填充算法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)
2、。请使用有效边表算法填充该多边形。 图1示例多边形图2 屏幕显示多边形3.算法设计:(1)建立AET和BUCKET类;(2)初始化桶,并在建立桶结点时为其表示的扫描线初始化为带头结点的链表;(3)对每个桶结点进行循环,将桶内每个结点的边表合并为有效边表,并进行有效边表循环;(4)按照扫描线从小到大的移动顺序,计算当前扫描线与多边形各边的交点,然后把这些交点按X值递增的顺序进行排序,配对,以确定填充区间;(5)用指定颜色点亮填充区间内的所有像素,即完成填充工作。4.源程序:1)/AET.hclass AET public:AET();virtual AET();double x;int yMax
3、;double k;/代替1/kAET *next;/AET.cppAET:AET()AET:AET()2) /Bucket.h#include "AET.h"class Bucket public:Bucket();virtual Bucket();int ScanLine;AET *p;/桶上的边表指针Bucket *next;/ Bucket.cppBucket:Bucket()Bucket:Bucket()3)/TestView.h#include "AET.h"/包含有效边表类#include "Bucket.h"/包含桶类
4、#define Number 7/N为闭合多边形顶点数,顶点存放在整型二维数组PointN中class CTestView : public CView。public:void PolygonFill();/上闭下开填充多边形void CreatBucket();/建立桶结点桶void Et();/构造边表void AddEdge(AET *);/将边插入AET表void EdgeOrder();/对AET表进行排序 。protected:COLORREF GetColor;/调色板CPoint Point7;/定义多边形Bucket *HeadB,*CurrentB;/桶的头结点和当前结点A
5、ET ENumber,*HeadE,*CurrentE,*T1,*T2;/有效边表的结点(4) TestView.cpp#define ROUND(a) int(a+0.5) /四舍五入CTestView:CTestView()/设置多边形的7个顶点Point0=CPoint(550,400);/P0Point1=CPoint(350,600);/P1Point2=CPoint(250,350);/P2Point3=CPoint(350,50);/P3Point4=CPoint(500,250);/P4Point5=CPoint(600,50);/P5Point6=CPoint(800,450
6、);/P6void CTestView: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->Text
7、Out(490,220,"P4");pDC->TextOut(600,30,"P5");pDC->TextOut(805,450,"P6"); void CTestView:OnMenuAET() /菜单函数AfxGetMainWnd()->SetWindowText("多边形有效边表填充算法");/显示标题CColorDialog ccd(GetColor);if(ccd.DoModal()=IDOK)/调用调色板选取前景色GetColor=ccd.GetColor();RedrawWindow
8、();/刷新屏幕CreatBucket();/初始化桶Et();/建立边表PolygonFill();/多边形填充void CTestView:CreatBucket()/初始化桶int ScanMin,ScanMax;/确定扫描线的最小值和最大值ScanMax=ScanMin=Point0.y;for(int i=1;i<Number;i+)if(Pointi.y<ScanMin)ScanMin=Pointi.y;/扫描线的最小值if(Pointi.y>ScanMax)ScanMax=Pointi.y;/扫描线的最大值for(i=ScanMin;i<=ScanMax;
9、i+)/建立桶结点if(ScanMin=i)/桶头结点HeadB=new Bucket;/建立桶的头结点CurrentB=HeadB;/CurrentB为Bucket当前结点指针CurrentB->ScanLine=ScanMin;CurrentB->p=NULL;/没有连接边链表CurrentB->next=NULL;else/建立桶的其它结点CurrentB->next=new Bucket;/新建一个桶结点CurrentB=CurrentB->next;/使CurrentB指向新建的桶结点CurrentB->ScanLine=i;CurrentB-&g
10、t;p=NULL;/没有连接边链表CurrentB->next=NULL;void CTestView:Et()/构造边表 for(int i=0;i<Number;i+)/访问每个顶点 CurrentB=HeadB;/从桶链表的头结点开始循环 int j=i+1;/边的第二个顶点,Pointi和Pointj构成边 if(j=Number) j=0;/保证多边形的闭合 if(Pointj.y>Pointi.y) /终点比起点高 while(CurrentB->ScanLine!=Pointi.y)/在桶内寻找该边的yMin CurrentB=CurrentB->n
11、ext;/移到下一个桶结点 Ei.x=Pointi.x;/计算AET表的值 Ei.yMax=Pointj.y; Ei.k=double(Pointj.x-Pointi.x)/(Pointj.y-Pointi.y);/代表1/k Ei.next=NULL; CurrentE=CurrentB->p;/获得桶上链接边表的地址 if(CurrentB->p=NULL)/当前桶结点上没有链接边结点 CurrentE=&Ei;/赋边的起始地址 CurrentB->p=CurrentE;/第一个边结点直接连接到对应的桶中 else while(CurrentE->next!
12、=NULL)/如果当前边已连有边结点 CurrentE=CurrentE->next;/移动指针到当前边的最后一个结点 CurrentE->next=&Ei;/把当前边接上去 /if if(Pointj.y<Pointi.y)/终点比起点低 while(CurrentB->ScanLine!=Pointj.y) CurrentB=CurrentB->next; Ei.x=Pointj.x; Ei.yMax=Pointi.y; Ei.k=double(Pointi.x-Pointj.x)/(Pointi.y-Pointj.y); Ei.next=NULL;
13、CurrentE=CurrentB->p; if(CurrentE=NULL) CurrentE=&Ei; CurrentB->p=CurrentE; else while(CurrentE->next!=NULL) CurrentE=CurrentE->next; CurrentE->next=&Ei; /if /for CurrentB=NULL; CurrentE=NULL; void CTestView:AddEdge(AET *NewEdge)/插入临时边表函数 T1=HeadE; if(T1=NULL)/边表为空,将边表置为TempEd
14、ge T1=NewEdge; HeadE=T1; else while(T1->next!=NULL)/边表不为空,将TempEdge连在该边之后 T1=T1->next; T1->next=NewEdge; void CTestView:EdgeOrder()/对边表进行排序函数 T1=HeadE; if(T1=NULL) return; if(T1->next=NULL)/如果该边表没有再连边表 return;/桶结点只有一条边,不需要排序 else if(T1->next->x<T1->x)/边表按x值排序 T2=T1->next;
15、T1->next=T2->next; T2->next=T1; HeadE=T2; T2=HeadE; T1=HeadE->next; while(T1->next!=NULL)/继续两两比较相连的边表的x 值,进行排序 if(T1->next->x<T1->x) T2->next=T1->next; T1->next=T1->next->next; T2->next->next=T1; T2=T2->next; else T2=T1; T1=T1->next; void CTestVi
16、ew:PolygonFill()/多边形填充函数 HeadE=NULL; for(CurrentB=HeadB;CurrentB!=NULL;CurrentB=CurrentB->next)/访问所有桶结点 for(CurrentE=CurrentB->p;CurrentE!=NULL;CurrentE=CurrentE->next)/桶中所有边结点 AET *TempEdge=new AET; TempEdge->x=CurrentE->x; TempEdge->yMax=CurrentE->yMax; TempEdge->k=CurrentE
17、->k; TempEdge->next=NULL; AddEdge(TempEdge);/将该边插入临时Aet 表 /for 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;
18、 while(T1!=NULL) if(CurrentB->ScanLine>=T1->yMax)/跳过一个结点 T2->next=T1->next; T1->next=NULL; T1=T2->next; else T2=T1; T1=T2->next; BOOL In=false;/设置一个BOOL变量In,初始值为假 double xb,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;/左闭右开 CClientDC
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 初中语文++第13课《唐诗五首》课件+统编版语文八年级上册
- 儿童精准营养师理论考核试题及答案
- 三国至隋唐的文化课件 2024-2025学年高中历史统编版(2019)必修中外历史纲要上
- 广东省汕尾市2023-2024学年高一下学期7月期末考试语文试题(解析版)
- 人力资源管理中的员工忠诚度问题研究
- 股权结构对公司财务稳健性的提升作用研究分析
- unit3(基础作业)2024-2025学年五年级上册 英语 人教版
- 2023年中石油昆仑物流有限公司招聘笔试真题
- 2023年潜江市委巡察办选调工作人员考试试题及答案
- 2023年内江市第六人民医院招聘员额人员笔试真题
- 企业IT运维管理体系-总体规划
- 腰椎间盘突出临床路径
- 瓷砖采购投标方案
- 人教版小学一年级英语课本上册-课件
- 法国中尉的女人PPT
- 灌浆基本理论与乌东德固结灌浆方案教学课件
- 篮球比赛小组赛积分表
- (完整版)血压监测记录表
- 夫妻自愿放弃房产协议书
- 新媒体运营劳动合同范本(5篇)
- 2023年青少年普法知识试题及答案
评论
0/150
提交评论