多边形的扫描转换算法、区域填充算法

贵州大学计算机图形学实验报告学院：计算机科学与信息学院专业：软件工程班级：姓名学号实验组实验时间指导教师成绩实验项目名称实验三多边形的扫描转换算法、区域填充算法实验目的通过本实验，了解并掌握在光栅显示系统中多边形的扫描转换和区域填充算法。实验要求1、用光栅扫描算法画出不自交的图形：2、用光栅扫描算法画出自交图形：3、用区域填充法画出图形：实验原理一、光栅扫描算法：扫描线算法是扫描转换多边形的常用算法，它充分利用了相邻像素之间的连贯性，避免了逐点判断和反复求交计算，达到了减少计算量和提高算法效率的目的。处理对象：非自交多边形（边与边之间除了顶点外无其它交点）。开发和利用相邻象素之间的连贯性是光栅图形学算法的重要技巧。扫描线算法综合利用了区域的连贯性、扫描线的连贯性和边的连贯性等三种形式的连贯性。区域的连贯性：相邻两条扫描线构成一个水平长方形区域，并被多边形的边分割为若干梯形（一类位于多边形的内部；另一类在多边形的外部，且间隔排列）。只需知道该区域内任一梯形中一点关于多边形的内外关系，即可确定区域内所有梯形关于多边形的内外关系。扫描线的连贯性：区域的连贯性在一条扫描线上的反映；边的连贯性：某条边与当前扫描线相交，也可能与下一条扫描线相交。可通过与当前扫描线的交点计算与下一扫描线的交点(利用斜率)。（区域的连贯性在相邻两扫描线上的0246810122468101234反映）根据扫描线的连贯性可知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的内部点。所以，对所有的扫描线填充入点到出点之间的点就可填充多边形。如何具体实现（如何找到入点、出点）？根据区域的连贯性，分为3个步骤：(1)求出扫描线与多边形所有边的交点；(2)把这些交点按x坐标值以升序排列；(3)对排序后的交点进行奇偶配对，对每一对交点间的区域进行填充。步骤(3)如上图：对y＝8的扫描线，对交点序列按x坐标升序排序得到的交点序列是(2,4,9,13)，然后对交点2与4之间、9与13之间的所有象素点进行填充。求交点、排序、配对、填色利用链表：与当前扫描线相交的边称为活性边(ActiveEdge)，把它们按与扫描线交点x坐标递增的顺序存入一个链表中，称为活性边表AEL(AEL，ActiveEdgeList)。它记录了多边形边沿扫描线的交点序列。AEL中每个对象需要存放的信息：ymax：边所交的最高扫描线；x：当前扫描线与边的交点；Δx：从当前扫描线到下一条扫描线之间的x增量next：指向下一对象的指针。伪码：建立ET，置y为ET中非空桶的最小序号；置AEL表为空，且把y桶中ET表的边加入AEL表中；whileAEL表中非空dobegin对AEL表中的x、Δx按升序排列；按照AEL表中交点前后次序，在每对奇偶交点间的x段予以填充；计算下一条扫描线：y=y+1；if扫描线y=ymaxthen从AEL表中删除这些边；对在AEL表中的其他边，计算与下一条扫描线的交点：x=x+Δx按照扫描线y值把ET表中相应桶中的边加入AEL表中；endendofalgorithm二、区域填充算法：区域可采用两种表示形式:内点表示枚举区域内部的所有像素；内部的所有像素着同一个颜色；边界像素着不同的颜色。边界表示：枚举出边界上所有的像素；边界上的所有像素着同一颜色；内部像素着不同的颜色。区域填充先将区域内的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。简单种子算法扫描线种子算法要求区域是“连通”的。测试对象为象素段,对区域内的每一象素段,只保留其最右边(或左边)的象素作为种子象素.区域填充(扫描线算法)：–目标：减少递归层次–适用于内点表示的4连通区域基本过程：当给定种子点时，首先填充种子点所在的扫描线上的位于给定区域的一个区段，然后确定与这一区段相通的上下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。算法步骤：1、填充并确定种子区段；2、初始化：将种子区段压入堆栈；3、出栈：如果堆栈为空，则算法结束；否则取栈顶元素y,xLeft,xRight），以纵坐标为y的扫描线为当前扫描线，[xLeft,xRight]为搜索区间；4、填充并确定新的区段。实验环境Win7系统，eclipse，jdk实验步骤1.根据上面算法的原理，在实验环境中进行算法的实现；实验内容一．扫描线算法核心代码：privatevoidScanLine(Graphics2Dg2){for(inti=yTop;i=yBottom;i++){//循环扫描线ListIntegerpointList=newArrayListInteger();//定义一个容器存放传过来的点for(Linelb:lineList){if((i=lb.getY1()&&ilb.getY2())||(ilb.getY1()&&i=lb.getY2())){floatx=lb.getX1()+lb.getK()*(i-lb.getY1());//求出交点横坐标intxInt=(int)x;pointList.add(xInt);}}Collections.sort(pointList);//对交点进行排序for(intj=0;jpointList.size()-1;j=j+2){intx1=pointList.get(j);intx2=pointList.get(j+1);g2.drawLine(x1+1,i,x2-1,i);}}}/**画多边形的边*/publicvoiddrawPicLine(Graphics2Dg2){map=getMap();for(inti=1;imap.size();i++){Pointpb1=map.get(i+1);Pointpb2=map.get(i);intx1=pb1.getX();inty1=pb1.getY();intx2=pb2.getX();inty2=pb2.getY();Linelb=newLine(x1,x2,y1,y2,(float)(x1-x2)/(y1-y2));lineList.add(lb);xLift=xLiftx2?xLift:x2;//得到最小的与最大的x,yxRight=xRightx2?xRight:x2;yTop=yTopy2?yTop:y2;yBottom=yBottomy2?yBottom:y2;if(i==(map.size()-1)){x1=pb1.getX();y1=pb1.getY();x2=((Point)map.get(1)).getX();y2=((Point)map.get(1)).getX();lb=newLine(x1,x2,y1,y2,(float)(x1-x2)/(y1-y2));}xLift=xLiftx2?xLift:x2;//得到最小的与最大的x,yxRight=xRightx2?xRight:x2;yTop=yTopy2?yTop:y2;yBottom=yBottomy2?yBottom:y2;}}扫描线种子算法：privatevoidlineFill(Graphics2Dg2){for(inti=yTop;i=yBottom;i++){//循环扫描线//g2.drawLine(xLift,i,xRight,i);ListIntegerpointList=newArrayListInteger();//每条线的交点集合,存放横坐标for(LineBeanlb:lineList){//for循环求直线与多边形的交点if((i=lb.getY1()&&ilb.getY2())||(ilb.getY1()&&i=lb.getY2())){floatx=lb.getX1()+lb.getK()*(i-lb.getY1());//求出交点横坐标intxInt=(int)x;pointList.add(xInt);}}Collections.sort(pointList);//对交点进行排序for(intj=0;jpointList.size()-1;j=j+2){intx1=pointList.get(j);intx2=pointList.get(j+1);g2.drawLine(x1+1,i,x2-1,i);//交点不填充}}}/**画多边形的边*/publicvoiddrawPicLine(Graphics2Dg2){for(inti=1;ipicList.size();i++){//根据给出的顶点画线PointBeanpb1=picList.get(i);intx1=pb1.getX();inty1=pb1.getY();PointBeanpb2=picList.get(i-1);intx2=pb2.getX();inty2=pb2.getY();g2.drawLine(x1,y1,x2,y2);LineBeanlb=newLineBean(x1,x2,y1,y2,(float)(x1-x2)/(y1-y2));//System.out.println((float)(x1-x2)/(y1-y2));lineList.add(lb);xLift=xLiftx2?xLift:x2;//得到最小的与最大的x,yxRight=xRightx2?xRight:x2;yTop=yTopy2?yTop:y2;yBottom=yBottomy2?yBottom:y2;}}实验结果扫描线算法：在界面上点击点，然后点击生成，形成下图黑色的图形：种子填充算法：实验总结在本次实验中，我对图形的了解更具体了，并且也加深了自己对java基本语法的一些巩固，还掌握了一些基本的图形扫描算法的原理，但是编写程序的过程不是很顺利，自己对算法的了解起初不是很深刻，对伪码的解读能力不是很强，在调试过程中，一直出现了很多bug，而且自己代码的集成度不是很高，自己的界面很粗糙，我的界面非常不能入目，在以后的实验中，我要尽量使自己的代码少出bug，并且也会注重自己的界面。争取得到更好的效果。指导教师意见签名：年月日注：可根据教学需要对以上栏目进行增减。表格内容可根据内容扩充。