贵州大学--实验三-多边形填充算法.doc

《贵州大学--实验三-多边形填充算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、贵州大学实验报告学院：计算机科学与信息专业：软件工程班级：102班姓名学号实验组实验时间指导教师成绩实验项目名称实验三多边形填充算法实验目的掌握光栅显示系统中多边形的扫描线和种子填充算法。掌握4连通与8连通区域的扩展性。熟悉实验原理，编写测试代码进行实验。实验要求根据本实验的特点、要求和具体条件，熟练掌握多边形填充算法中的扫描线算法和种子填充算法，编写测试代码进行实验，熟悉相应的原理和要求。实验原理一、扫描线算法利用相邻像素之间的连贯性，提高算法效率。根据多边形内部点的连续性知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的内部点

2、。所以，对所有的扫描线填充入点到出点之间所有的点就可填充多边形。处理对象：非自交多边形（边与边之间除了顶点外无其它交点）判断扫描线上的点是否在多边形之内,根据多边形区域连续性，分为3个步骤：–求出扫描线与多边形所有边的交点；–把这些交点的x坐标值以升序排列；–对每一对交点间的区域进行填充。–第三个步骤是从奇数个交点出发到偶数个交点。如图，对y＝8的扫描线排序x坐标得到的表是(2,4,9,13)，然后对交点2与4之间、9与13之间的所有象素点进行填充。几点规则：边界上的象素填充所遵循的规则为:“左闭右开”，“下闭上开”(将左边界和下边界的点算为内

3、部，而将右边界和上边界算为外部)顶点：“上开下闭”。几种特殊情况：1．扫描线交于一顶点，共享的两条边分另处于扫描线的两边，这时交点只取一个。2.共享交点的两条边处于扫描线的上方，这时交点取二个。3．共享交点的两条边处于扫描线的下方，这时交点取0个。4．水平边在算法中不起任何作用，可不考虑。活性边表(提高效率)：为了减少求交的计算量，要利用一条边与相继的两条扫描线的交点的连贯性。在处理一条扫描线时只对活性边（与它相交的多边形的边）进行求交运算。把交点按x增加方向存在一个链表（活性边表）中。活性边：与当前扫描线相交的边。活性边表（AEL）：按交点x

4、的增量顺序存放在一个链表中，该链表称作活性边表（AEL）。一、种子填充算法种子填充首先假定区域由封闭轮廓线围成，且轮廓线内某点是已知的，然后开始搜索与种子点相邻且位于轮廓线内的点。如果这相邻点不在轮廓线内，则已达到轮廓线的边界；如果相邻点在轮廓线之内，则这相邻点成为新的种子点，继续搜索下去。只适用于光栅扫描设备。区域分类（区域采用边界定义，即区域边界上与边界外的象素取相同值，区域内部的点取不同值）1、四向连通区域：各象素在水平垂直四个方向是边通的。即从区域内任一点出发，可水平／垂直移动到达区域内任一点。1、八向连通区域：各象素在水平、垂直、及四

5、个对角线方向都是是边通的。即从区域内任一点出发，可水平、垂直、及四个对角线方向移动到达区域内任一点。扫描线种子算法的测试对象为象素段,对区域内的每一象素段,只保留其最右边(或左边)的象素作为种子象素.区域填充(扫描线算法)：目标：减少递归层次适用于内点表示的4连通区域基本过程：当给定种子点时，首先填充种子点所在的扫描线上的位于给定区域的一个区段，然后确定与这一区段相通的上下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。算法步骤：1、填充并确定种子区段；2、初始化：将种子区段压入堆栈；3、出栈：如果堆栈为空，则算法

6、结束；否则取栈顶元素y,xLeft,xRight），以纵坐标为y的扫描线为当前扫描线，[xLeft,xRight]为搜索区间；4、填充并确定新的区段。实验环境硬件平台：PC机软件：WindowsXP平台，eclipse编程语言：java实验步骤1.掌握多边形填充算法的基本原理；2.依据填充算法，在eclipse下编写源程序并进行调试；3.对运行过程中的错误进行修改；4.对运行结果进行分析与总结；5.书写实验报告。实验内容扫描线算法的核心代码如下所示：publicvoidlineFill(Graphicsg){for(inti=ymin;i<=y

7、max;i++){//循环扫描线Listpointlist=newArrayList();//每条线的交点集合,存放横坐标for(MyLinelb:linelist){//增强的for循环求直线与多边形的交点if((i>=lb.getY1()&&i

8、

9、(i=lb.getY2())){floatx=lb.getX1()+1/lb.getK()*(i-lb.getY1());//求出交点横坐标intxInt=(int)x;pointlist.add(xInt)

10、;}}Collections.sort(pointlist);//对交点进行排序for(intj=0;j