图形学实验报告四 多边形填充算法_第1页
图形学实验报告四 多边形填充算法_第2页
图形学实验报告四 多边形填充算法_第3页
图形学实验报告四 多边形填充算法_第4页
图形学实验报告四 多边形填充算法_第5页
已阅读5页,还剩7页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、贵州大学实验报告学院:计算机科学与信息学院 专业:计算机科学与技术 班级: 101姓名学号实验组4实验时间2013.4.25指导教师吴云成绩实验项目名称多边形填充算法实验目的使学生掌握光栅显示系统中多边形的扫描转换和区域填充算法。掌握4连通区域的扩展性。实验要求实现多边形的扫描转换算法和区域填充算法实验原理扫描线算法算法原理:利用相邻像素之间的连贯性,提高算法效率。根据多边形内部点的连续性知:一条扫描线与多边形的交点中,入点和出点之间所有点都是多边形的内部点。所以,对所有的扫描线填充入点到出点之间所有的点就可填充多边形。1024681012024681234处理对象:非自交多边形(边与边之间除

2、了顶点外无其它交点)判断扫描线上的点是否在多边形之内,根据多边形区域连续性,分为3个步骤: 求出扫描线与多边形所有边的交点; 把这些交点的x坐标值以升序排列; 对每一对交点间的区域进行填充。 第三个步骤是从奇数个交点出发到偶数个交点。如右图,对y8的扫描线排序x坐标得到的表是(2,4,9,13),然后对交点2与4之间、9与13之间的所有象素点进行填充。几点规则:边界上的象素:“左闭右开”,“下闭上开”(将左边界和下边界的点算为内部,而将右边界和上边界算为外部)顶点:“上开下闭”。几种特殊情况:1扫描线交于一顶点,共享的两条边分另处于扫描线的两边,这时交点只取一个,如扫描线y=3,该点被填充一次

3、。2.共享交点的两条边处于扫描线的上方,这时交点取二个,如扫描线y=1,该点被填充一次。3共享交点的两条边处于扫描线的下方,这时交点取0个,如扫描线y=9,无交点,不填充。4水平边在算法中不起任何作用,可不考虑。活性边表(提高效率):为了减少求交的计算量,要利用一条边与相继的两条扫描线的交点的连贯性。在处理一条扫描线时只对活性边(与它相交的多边形的边)进行求交运算。把交点按x增加方向存在一个链表(活性边表)中。活性边:与当前扫描线相交的边。活性边表(AEL):按交点x的增量顺序存放在一个链表中,该链表称作活性边表(AEL)。种子填充算法算法原理种子填充算法首先假定区域由封闭轮廓线围成,且轮廓线

4、内某点是已知的,然后开始搜索与种子点相邻且位于轮廓线内的点。如果这相邻 点不在轮廓线内,则已达到轮廓线的边界;如果相邻点在轮廓线之内,则这相邻点成为新的种子点,继续搜索下去。只适用于光栅扫描设备。区域分类(区域采用边界定义,即区域边界上与边界外的象素取相同值,区域内部的点取不同值)1、四向连通区域:各象素在水平垂直四个方向是边通的。即从区域内任一点出发,可水平垂直移动到达区域内任一点。2、八向连通区域:各象素在水平、垂直、及四个对角线方向都是是边通的。即从区域内任一点出发,可水平、垂直、及四个对角线方向移动到达区域内任一点。扫描线种子算法测试对象为象素段 ,对区域内的每一象素段,只保留其最右边

5、(或左边)的象素作为种子象素.区域填充(扫描线算法):目标:减少递归层次适用于内点表示的4连通区域基本过程:当给定种子点时,首先填充种子点所在的扫描线上的位于给定区域的一个区段,然后确定与这一区段相通的上下两条扫描线上位于给定区域内的区段,并依次保存下来。反复这个过程,直到填充结束。算法步骤:1、填充并确定种子区段;2、初始化:将种子区段压入堆栈;3、出栈:如果堆栈为空,则算法结束;否则取栈顶元素y,xLeft,xRight),以纵坐标为y的扫描线为当前扫描线,xLeft, xRight为搜索区间;4、填充并确定新的区段 。扫描线种子填充: public void FillField(int

6、x, int y, Color newColor, uint oldColor, Graphics g) if ("".Equals(txtx.Text) | "".Equals(txty.Text) return; else x = Convert.ToInt32(txtx.Text); y = Convert.ToInt32(txty.Text); int xl, xr; bool spanNeedFill; myStack.Clear(); int ptx = x; int pty = y; myStack.Push(ptx); myStack.P

7、ush(pty); while (myStack.Count != 0) pty = (int)myStack.Pop(); ptx = (int)myStack.Pop(); x = ptx; y = pty; while (bitmap.GetPixel(g, x, y) = oldColor) bitmap.SetPixel(g, x, y, ColorTranslator.ToWin32(newColor); x+; xr = x - 1; x = ptx - 1; while (bitmap.GetPixel(g, x, y) = oldColor) bitmap.SetPixel(

8、g, x, y, ColorTranslator.ToWin32(newColor); x-; xl = x + 1; x = xl; y = y + 1; while (x <= xr) spanNeedFill = false; while (bitmap.GetPixel(g, x, y) = oldColor) spanNeedFill = true; x+; if (spanNeedFill) ptx = x - 1; pty = y; myStack.Push(ptx); myStack.Push(pty); spanNeedFill = false; while (bitm

9、ap.GetPixel(g, x, y) != oldColor && x <= xr) x+; x = xl; y = y - 2; while (x <= xr) spanNeedFill = false; while (bitmap.GetPixel(g, x, y) = oldColor) spanNeedFill = true; x+; if (spanNeedFill) ptx = x - 1; pty = y; myStack.Push(ptx); myStack.Push(pty); spanNeedFill = false; while (bitm

10、ap.GetPixel(g, x, y) != oldColor && x <= xr) x+; 四连通种子填充: public void BoundaryFill4(int x, int y, uint oldColor, Graphics g) if ("".Equals(txtx.Text) | "".Equals(txty.Text) return; else x = Convert.ToInt32(txtx.Text); y = Convert.ToInt32(txty.Text); if (bitmap.GetPixel

11、(g, x, y) != oldColor && bitmap.GetPixel(g, x, y) = ColorTranslator.ToWin32(Color.Yellow) bitmap.SetPixel(g, x, y, ColorTranslator.ToWin32(Color.Red); BoundaryFill4(x, y + 1, oldColor, g); BoundaryFill4(x - 1, y, oldColor, g); BoundaryFill4(x, y - 1, oldColor, g); BoundaryFill4(x + 1, y, oldColor, g); 实验环境VS2010(C#) 实验步骤1、 添加一个C#下的Windows窗体应用程序,实现对于算法的选择。2、 根据不同算法添加不同窗体,接受圆初始化数据,编写核心函数。代码见实验原理中代码部分。3、 调试运行。实验内容在VS2010环境下利用C#编程实现多边

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论