多边形的扫描转换及区域填充

多边形的扫描转换及区域填充第一页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-2内容基本概念

扫描转换矩形扫描转换多边形区域填充光栅图形的反走样第二页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-3基本概念多边形有两种重要的表示方法顶点表示用多边形的顶点序列来表示多边形。这种表示直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些象素在多边形内，故不能直接用于面着色点阵表示用位于多边形内的象素集合来刻画多边形。这种表示丢失了许多几何信息，但便于帧缓冲器表示图形，是面着色所需要的图形表示形式。第三页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-4基本概念多边形的扫描转换把多边形的顶点表示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应象素设置相应的灰度和颜色，通常称这种转换为多边形的扫描转换。 区域填充（演示）

是指先将在点阵表示的多边形区域内的一点（称为种子点）赋予指定的颜色和灰度，然后将这种颜色和灰度扩展到整个区域内的过程。第四页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-5扫描转换矩形问题：矩形是简单的多边形，那么为什么要单独处理矩形？应用非常多，特别是窗口系统比一般多边形可简化计算共享边界如何处理？左闭右开下闭上开属于谁？第五页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-6扫描转换矩形方法voidFillRectangle(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() */第六页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-7扫描转换多边形凸多边形任意两顶点间的连线均在多边形内凹多边形任意两顶点间的连线有不在多边形内的部分含内环的多边形多边形内再套有多边形，多边形内的多边形也叫内环，内环之间不能相交第七页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-8扫描转换多边形几种方法逐点判断算法逐个判断绘图窗口内的像素，确定它们是否在多边形区域内部，从而求出位于多边形区域内的像素的集合。扫描线算法（要求重点掌握）利用相邻像素之间的连贯性，避免逐点判断和反复求交运算。边缘填充算法利用求余运算，来达到填充的目的。第八页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-9逐点判断算法voidFillPolygonPbyP(Polygon*P,intpolygonColor){intx,y;

for(y=ymin;y<=ymax;y++)for(x=xmin;x<=xmax;x++) if(IsInside(P,x,y)) PutPixel(x,y,polygonColor); else PutPixel(x,y,backgroundColor);}/*endofFillPolygonPbyP() */#defineMAX100Typedefstruct{intPolygonNum;//多边形顶点个数

Pointvertexces[MAX]//多边形顶点数组

}Polygon//多边形结构第九页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-10逐点判断算法逐个判断绘图窗口内的像素如何判断点在多边形的内外关系？射线法弧长法第十页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-11点关于多边形内外关系的判断射线法（演示）如果从一点发出的射线与多边形边界的交点个数为奇数，则该点位于多边形之内，否则位于多边形之外。(a)p1p2p3p4p1(b)p2p3(c)p1p2p3p4(d)p5p1p2p3p4p0p1p2p3p4U0U1U2U3第十一页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-12点关于多边形内外关系的判断弧长法（累计角度法)步骤从v点向多边形P各顶点发出射线，形成有向角计算有向角的和，得出结论（演示）第十二页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-13逐点判断算法-小结逐点判断的算法虽然程序简单，但不可取。原因是速度太慢，效率低。主要是由于该算法割断了各象素之间的联系，孤立地考察各象素与多边形的内外关系，使得几十万甚至几百万个象素都要一一判别，每次判别又要多次求交点，需要做大量的乘除运算，花费很多时间。第十三页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-14扫描线算法处理对象非自交多边形（边与边之间除了顶点外无其它交点）第十四页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-15扫描线算法扫描线算法是多边形扫描转换的常用算法。与逐点判断算法相比，扫描线算法充分利用了相邻象素之间的连贯性，避免了对象素的逐点判断和反复求交的运算，达到了减少计算量和提高速度的目的。开发和利用相邻象素之间的连贯性是光栅图形算法研究的重要内容。扫描转换算法综合利用了区域的连贯性、扫描线的连贯性和边的连贯性等三种形式的连贯性。第十五页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-16扫描线算法基本思想对于一个给定的多边形，用一组水平或垂直的扫描线进行扫描，分别求出每条扫描线与多边形的交点，这些交点将扫描线分割为相间排列的落在多边形内和多边形外的线段，将落在多边形内的所有线段上的每个像素点赋以给定的多边形填充色。利用相邻象素之间的连贯性填充每一条扫描线位于多边形内部的区段。第十六页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-17区域的连贯性设多边形P的顶点Pi=(xi,yi),i=0,1,…,n，又设yi0,yi1,…yin是各顶点Pi的坐标yi的递减数列，即yik≥yik+1,0≤k≤n-1。屏幕上位于y=yik和y=yik+1两条扫描线之间的长方形区域被多边形P的边分割成若干梯形（三角形可看作其中一底边长为零的梯形），它们具有下列性质：第十七页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-18区域的连贯性梯形的两底边分别在y=yik和y=yik+1（yik≥yik+1)两条扫描线上，腰在多边形P的边上或在显示屏幕的边界上。这些梯形可分为两类：一类位于多边形P的内部；另一类在多边形P的外部。两类梯形在长方形区域{yik,yik+1}内相间的排列，即相邻的两梯形必有一个在多边形P内，另一个在P外。第十八页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-19区域的连贯性结论：根据这些性质，实际上只需知道该长方形区域内任一梯形内一点关于多边形P的内外关系后，即可确定区域内所有梯形关于P的内外关系。第十九页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-20扫描线的连贯性设e为一整数，yi0≥e≥yin。若扫描线y=e与多边形P的Pi-1Pi相交，则记其交点的横坐标为xei。以上交点的横坐标递增排序得到的序列称为交点序列。交点序列具有如下性质：第二十页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-21扫描线的连贯性（1）交点个数为偶数。（2）交点之间的区段按交替的顺序依次出现在多边形内部和外部。以上性质称为扫描线的连贯性，它是多边形区域连贯性在一条扫描线上的反映。第二十一页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-22边的连贯性由扫描线y=e和多边形的所有交点递推出扫描线y=d=e+1与多边形各边的交点。边的连贯性，它是区域的连贯性在相邻两扫描线上的反映。扫描线

y=e(x1,e)(x1+1/m,e+1)

y=d=e+1利用边的连贯性求交点q0q3q1q2=xy第二十二页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-23奇点的处理当扫描线与多边形P的交点是P的顶点时，则称该交点为奇点。以上所述多边形的连贯性都基于这样的几何事实：每一条扫描线与多边形P的边界的交点个数都是偶数。但是如果把每一奇点简单地计为一个交点或者简单地计为两个交点，都可能出现奇数个交点。那么如何保证交点数为偶数呢？

y=eq0q3q1q2=第二十三页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-24奇点的处理若奇点做一个交点处理，则情况A，交点个数不是偶数。若奇点做两个交点处理，则情况B，交点个数不是偶数。第二十四页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-25奇点的处理多边形P的顶点可分为两类：极值奇点和非极值奇点。如果(yi-1-yi)(yi+1-yi)≥0，则称顶点Pi为极值点；否则称Pi为非极值点。规定：奇点是极值点时，该点按两个交点计算，否则按一个交点计算。奇点的预处理：第二十五页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-26交点取整规则要求：使生成的像素全部位于多边形之内由直线的扫描转换算法（如中点算法或DDA算法）求出的表示边的像素虽然和交点最靠近，却无法保证这些像素都落在多边形区域的内部．第二十六页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-27交点取整规则假设某非水平边与扫描线y＝e相交，交点的横坐标记为x，则有如下几种规则：（1）x为小数，即交点(x，e)落于扫描线y＝e上两个相邻像素之间X为小数第二十七页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-28交点取整规则（2）交点(x，e)正好落于像素点上边界上象素的取舍问题，避免填充扩大化。按照前面所介绍的对多边形区域边界的处理方法，若(x，e)位于多边形左边上，见图(a)，则将它看作属于多边形；若(x，e)在多边形右边上，见图(b)．则它不属于多边形。左闭右开的原则（x，e）落于像素上的情形第二十八页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-29交点取整规则（3）落在像素点上交点(x，e)为多边形的顶点扫描线与多边形的顶点相交时，交点的取舍，保证交点正确配对。处理方法：将多边形的每条边看成是下端闭上端开第二十九页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-30扫描线算法-数据结构

为了提高效率，在处理一条扫描线时，仅对与它相交的多边形的边进行求交运算。活性边（activeedge)与当前扫描线相交的边；活性边表（AET--Activeedgetable)将活性边按与扫描线交点x坐标递增的顺序存入一个链表中，它记录了多边形边沿扫描线的交点序列。每条扫描线对应一个活性边表。只需对当前扫描线的活性边表作更新，即可得到下一条扫描线的活性边表。第三十页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-31扫描线算法-数据结构(扫描线6的活性边表)AET(扫描线7的活性边表)AET第三十一页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-32扫描线算法-数据结构如何计算下一条扫描线与边的交点？直线方程：ax+by+c=0当前交点坐标：(xi,yi)下一交点坐标：(xi+1,yi+1)xi+1=

((-byi+1)-c)/a=(-b(yi+1)-c)/a=xi-b/axi+1=xi+Δx（Δx=-b/a为常数

)活动边表中需要存放的信息x：当前扫描线与边的交点Δx＝-b/a：从当前扫描线到下一条扫描线之间的x增量ymax：边所交的最高扫描线，即边的上端点的y坐标；第三十二页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-33扫描线算法-数据结构为了方便边的活性边表（AET）的更新，建立另一个表，即边表（ET----EdgeTable）边表中需要存放的信息x：扫描线与该边的初始交点，即边的下端点的x坐标Δx：x的增量ymax：该边的最大y值，即边的上端点的y坐标；边表ET是按边的下端点的y坐标对非水平边进行分类的指针数组。下端点的y坐标的值等于i的边归入第i类。同一类中，各边按x值（x值相等时，按Δx的值）递增的顺序排列成行。第三十三页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-34扫描线算法-数据结构P6P1ET第三十四页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-35扫描线算法-数据结构小结：算法中采用较灵活的数据结构。它由边表ET（EdgeTable）和活性边表AET（ActiveEdgeList）两部分组成。边表ET和活性边表AET中的基本元素为多边形的边。边的结构由以下四个域组成：x：在ET中表示边的下端点的x坐标，在AET中则表示边与扫描线的交点的坐标；Δx：边的斜率的倒数；ymax：边的上端点的y坐标；next：指向下一条边的指针。第三十五页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-36扫描线算法-算法实现步骤1.建立ET；2.将扫描线纵坐标y的初值置为ET中非空元素的最小序号（如前图所示，y=1）；3.置AET为空；4.执行下列步骤直至ET和AET都为空：如果ET中的第y类非空，则将其中的所有边取出并插入AET中；如果有新的边插入AET，则对AET中各边排序；对AET中的边两两配对，将每对边中x坐标按规则取整，获得有效的填充区段，再填充；将当前扫描线纵坐标y值递增1，即y=y+1；对AET中满足y=ymax边删去（因为每条边被看作下闭上开的）；对AET中剩下的每一条边的x递增Δx，即x=x+Δx。第三十六页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-37扫描线算法-算法实现步骤voidpolyfill(polygon,color)intcolor;多边形polygon;{for(各条扫描线i)

{初始化边表头指针ET[i]；

把ymin=i的边放进边表ET[i];

}

y=最低扫描线号；

初始化活性边表AET为空；

for(各条扫描线i)

{把边表ET[i]中的边结点用插入排序法插入AET表，使之按x坐标递增顺序排列；

遍历AET表，把配对交点区间(左闭右开)上的象素(x,y)，用putpixel(x,y,color)改写象素颜色值；

遍历AET表，把ymax=i的结点从AET表中删除，并把ymax>i结点的x值递增Δx；

}}/*polyfill*/第三十七页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-38多边形扫描线算法分析100246810122468P3P2P1P4P5P6e3e4e2e1e5e6^^^^-2.579^1.511^01311^029^1.575-2.573012345677ETymaxx△xe1e2e6e5e3e4第三十八页，共六十二页，编辑于2023年，星期五100246810122468P3P2P1P4P5P6e3e4e2e1e5e6^^^^-2.579^1.511^01311^029^1.575-2.573012345677ETymaxx△xe1e2e6e5e3e4

(11.5,10)->(13,10)AET=空y=1AET=-2.573空1.575(7,1)->(7,1)y=2AET=-2.54.53空1.58.55(4.5,2)->(8.5,2)y=3AET=029空1.5105(2,3)->(10,3)y=4AET=029空1.511.55(2,4)->(11.5,4)y=5AET=029空13(2,5)->(13,5)y=6AET=029空01311(2,6)->(13,6)y=7AET=029-2.579(2,7)->(7,7)1.5711空01311(7,7)->(13,7)y=8AET=029-2.54.59(2,8)->(4.5,8)1.58.51101311(8.5,8)->(13,8)空y=9AET=空y=10AET=1.511.51101311空y=11AET=空11011101.511130(10,9)->(13,9)第三十九页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-40扫描线算法与逐点判断法的比较扫描线算法的数据结构和算法本身都比逐点判断法复杂得多。扫描线算法利用边的连贯性以加速交点的计算，利用ET以排除盲目求交。扫描线算法利用扫描线的连贯性以避免逐点判别，所以速度要比逐点判断算法快得多。第四十页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-41区域填充区域指已经表示成点阵形式的填充图形,它是相互连通的一组像素的集合。区域填充

是对区域重新着色的过程。是指先将区域的一点（称为种子点）赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的。

第四十一页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-42区域填充区域的表示形式1.内点表示枚举出给定区域内所有像素内部的所有像素着同一个颜色边界像素着与内部像素不同的颜色2.边界表示枚举出给定区域所有边界上像素边界上的所有像素着同一颜色内部像素着与边界像素不同的颜色区域的内点表示和边界表示第四十二页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-43区域填充区域填充要求区域是连通的区域的连通形式4连通8连通第四十三页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-44区域填充4连通与8连通区域的区别连通性：4连通可看作8连通区域，但对边界有要求对边界的要求第四十四页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-45种子填充算法-内点表示区域设G为一内点表示的区域，(x,y)为区域内一点，old_color为G的原色。现取(x,y)为种子点对区域G进行填充：即先置像素(x,y)的颜色为new_color，然后逐步将整个区域G都置为同样的颜色。步骤：种子象素入栈，当栈非空时，执行如下三步操作（1）栈顶象素出栈（2）将出栈象素置成多边形色（3）按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。 第四十五页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-46种子填充算法-内点表示区域例：多边形由P0P1P2P3P4构成：P0(1,5)、P1(5,5)、P2(7,3)、P3(7,1)、P4(1,1)设种子点为（3，3），搜索的方向是上、下、左、右。依此类推，最后像素被选中并填充的次序如图中箭头所示P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1)第四十六页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-47种子填充算法-内点表示区域递归算法可实现如下voidFloodFill4(intx,inty,intoldColor,intnewColor){intcolor;color=GetPixel（x，y）;if（color==oldColor）{PutPixel(x,y,newColor);FloodFill4(x,y+1,oldColor,newColor);FloodFill4(x,y-1,oldColor,newColor);FloodFill4(x-1,y,oldColor,newColor);FloodFill4(x+1,y,oldColor,newColor);}

第四十七页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-48种子填充算法-边界表示区域步骤：种子象素入栈，当栈非空时，执行如下三步操作（1）栈顶象素出栈（2）将出栈象素置成多边形色（3）按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。 填充填充第四十八页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-49种子填充算法-边界表示区域voidBoundaryFill4(intx,inty,intboundaryColor,intnewColor){ intcolor; color=GetPixel(x,y); if((color!=boundaryColor)&&(color!=newColor)) { PutPixel(x,y,newColor); BoundaryFill4(x,y+1,oldColor,newColor); BoundaryFill4(x,y-1,oldColor,newColor); BoundaryFill4(x-1,y,oldColor,newColor); BoundaryFill4(x+1,y,oldColor,newColor); }}递归算法可实现如下第四十九页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-50种子填充算法-边界表示区域0123454321(3,2)(2,2)(3,3)(4,2)(3,1)(2,1)(4,1)(4,2)(2,2)(1,2)(2,3)(3,3)第五十页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-51种子填充算法

该算法也可以填充有孔区域。缺点有些像素会入栈多次，降低算法效率；栈结构占空间。递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。改进算法:减少递归次数，提高效率。解决方法：用扫描线填充算法第五十一页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章-52扫描线填充算法目标减少递归层次适用范围内点表示的4连通区域算法思想在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描线上的该段区间；然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的个区段都填充完毕。第五十二页，共六十二页，编辑于2023年，星期五多边形的扫描转换及区域填充第五章