多边形的转换与区域填充

《多边形的转换与区域填充》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章多边形的扫描转换与区域填充第4章多边形的扫描转换与区域填充一、在计算机图形学中，多边形有两种重要的表示方法：1.顶点表示用多边形的顶点序列来刻画多边形顶点表示特点表示方法直观，几何意义强，占内存空间少，但没指明哪些像素在多边形内，不能直接用于着色。多边形的顶点表示第4章多边形的扫描转换与区域填充2.点阵表示用位于多边形内部或边界上的像素集合来刻画多边形点阵表示特点会失去很多重要的几何信息，不过它是光栅显示系统显示面着色时所需的图形表示形式。多边形的点阵表示第4章多边形的扫描转换与区域填充二

2、、多边形填充方式1.多边形扫描转换：顶点表示不能直接用于显示，必须要进行从多边形顶点表示到点阵表示的转换，这种转换就是给多边形包围的区域着色的过程，即从多边形的给定边界出发，求出位于其内部的各个像素，并将其灰度和颜色值写入帧缓存中相应的单元。主要用来填充多边形区域以及由多边形拟合的其他简单曲线区域。2.区域填充：从给定的位置开始涂描直到指定的边界为止。用在具有复杂形状边界的多边形以及交互式绘图系统中。第4章多边形的扫描转换与区域填充4.1矩形填充4.2多边形扫描转换4.3区域填充4.4多边形扫描

3、转换与区域填充的区别4.5光栅图形的反走样4.1矩形填充为了将它用指定的颜色均匀填充，只要填充从ymin到ymax每条扫描线位于xmin和xmax之间的区段就可以。其程序如下：4.1矩形填充为了减少函数调用的次数，每条扫描线上的[xmin，xmax]区间可以用画线函数填充，其程序如下：4.1矩形填充存在问题：如果两个矩形共享一条边：（1）如果象素的中心落在某个矩形区域内，则它属于该区域。（2）如果将中心落在其共享边界的像素看成是同时属于两个矩形图元区域，那么，落在共享边界上的像素就会被重画两次。

4、（3）如果将中心落在其共享边界的像素看成是不属于任何区域，那么，中心落在共享边界上的像素就会被丢失。处理措施：如果像素的中心落在矩形边界的左方或下方时，该像素属于矩形，否则不属于该多边形区域，也就是说，如果象素的中心落在矩形边界的右方或上方时，该象素不属于矩形区域。4.2多边形扫描转换4.2.1逐点判断算法基本思想：逐个判断绘图窗口内的像素，确定它们是否在多边形区域内部，从而求出位于多边形区域内的像素的集合。实现扫描转换多边形最简单方法就是逐点判断。实质：进行多边形对平面上点的包含性检查常用方法

5、：射线法弧长法4.2.1逐点判断算法1.射线法基本思想：由被测点向某方向作射线，计算此射线与多边形所有边的交点个数，用交点分布的奇偶性判别多边形与点的关系。判断依据：若交点个数为奇数，则被测点在多边形内部；若交点个数为偶数（包括0），则该点在多边形的外部。ACBDabdc4.2.1逐点判断算法一、射线法问题：当射线恰好通过多边形的顶点时，怎么判断？射线f过顶点，若将交点计数为2，则F点在多边形外。但若规定射线过顶点时，计数为1，则E在多边形内。efEF12345AB4.2.1逐点判断算法点A:0

6、个交点，在多边形外点B:1个交点，在多边形内点C：3个交点，在多边形内点D:1个交点，在多边形内点E:2个交点，在多边形外点F:1个交点，在多边形内（剔除重合边）f一、射线法措施：在射线左边的边与该射线相交时交点有效，应计数；而在射线右边的边与射线相交时交点无效，不计数。（左闭右开原则）4.2.1逐点判断算法二、弧长法要求多边形由有向边组成，即规定沿多边形各边的走向其左侧（或右侧）为多边形的内部。思想以被测点为圆心作单位圆，将全部有向边向单位圆作径向投影，并计算其在单位圆上弧长的代数和。判断方法

7、如果代数和为0，则被测点在多边形之外，若代数和为2，则被测点在多边形之内。其他对于内部有空洞的多边形，只要按照上述规定来定义多边形的有向边，则可以采用同样的测试方法。4.2.1逐点判断算法二、弧长法点P在多边形外部点P在多边形内部4.2.1逐点判断算法算法实现：用函数Inside（polygon，x，y）来测试被测点（x，y）的位置；函数返回“真”值，即可对多边形内部的点进行填充。算法特点：简单速度慢算法割断了像素间的联系，孤立地考察各个像素与多边形的内外关系，使得绘图窗口内的每一个像素都要一

8、一判别，每次判别又需要大量的运算，所以效率很低。4.2.2扫描线填充算法一、区域特点：一条扫描线上的像素存在着相关性在多边形边处，像素性质才发生变化将相邻像素放在一起测试，从而减少测试点的数目4.2.2扫描线填充算法二、基本思想按扫描线顺序，先计算出扫描线与多边形区域边界的交点，然后判断扫描线上的哪些部分在区域边界之内，再用要求的颜色显示边界内的像素。实现：依次考察各条扫描线，一条扫描线从左至右与多边形的交点是成对出现的，即A、B点，C、D点之间的像素都位于多边形之内，则A、B为一个区段，C、D