多边形的扫描转换算法、区域填充算法(共10页).doc

《多边形的扫描转换算法、区域填充算法(共10页).doc》由会员分享，可在线阅读，更多相关《多边形的扫描转换算法、区域填充算法(共10页).doc（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上贵州大学计算机图形学实验报告学院：计算机科学与信息学院 专业：软件工程 班级：姓名学号实验组实验时间指导教师成绩实验项目名称实验三 多边形的扫描转换算法、区域填充算法实验目的通过本实验，了解并掌握在光栅显示系统中多边形的扫描转换和区域填充算法。实验要求1、 用光栅扫描算法画出不自交的图形：2、 用光栅扫描算法画出自交图形：3、 用区域填充法画出图形：实验原理一、 光栅扫描算法： 扫描线算法是扫描转换多边形的常用算法，它充分利用了相邻像素之间的连贯性，避免了逐点判断和反复求交计算，达到了减少计算量和提高算法效率的目的。处理对象：非自交多边形 （边与边之间除了顶点外无其它

2、交点）。开发和利用相邻象素之间的连贯性是光栅图形学算法的重要技巧。扫描线算法综合利用了区域的连贯性、扫描线的连贯性和边的连贯性等三种形式的连贯性。区域的连贯性：相邻两条扫描线构成一个水平长方形区域，并被多边形的边分割为若干梯形（一类位于多边形的内部；另一类在多边形的外部，且间隔排列）。只需知道该区域内任一梯形中一点关于多边形的内外关系，即可确定区域内所有梯形关于多边形的内外关系。 扫描线的连贯性：区域的连贯性在一条扫描线上的反映；边的连贯性：某条边与当前扫描线相交，也可能与下一条扫描线相交。可通过与当前扫0246810122468101234描线的交点计算与下一扫描线的交点(利用斜率)。（区域

3、的连贯性在相邻两扫描线上的反映）根据扫描线的连贯性可知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的内部点。所以，对所有的扫描线填充入点到出点之间的点就可填充多边形。如何具体实现（如何找到入点、出点）？根据区域的连贯性，分为3个步骤：(1)求出扫描线与多边形所有边的交点；(2)把这些交点按x坐标值以升序排列；(3)对排序后的交点进行奇偶配对，对每一对交点间的区域进行填充。步骤(3)如上图：对y8的扫描线，对交点序列按x坐标升序排序得到的交点序列是(2,4,9,13)，然后对交点2与4之间、9与13之间的所有象素点进行填充。求交点、排序、配对、填色利用链表：与当前扫描线相交的边称

4、为活性边(Active Edge)，把它们按与扫描线交点x坐标递增的顺序存入一个链表中，称为活性边表AEL (AEL， Active Edge List)。它记录了多边形边沿扫描线的交点序列。AEL中每个对象需要存放的信息：ymax：边所交的最高扫描线；x：当前扫描线与边的交点；x：从当前扫描线到下一条扫描线之间的x增量next：指向下一对象的指针。伪码：建立ET，置y为ET中非空桶的最小序号；置AEL表为空，且把y桶中ET表的边加入AEL表中；while AEL表中非空 dobegin 对AEL表中的x、 x按升序排列； 按照AEL表中交点前后次序，在每对奇偶交点间的x段予 以填充； 计算下

5、一条扫描线：y=y+1； if 扫描线 y=ymaxthen 从AEL表中删除这些边； 对在AEL表中的其他边，计算与下一条扫描线的交点：x=x +x 按照扫描线y值把ET表中相应桶中的边加入AEL表中；endend of algorithm二、 区域填充算法： 区域可采用两种表示形式:内点表示枚举区域内部的所有像素；内部的所有像素着同一个颜色；边界像素着不同的颜色。边界表示：枚举出边界上所有的像素；边界上的所有像素着同一颜色；内部像素着不同的颜色。区域填充先将区域内的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。简单种子算法扫描线种子算法要求区域是“连通”的。测试对象为象素段 ,对区

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

7、jdk实验步骤1. 根据上面算法的原理，在实验环境中进行算法的实现；实验内容一 扫描线算法核心代码：private void ScanLine(Graphics2D g2) for(int i=yTop;i=yBottom;i+)/循环扫描线ListpointList =new ArrayList();/定义一个容器存放传过来的点for(Line lb : lineList)if(i=lb.getY1()&ilb.getY2()|(i=lb.getY2()float x = lb.getX1()+lb.getK()*(i-lb.getY1();/求出交点横坐标int xInt = (int)

8、x;pointList.add(xInt);Collections.sort(pointList);/对交点进行排序for(int j=0;jpointList.size()-1;j=j+2)int x1 = pointList.get(j);int x2 = pointList.get(j+1);g2.drawLine(x1+1, i, x2-1, i);/* * 画多边形的边 */public void drawPicLine(Graphics2D g2) map = getMap();for(int i = 1; i map.size(); i+) Point pb1 = map.get

9、(i+1);Point pb2 = map.get(i);int x1 = pb1.getX();int y1 = pb1.getY();int x2 = pb2.getX();int y2 = pb2.getY();Line lb = new Line(x1, x2, y1, y2, (float)(x1-x2)/(y1-y2);lineList.add(lb);xLift = xLiftx2? xRight:x2;yTop = yTopy2? yBottom:y2;if(i = (map.size()-1) x1 = pb1.getX();y1 = pb1.getY();x2 = (Poi

10、nt)map.get(1).getX();y2 = (Point)map.get(1).getX();lb = new Line(x1, x2, y1, y2, (float)(x1-x2)/(y1-y2);xLift = xLiftx2? xRight:x2;yTop = yTopy2? yBottom:y2;扫描线种子算法：private void lineFill(Graphics2D g2) for(int i=yTop;i=yBottom;i+)/循环扫描线/g2.drawLine(xLift, i, xRight, i);List pointList =new ArrayList(

11、);/每条线的交点集合,存放横坐标for(LineBean lb : lineList)/for循环求直线与多边形的交点if(i=lb.getY1()&ilb.getY2()|(i=lb.getY2()float x = lb.getX1()+lb.getK()*(i-lb.getY1();/求出交点横坐标int xInt = (int) x;pointList.add(xInt);Collections.sort(pointList);/对交点进行排序for(int j=0;jpointList.size()-1;j=j+2)int x1 = pointList.get(j);int x2

12、= pointList.get(j+1);g2.drawLine(x1+1, i, x2-1, i);/交点不填充/* * 画多边形的边 */public void drawPicLine(Graphics2D g2) for(int i=1;ipicList.size();i+)/根据给出的顶点画线PointBean pb1 = picList.get(i);int x1 = pb1.getX();int y1 = pb1.getY();PointBean pb2 = picList.get(i-1);int x2 = pb2.getX();int y2 = pb2.getY();g2.dr

13、awLine(x1, y1, x2, y2);LineBean lb = new LineBean(x1, x2, y1, y2, (float)(x1-x2)/(y1-y2);/System.out.println(float)(x1-x2)/(y1-y2);lineList.add(lb);xLift = xLiftx2? xRight:x2;yTop = yTopy2? yBottom:y2;实验结果扫描线算法：在界面上点击点，然后点击生成，形成下图黑色的图形：种子填充算法：实验总结 在本次实验中，我对图形的了解更具体了，并且也加深了自己对java基本语法的一些巩固，还掌握了一些基本的图形扫描算法的原理，但是编写程序的过程不是很顺利，自己对算法的了解起初不是很深刻，对伪码的解读能力不是很强，在调试过程中，一直出现了很多bug，而且自己代码的集成度不是很高，自己的界面很粗糙，我的界面非常不能入目，在以后的实验中，我要尽量使自己的代码少出bug，并且也会注重自己的界面。争取得到更好的效果。指导教师意见签名： 年 月 日注：可根据教学需要对以上栏目进行增减。表格内容可根据内容扩充。专心-专注-专业