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

《多边形的扫描转换算法、区域填充算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

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

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

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

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

7、4、填充并确定新的区段。实验Win7系统，eclipse，jdk环境实验1.根据上面算法的原理，在实验环境中进行算法的实现；步骤一．扫描线算法核心代码：privatevoidScanLine(Graphics2Dg2){for(inti=yTop;i<=yBottom;i++){//循环扫描线ListpointList=newArrayList();//定义一个容器存放传过来的点for(Linelb:lineList){if((i>=lb.getY1()&&i

8、

9、(i