13. 设五边形的五个顶点坐标为(10, 10)，(15, 5)，(12, 5)，(8, 2)和(4, 5)，利用多边形区域填充算法，编一程序生成一个实心图。 解：假设以上五个顶点依次对应编号A-B-C-D-E，首先计算得到ET表： 6-10 5 4 3 2 1 该多边形的AET指针的内容为： 1 AET为空 2 3 4 1 2 3 4 5 6 7 8 9 10 01234567891011121314 1516
5 6 7 8 9 10 具体编程实现如下： 第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
实验题目：实验二有效边表填充算法 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.算法设计： （1）建立AET和BUCKET类； （2）初始化桶，并在建立桶结点时为其表示的扫描线初始化为带头结点的链表； （3）对每个桶结点进行循环，将桶内每个结点的边表合并为有效边表，并进行有效边表循环； （4）按照扫描线从小到大的移动顺序，计算当前扫描线与多边形各边的交点，然后把这些交点按X值递增的顺序进行排序，配对，以确定填充区间； （5）用指定颜色点亮填充区间内的所有像素，即完成填充工作。 4.源程序： 1)//AET.h class AET { public: AET(); virtual ~AET(); double x; int yMax; double k;//代替1/k AET *next; }; //AET..cpp AET::AET() {
} AET::~AET() { } 2) //Bucket.h #include "AET.h" class Bucket { public: Bucket(); virtual ~Bucket(); int ScanLine; AET *p;//桶上的边表指针 Bucket *next; }; // Bucket.cpp Bucket::Bucket() { } Bucket::~Bucket() { } 3)//TestView.h #include "AET.h"//包含有效边表类 #include "Bucket.h"//包含桶类 #define Number 7//N为闭合多边形顶点数，顶点存放在整型二维数组Point[N]中class CTestView : public CView { 。。。。。。。。。 public: void PolygonFill();//上闭下开填充多边形 void CreatBucket();//建立桶结点桶 void Et();//构造边表 void AddEdge(AET *);//将边插入AET表 void EdgeOrder();//对AET表进行排序
研究方法 因农产品流通研究涉及环节众多、需要从多角度、多方位着手、综合探究, 单凭某一种理论视角无法洞察所有,所以本文采用了多学科相交叉的方法、应用了新制度经济学、现代产业经济学等学科理论、并结合图形和案例等工具对农产品流通模式进行了系统的研究。具体方法如下: (1 )文献研究法 主要体现在该文的文献综述部分,通过对先辈研究成果的大量阅读、整理、 归纳,了解了迄今为止有关的研究范围、研究角度、研究方法、研究成果以及未覆盖的研究方面和未深化的研究分支,以上都对本篇论文的研究内容起了指导作用。 (2 )逻辑推演法 本文是以“依据现实背景和文献查阅基础上提出命题一对中国农产品流通 模式的现状分析和与国外模式的比较下找出问题所在--引进相关理论创新农 产品流通模式--提出有效政策建议”的逻辑结构框架展开的研究,符合命题的 内在逻辑关系。 (3 )规范分析与实证分析相结合 本文解释了农产品价格上涨的一个重要原因--流通成本过高;阐述了我国 现有农产品流通模式对生产者(农民)和消费者(市民)造成的影响;分析了 影响农产品流通成本的制度因素和市场因素。以上结合相应的统计数据和分析工具都回答了经济学中“是什么”的问题,也正是实证分析的体现。除此之外, 本文还致力于创新一个适用中国的农产品流通的新模式并最后给出相应的政 策建议,这也是回答了经济学中“应该是什么”的问题一正是规范分析的所在。
5 (4)定性分析和定量分析相结合 文章在探索创新农产品流通新模式的过程中,不仅需要有定性分析,包括 从现有模式到创新模式的改进分析、创新模式的可行性分析等,还需要收集大量数据、实例作为论据,对新模式的合理性进行评估的定量分析。 (5)多种学科相交叉的方法 前面己经提到:本文引入了新制度经济学的交易费用理论和现代产业经济 学的SCP范式来分别针对如何降低农产品流通成本和如何构建农产品流通新模式做了研究,并且,本文相关研究也应用到了统计学和计量经济学的方法。因此,各种学科在此再也不能独自发挥功效了。
实验四区域填充算法的实现 一、实验目的和要求： 1、掌握区域填充算法基本知识 2、理解区域的表示和类型，能正确区分四连通和八连通的区域 3、了解区域填充的实现原理，利用Microsoft Visual C++ 6.0（及EasyX_2011版） 实现区域种子填充的递归算法。 二、实验内容： 1、编程完成区域填色 2、利用画线函数，在屏幕上定义一个封闭区域。 3、利用以下两种种子填充算法，填充上述步骤中定义的区域 (1)边界表示的四连通区域种子填充的实现 (2)内点表示的四连通区域种子填充的实现 4、将上述算法作部分改动应用于八连通区域，构成八连通区域种子填充算法， 并编程实现。 三、实验结果分析 1、以上各种算法相应代码及运行结果如下： 程序代码： #include
计算机图形学课程设计设计题目改进的有效边表算法对多边形的填充学院名称信息科学与技术学院 专业名称计算机科学与技术 学生姓名刘柯 学生学号201213030112 任课教师梅占勇 设计（论文）成绩 教务处制 2015年9 月28 日
目录 一、设计内容与要求 (3) 1.1设计题目 (3) 1.2 设计内容 (3) 1.3 设计目标 (3) 二、总体设计 (3) 2.1 多边形的表示 (3) 2.2 x-扫描线算法 (4) 2.3 改进的有效边表算法 (4) 2.3.1 改进的有效边表算法 (4) 2.3.2 有效边表 (5) 2.3.3 边表 (6) 三、详细设计 (8) 3.1 改进的有效边表算法的实现 (8) 3.2 有效边表算法程序流程图 (9) 四、测试结果 (9) 五、总结 (15) 六、源代码 (15) 参考文献 (26)
一、设计内容与要求 1.1设计题目 用改进的有效边表算法实现多边形的填充 1.2 设计内容 使用OpenGL实现用改进的有效边表算法填充多边形 1.3 设计目标 参照课本上改进的有效边表算法的思想，实现该算法的C语言代码，并用该算法搭配OpenGL以像素点的方式绘制出给定顶点坐标的多边形。 二、总体设计 2.1 多边形的表示 在计算机图形学中，多边形有2种重要的表示方法：顶点表示和点阵表示。 顶点表示用多边形的顶点序列来刻画多边形，这种方法直观、几何意义强，占用内存少，应用普遍，但它没有明确指出哪些像素在多边形内，故不能直接用于面着色。 点阵表示用位于多边形内的像素的集合来刻画多边形。这种表示法虽然失去了许多重要的几何信息，但便于运用帧缓存表示图形，是面着色所需要的图形表示形式。 大多数图形应用系统采用顶点序列表示多边形，而顶点表示又不能直接用于显示，那么就必须有从多边形的顶点表示到点阵表示的转换，这种转换称为多边形的扫描转
太原工业学院
实验拓展：绘制颜色渐变的三角形和四边形。 void CTriangle::Draw(CDC* pDC)//画出来一个三角形 { pDC->MoveTo(point0.x,point0.y); pDC->LineTo(point1.x,point1.y); pDC->LineTo(point2.x,point2.y); pDC->LineTo(point0.x,point0.y); } void CTriangle::GouraudShader(CDC* pDC) { SortVertex();//point0点为y坐标最小的点,point1点为y坐标最大的点,point2点的y坐标位于二者之间。如果y值相同，取x最小的点//定义三角形覆盖的扫描线条数 int nTotalScanLine = point1.y - point0.y + 1; //定义span的起点与终点数组 SpanLeft = new CPoint2[nTotalScanLine];//跨度左边数组 SpanRight = new CPoint2[nTotalScanLine];//跨度右边数组 //判断三角形与P0P1边的位置关系，0-1-2为右手系 int nDeltz = (point1.x - point0.x) * (point2.y - point1.y) - (point1.y - point0.y) * (point2.x - point1.x);//点矢量叉积的z坐标 if(nDeltz > 0)//三角形位于P0P1边的左侧 { nIndex = 0; DDA(point0, point2, TRUE); DDA(point2, point1, TRUE); nIndex = 0; DDA(point0, point1, FALSE); }
研究方法及步骤 【摘要】本文从科学研究的思维方式入手，介绍了研究的路径、研究的分析方法，以及研究的设计与步骤。作者强调论文写作应该反映研究过程，遵循科学的分析方法和步骤。作者对论文写作中涉及的主要方法与步骤进行了介绍和分析，特别是针对传统的研究思维模式进行了反思，剖析了研究生论文写作中的问题，为研究生的论文写作勾画出了一个研究过程的框架。 【关键字】研究方法研究步骤定量分析定性分析论文写作步骤 ThesisWriting:ResearchMethodologiesandProcedures JianWang ProfessorofInternationalbusiness UniversityofInternationalBusinessandEconomics(UIBE) ABSTRACT:Thispaperbeginswithscientificresearchcycleconcept,introd ucesresearchapproaches,analysismethods,researchdesignandprocedures.Th eauthoremphasizestheimportanceofmethodologiesandprocedures,whichshoul https://www.doczj.com/doc/058786702.html,paredwithnormalscientificresear chmethodologiesandprocedures,theauthorrethinkstheChinesetraditionalis sue-orientedresearchapproachbypointingoutitsambiguityandignoranceofme thodologiesandprocedures.Thepapercanprovideaguidanceandframeworkforgr aduatestudentsdoingresearchwhilecompletingtheirthesiswritings. KEYWORDS:researchmethodology,researchprocedures,quantitativemetho ds,qualitativemethods,thesiswritingprocedures 论文写作中的研究方法与研究步骤 一、研究的循环思维方式 二、研究的路径 三、研究的分析方法 四、研究过程的设计与步骤 五、对传统研究思维模式的再思考 在我们指导研究生写论文的过程中，甚至于我们自己从事课题研究时，不禁让我们思考一系列有关研究的基本问题。例如，我们为什么要写论文？我们为什么要做研究？在我们探讨论文写作的过程中，我们是为了完成论文本身的写作，还是完成一个研究过程？写论文与做研究之间有什么联系与区别？如果论文写作应该反映一个研究过程，那么研究过程应该是什么样的？我们用什么样的方法进行研究？我们发现这些问题的解决，对指导研究生的论文写作有非常大的帮助。因此，本文就以我个人在从事教学课题研究和指导研究生完成论文中总结的一些有关研究方法与研究步骤的问题与大家交流共享。欢迎大家参与讨论。 一、研究的循环思维方式 世界上无论哪个领域都存在许多未知的事物，也存在着许多未知的规律。我们研究者的主要任务就是要不断地从大量的事实中总结规律，将之上升到可以指导实践的理论。然而理论也并不是绝对的真理，它也要在实践中不断地被修正，因此，就会有人对理论的前提和内容进行质疑，并提出新的猜想和新的思维。新的猜想和新的思维又要在实践中进行验证，从而发展和完善理论体系。我们探求未知事物及其规律就需要有研究的过程。这个过程，我们称之为研究的循环思维方式（ResearchCycle）。用概念模型来表述就是[1]： Facts—Theory—Speculation
华北水利水电大学 计算机图形学 实验报告 2017--2018学年 第一学期 2014级 计算机科学与技术 专业 指导老师 曹源昊 班级 2014157 学号 201415717 姓名 李卫朋 实验四、画圆与凸多边形填充算法 1. 实验目的 练习对Bezier 曲线的绘制和Bezier 曲线的de Casteljau 算法。 2. 实验内容和要求 按要求完成以下一个作业。提交纸质实验报告，同时提交实验报告和源代码的电子版。 实现Bezier 曲线的de Casteljau 递推算法，能够对任意介于0和1之间的参数t 计算Bezier 曲线上的点，然后把Bezier 曲线绘制成首尾相连的直线段。 要求： (1). 对[0,1]参数区间进行100等分。 (2). 控制点的数目至少为5个，即Bezier 曲线的次数不低于4次。 (3). 同时绘制控制多边形。 (4). 至少绘制两条Bezier 曲线，具有不同的次数，颜色和曲线宽度。 形如： 3. 算法描述 使用vs2012编译环境，使用OpenGL 进行绘图操作。 4. 源程序代码 // 实验4.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include
课程设计报告 课程名称计算机图形学 课题名称多边形裁剪与填充 专业计算机科学与技术 班级计算机0902 学号 姓名 指导教师刘长松曹燚 2012年10 月9 日
湖南工程学院 课程设计任务书 课程名称计算机图形学课题多边形裁剪与填充 专业班级计算机0902 学生姓名 学号 指导老师刘长松曹燚 审批 任务书下达日期2012年9月15 日 任务完成日期2012 年10月9 日
一、设计内容与设计要求 1．设计内容： 交互式地实现多边形的裁剪和填充。。 2．设计要求： 1）窗口功能设计。 2）实现鼠标画多边形与数据存储功能。 3）实现鼠标剪裁窗口选择功能。 4）实现多边形裁剪和填充功能。 3.算法提示： 多边形裁剪算法分析： 基本思想是一次用窗口的一条边裁剪多边形，窗口的一条边以及延长线构成裁剪线，该线把平面分成两个部分：可见一侧，不可见一侧。用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入点。 对于每一条裁剪边，只是判断点在窗口的哪一测以及求线段与裁剪边的交点算法应随之改变。 多边形填充算法分析： 确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin 和ymax），从y=ymin 到 y=ymax, 每次用一条扫描进行填充。对一条扫描线填充的过程可分为四个步骤: a.求交b.排序c.交点配对d.区间填色。 二、进度安排 第 3 周星期一8：00——12：00 星期二8：00——12：00 星期三8：00——12：00 星期四8：00——12：00 星期五8：00——12：00 第 4 周星期一8：00——12：00 附： 课程设计报告装订顺序：封面、任务书、目录、正文、附件（A4大小的图纸及程序清单）、评分。正文的格式：一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。 正文的内容：一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释）。 正文总字数要求在5000字以上（不含程序原代码）。
实验二2-2 一、实验题目 给定四个点绘制图4-44所示的不同转角的两个正方形，使用有效边表算法进行填充，填充效果如图4-45所示，注意采用“左闭右开”和“上闭下开”的原则，使得每个正方形的右边界和下边界没有填充。 二、实验思想 有效边表填充算法通过维护边表和有效边表，避开了扫描线与多边形所有边求交的复杂运算。填充原理是按照扫描线从小到大的移动顺序，计算当前扫描线与有效边的交点，然后把这些交点按x值递增的顺序进行排序、配对，以确定填充区间，最后用指定颜色填充区间内的所有像素，即完成填充工作。 三、实验代码 void CTestView::GetMaxX()//获得屏幕宽度 { CRect Rect; GetClientRect(&Rect); MaxX=Rect.right; } void CTestView::GetMaxY()//获得屏幕高度 { CRect Rect; GetClientRect(&Rect); MaxY=Rect.bottom; } void CTestView::ReadPoint()//读入点表函数 { //设置第一个正方形的4个顶点 int a=160; P1[0]=CP2(MaxX/4-a,MaxY/2+a);//P0 P1[1]=CP2(MaxX/4+a,MaxY/2+a);//P1 P1[2]=CP2(MaxX/4+a,MaxY/2-a);//P2 P1[3]=CP2(MaxX/4-a,MaxY/2-a);//P3 //设置第二个正方形的4个顶点
int b=ROUND(sqrt(2)*a); P2[0]=CP2(3*MaxX/4,MaxY/2+b);//P0 P2[1]=CP2(3*MaxX/4+b,MaxY/2);//P1 P2[2]=CP2(3*MaxX/4,MaxY/2-b);//P2 P2[3]=CP2(3*MaxX/4-b,MaxY/2);//P3 } void CTestView::DrawRect(CDC *pDC,CP2 *P)//绘制正方形函数{ CP2 T; CLine line; for(int i=0;i<4;i++)//边循环 { if(i==0) { line.MoveTo(pDC,P[i]); T=P[0]; } else { line.LineTo(pDC,P[i]);; } } line.LineTo(pDC,T);//闭合 } void CTestView::OnMENUIFill() { // TODO: Add your command handler code here COLORREF FColor; CColorDialog ccd(RGB(255,0,0)); if(ccd.DoModal()==IDOK)//调用调色板选取色 { FColor=ccd.GetColor(); m_Red=GetRValue(FColor);//获得颜色的红色分量
实验报告 一、实验目的 1、掌握有序边表算法填充多边形区域； 2、理解多边形填充算法的意义； 3、增强C语言编程能力。 二、算法原理介绍 根据多边形内部点的连续性知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的内部点。所以，对所有的扫描线填充入点到出点之间所有的点就可填充多边形。 判断扫描线上的点是否在多边形之内，对于一条扫描线，多边形的扫描转换过程可以分为四个步骤： （1）求交：计算扫描线与多边形各边的交点； （2）排序：把所有交点按x值递增顺序排序； （3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间; （4）着色：把相交区间内的象素置成多边形颜色，把相交区间外的象素置成背景色。 p1,p3,p4,p5属于局部极值点，要把他们两次存入交点表中。如扫描线y=7上的交点中，有交点(2,7,13)，按常规方法填充不正确，而要把顶点(7,7)两次存入交点表中(2,7,7,13)。p2，p6为非极值点，则不用如上处理。
为了提高效率，在处理一条扫描线时，仅对与它相交的多边形的边进行求交运算。把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中，称此链表为活性边表(AET)。 对每一条扫描线都建立一个与它相交的多边形的活性边表（AET）。每个AET的一个节点代表一条活性边，它包含三项内容 1.x -当前扫描线与这条边交点的x坐标； 2.Δx -该边与当前扫描线交点到下一条扫描线交点的x增量； 3.ymax -该边最高顶点相交的扫描线号。 每条扫描线的活性边表中的活性边节点按照各活性边与扫描线交点的x值递增排序连接在一起。 当扫描线y移动到下一条扫描线y = y+1时，活性边表需要更新，即删去不与新扫描线相交的多边形边，同时增加与新扫描线相交的多边形边，并根据增量法重新计算扫描线与各边的交点x。 当多边形新边表ET构成后，按下列步骤进行： ①对每一条扫描线i，初始化ET表的表头指针ET[i]； ②将ymax = i的边放入ET[i]中； ③使y =多边形最低的扫描线号； ④初始化活性边表AET为空； ⑤循环，直到AET和ET为空。 ●将新边表ET中对应y值的新边节点插入到AET表。 ●遍历AET表，将两两配对的交点之间填充给定颜色值。 ●遍历AET表，将 ymax= y的边节点从AET表中删除，并将ymax> y的各边节点 的x值递增Δx；并重新排序。 ●y增加1。 三、程序源代码 #include "graphics.h" #define WINDOW_HEIGHT 480 #define NULL 0 #include "alloc.h" #include "stdio.h" #include "dos.h" #include "conio.h" typedef struct tEdge /*typedef是将结构定义成数据类型*/ { int ymax; /* 边所交的最高扫描线号 */
计算机图形学实验报告 班级： 学号：
姓名：
实验三多边形填充 一实验目的 1)掌握多边形的有效边表填充算法； 2)掌握边界像素处理原则； 3)掌握菱形图形的填充方法。 二实验要求 1)设计实现多边形填充类，可以设置顶点序列，调用填充函 数。 2)多边形填充采用有效边表填充算法进行实现，通过建立多 边形的桶表和边表数据，按照算法步骤依次扫描填充；3)调用设计实现的多边形填充类，对菱形线框进行颜色填充。三实验步骤 第1步:创建MFC应用程序框架 参照第一章的步骤建立空的MFC应用程序框架。 第2步:设计实现直线绘制类 设计实现多边形填充类 1）有效边表填充算法原理 在多边形填充过程中，常采用：“下闭上开”和“左闭右开”的原则对边界像素进行处理。有效边表填充算法通过维护“桶表和边表”数据，节省了有效数据存储空间，避免了扫描线与多
边形所有边求交的运算耗时。 图1 边表结点数据结构 有效边表填充算法实现步骤为： a）根据多边形的顶点序列，建立其“桶表和边表”数据。b）按照扫描线从小到大的移动顺序，取出当前扫描线对应桶的边表数据。 c）如果“桶表”数据已经取完，则填充结束；否则，继续后续填充操作。 d）将当前桶里的边表数据加入到有效边表，根据“下闭上开”的原则，删除已经到y max的无效边。 e）对当前扫描线的有效边表按x值递增的顺序进行排序、配对，以确定填充区间；根据“左闭右开”的原则，对两两配对的填充空间进行像素填充。 f）继续回到步骤b。 1）新建多边形填充类CFillPoly头文件
首先声明二维点类“CP2”、边表类“CAET”和桶表类“CBucket”，用于存储和传递多边形“桶表和边表”数据。多边形填充类中主要包括存放多边形顶点数据、有效边表结点指针和桶表结点指针的成员变量，以及创建桶表、边表、有效边表排序和填充多边形等成员函数。“FillPoly.h”头文件中具体类型声明代码如下： #pragma once class CP2 { public: CP2 (); virtual~CP2 (); CP2 (double,int);
实验三多边形的有效边表填充算法 一、实验目的与要求 1、理解多边形的扫描转换原理、方法； 2、掌握有效边表填充算法； 3、掌握链表的建立、添加结点、删除节点的基本方法； 3、掌握基于链表的排序操作。 二、实验内容 在实验二所实现工程的基础上，实现以下内容并把实现函数封装在类 CMyGL 中。 1、C++实现有效边表算法进行多边形扫描转换 2、利用1进行多边形扫描转换和区域填充的实现； 三、实验原理 请同学们根据教材及上课的PPT独立完成。 四、实验步骤（程序实现）。 1、建立并选择工程项目。打开VC6.0->菜单File 的New 项,在projects 属性页选择MFC AppWizard(exe)项，在Project name 中输入一个工程名,如“Sample”。单文档。 2、新建一个图形类。选择菜单Insert New class，Class type 选择“Generic Class”，Name 输入类名，如“CMyCG。 3、向新建的图形类中添加成员函数（实际就是加入实验要求实现的图形生成算法的实现代码）。在工作区中直接鼠标右键单击，选择“Add Member Function…”项，添加绘制圆的成员函数。 void PolygonFill(int number, CPoint *p, COLORREF color, CDC* pDC) 添加其他成员函数： CreatBucket(); CreatET(); AddEdge(); EdgeOrder(); 4、成员函数的实现。实现有效边表填充算法。这一部分需要同学们去实现。 参考实现： 多边形的有效边表填充算法的基本过程为： 1、定义多边形： 2、初始化桶 3、建立边表 4、多边形填充 1)对每一条扫描线，将该扫描线上的边结点插入到临时AET表中，HeadE. 2)对临时AET表排序，按照x递增的顺序存放。 3)根据AET表中边表结点的ymax抛弃扫描完的边结点，即ymax>=scanline 4)扫描AET表，填充扫描线和多边形相交的区间。
private void scanLineFillingToolStripMenuItem_Click(object sender, EventArgs e) { slf.ScanLinePolygonFill(P,g,XiangSu); } private void label2_Click(object sender, EventArgs e) { } private void四联通填充ToolStripMenuItem_Click(object sender, EventArgs e) { tempp.X = tempP[3].X + XiangSu;//选取第4个点内侧（随机猜测） tempp.Y = tempP[3].Y + XiangSu; checkBox.Enabled = false;//让绘制过程中不能改变选择 do_check();//也要检查一遍，不然会出现错误 FloodSeedFill(tempp); checkBox.Enabled = true;//恢复 } ///
实验二有效边表填充算法 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.算法设计： 4.源程序： 1）//AET.h和AET..cpp class AET { } 2）//Bucket.h和Bucket.cpp class Bucket { } 3) // TestView.h #include "AET.h"//包含有效边表类 #include "Bucket.h"//包含桶类 #define Number 7//N为闭合多边形顶点数，顶点存放在整型二维数组Point[N]中class CTestView : public CView { 。。。。。。。。。 public: void PolygonFill();//上闭下开填充多边形 void CreatBucket();//建立桶结点桶 void Et();//构造边表 void AddEdge(AET *);//将边插入AET表 void EdgeOrder();//对AET表进行排序
多边形的偏移填充算法 多边形偏移（polygon offset）算法可能我们印象不深，不过用过autoCAD的同学也印象autoCAD 上面也还是有这个功能的。我们可以用autoCAD上的“正多边形”功能画一个多边形，然后用修改工具中“偏移”按钮，对多边形进行偏移，见图1，从外面的一个大的5边形按照边偏移至里面小的5边形，其中相应边偏移的距离定义为offset值。 图1 AutoCAD中的多边形偏移效果图 当然，这只是简单的情况，复杂的情况可能是有多个多边形，其中1个outer多边形，多个inner 多边形，然后offset的时候应该是outer多边形向内offset，inner多边形向外offset。当一个多边形（特别是凹多边形）初步offset时，可能会发生自交；然后多边形之间也可能会发生相交。大概思路：这里就需要首先将自交的多边形分裂出来，并选择正确的多边形；然后将选择出来的多边形进行求交计算，再一次将有相交的多边形合并分裂出来，并且选择正确的多边形，这个时候得到的全部多边形就是一次offset出来的结果。 1、为了保证outer多边形能向内offset，inner多边形能向外offset，这里需要保证outer多边形是逆时针方向旋转的，inner多边形是顺时针方向旋转的。 1.1 这里就稍稍讲下多边形的顺逆判断。
在多边形是简单多边形的前提下，其实还是挺简单的，只要找出多边形左下角的一个顶点，然后判断与这个顶点相连的两条边的叉积是否大于0就行了；如果多边形不是简单多边形，比如有自相交，有顶点夹角为0的情况等等，这个时候多边形就不应该有顺逆这种属性吧 2、对单个多边形，根据角平分线初步偏移得到角点 对于一个角点，可以设这个顶点为curPoint，相连的前一个点为prePoint，下一个点为nexPoint，于是可以得到两个向量a = prePoint – curPoint，b=nexPoint – curPoint。将向量a和b设置为单位向量之后，相加就能得到角平分线的方向向量c。然后对单位向量a和b做点乘和叉乘，就能得到这个角度的cos和sin值了，我们假设这个角度的一般为Θ，则cos=cos2Θ，sin=sin2Θ。根据三角函数，就能得到sinΘ值，之后将就能得到该顶点的角平分线方向的偏移向量d=c/|c|×offset÷sinΘ。 3、考虑到有些边在偏移的过程中会消失，即一些边有退化的offset值，见图3。如果初步偏移的值大于它的退化offset值，则该边就会反向出现，见图3中的边【4,5】，会给后面的程序带来很大的麻烦。 图2
多边形有效边表填充算法案例效果如下： 具体实现： （1）新建MFC项目： （2）分别添加类：AET 和Bucket
在AET.h 中定义#pragma once class AET { public: AET(void); ~AET(void); double x; int yMax; double k; AET * next; }; 在Bucket.h中定义#pragma once #include"AET.h" class Bucket {
public: Bucket(void); ~Bucket(void); int Scanline; AET *p; Bucket * next; }; （3）定义菜单 （4）添加菜单处理程序 （5）定义视图头文件 // scanfillView.h : CscanfillView 类的接口// #pragma once #include"AET.h" #include"Bucket.h" # define Number 7 class CscanfillView : public CView {
protected: // 仅从序列化创建 CscanfillView(); DECLARE_DYNCREATE(CscanfillView) // 属性 public: CscanfillDoc* GetDocument() const; // 操作 public: void PolygonFill(); //上闭下开填充多边形 void CreatBucket(); //建立桶节点 void Et(); //构造边表 void AddEdge(AET *); //将边插入AET表 void EdgeOrder(); //对AET表进行排序 // 重写 public: virtual void OnDraw(CDC* pDC); // 重写以绘制该视图 virtual BOOL PreCreateWindow(CREATESTRUCT& cs); protected: virtual BOOL OnPreparePrinting(CPrintInfo* pInfo); virtual void OnBeginPrinting(CDC* pDC, CPrintInfo* pInfo); virtual void OnEndPrinting(CDC* pDC, CPrintInfo* pInfo); // 实现 public: virtual ~CscanfillView(); #ifdef _DEBUG virtual void AssertValid() const; virtual void Dump(CDumpContext& dc) const; #endif protected: COLORREF GetColor; //调色板 CPoint Point[7]; //定义多边形 Bucket * HeadB,*CurrentB; //桶的头结点和当前节点 AET E[Number],*HeadE,*CurrentE,*T1,*T2; //有效边表的节点 // 生成的消息映射函数 protected: DECLARE_MESSAGE_MAP() public: afx_msg void OnMenuAET(); };
实验二有效边表填充算法 实验题目：有效边表填充算法学号： 姓名：班级： 指导老师：完成日期： 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 class AET { public: AET(); virtual ~AET(); double x; int yMax; double k; //代替1/k AET *next; } 2）//Bucket.h和Bucket.cpp class Bucket
{ public: Bucket(); virtual ~Bucket(); int ScanLine; AET *p;//桶上的边表指针 Bucket *next; } 3) // TestView.h #include "AET.h"//包含有效边表类 #include "Bucket.h"//包含桶类 #define Number 7//N为闭合多边形顶点数，顶点存放在整型二维数组Point[N]中class CTestView : public CView { 。。。。。。。。。 public: void PolygonFill();//上闭下开填充多边形 void CreatBucket();//建立桶结点桶 void Et();//构造边表 void AddEdge(AET *);//将边插入AET表 void EdgeOrder();//对AET表进行排序 。。。。。。。。。。 protected: COLORREF GetColor;//调色板 CPoint Point[7];//定义多边形 Bucket *HeadB,*CurrentB;//桶的头结点和当前结点 AET E[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 } void CTestView::OnDraw(CDC* pDC) {