多边形的转换及区域填充

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

1、第五章多边形的扫描转换及区域填充内容基本概念扫描转换矩形扫描转换多边形区域填充光栅图形的反走样多边形的扫描转换及区域填充2基本概念多边形有两种重要的表示方法顶点表示用多边形的顶点序列来表示多边形。这种表示直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些象素在多边形内，故不能直接用于面着色点阵表示用位于多边形内的象素集合来刻画多边形。这种表示丢失了许多几何信息，但便于帧缓冲器表示图形，是面着色所需要的图形表示形式。多边形的扫描转换及区域填充3基本概念多边形的扫描转换把多边形的顶点表示转换为点阵表示，也

2、就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应象素设置相应的灰度和颜色，通常称这种转换为多边形的扫描转换。区域填充（演示）是指先将在点阵表示的多边形区域内的一点（称为种子点）赋予指定的颜色和灰度，然后将这种颜色和灰度扩展到整个区域内的过程。多边形的扫描转换及区域填充4扫描转换矩形问题：矩形是简单的多边形，那么为什么要单独处理矩形？应用非常多，特别是窗口系统比一般多边形可简化计算共享边界如何处理？左闭右开下闭上开属于谁？多边形的扫描转换及区域填充5扫描转换矩形方法voidFillRectan

3、gle(Rectangle*rect,intcolor){intx,y;for(y=rect->ymin;y<=rect->ymax;y++)for(x=rect->xmin;x<=rect->xmax;x++)PutPixel(x,y,color);}/*endofFillRectangle()*/多边形的扫描转换及区域填充6扫描转换多边形凸多边形任意两顶点间的连线均在多边形内凹多边形任意两顶点间的连线有不在多边形内的部分含内环的多边形多边形内再套有多边形，多边形内的多边形也叫内环，内环之间不能相交多边形的扫描转换及区

4、域填充7扫描转换多边形几种方法逐点判断算法逐个判断绘图窗口内的像素，确定它们是否在多边形区域内部，从而求出位于多边形区域内的像素的集合。扫描线算法（要求重点掌握）利用相邻像素之间的连贯性，避免逐点判断和反复求交运算。边缘填充算法利用求余运算，来达到填充的目的。多边形的扫描转换及区域填充8逐点判断算法voidFillPolygonPbyP(Polygon*P,intpolygonColor){intx,y;for(y=ymin;y<=ymax;y++)for(x=xmin;x<=xmax;x++)if(IsInside(P

5、,x,y))PutPixel(x,y,polygonColor);elsePutPixel(x,y,backgroundColor);}/*endofFillPolygonPbyP()*/#defineMAX100Typedefstruct{intPolygonNum;//多边形顶点个数Pointvertexces[MAX]//多边形顶点数组}Polygon//多边形结构多边形的扫描转换及区域填充9逐点判断算法逐个判断绘图窗口内的像素如何判断点在多边形的内外关系？射线法弧长法多边形的扫描转换及区域填充10点关于多边形内外

6、关系的判断射线法（演示）如果从一点发出的射线与多边形边界的交点个数为奇数，则该点位于多边形之内，否则位于多边形之外。(a)p1p2p3p4p1(b)p2p3(c)p1p2p3p4(d)p5p1p2p3p4p0p1p2p3p4U0U1U2U3多边形的扫描转换及区域填充11点关于多边形内外关系的判断弧长法（累计角度法)步骤从v点向多边形P各顶点发出射线，形成有向角计算有向角的和，得出结论（演示）多边形的扫描转换及区域填充12逐点判断算法-小结逐点判断的算法虽然程序简单，但不可取。原因是速度太慢，效率低。主要是由于该算法割断了

7、各象素之间的联系，孤立地考察各象素与多边形的内外关系，使得几十万甚至几百万个象素都要一一判别，每次判别又要多次求交点，需要做大量的乘除运算，花费很多时间。多边形的扫描转换及区域填充13扫描线算法处理对象非自交多边形（边与边之间除了顶点外无其它交点）多边形的扫描转换及区域填充14扫描线算法扫描线算法是多边形扫描转换的常用算法。与逐点判断算法相比，扫描线算法充分利用了相邻象素之间的连贯性，避免了对象素的逐点判断和反复求交的运算，达到了减少计算量和提高速度的目的。开发和利用相邻象素之间的连贯性是光栅图形算法研究的重要内容。扫描

8、转换算法综合利用了区域的连贯性、扫描线的连贯性和边的连贯性等三种形式的连贯性。多边形的扫描转换及区域填充15扫描线算法基本思想对于一个给定的多边形，用一组水平或垂直的扫描线进行扫描，分别求出每条扫描线与多边形的交点，这些交点将扫描线分割为相间排列的落在多边形内和多边形外的线段，将落在多边形内的所有线段上的每个像素点赋