资源描述：
《二维填充图元生成ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、生成填充图元的上机实习利用VC++，编程实现多边形的填充地点：教五319时间：周一下午6-7节周二下午6-7节第五章二维填充图元生成一般步骤确定那些像素位于填充图元的内部；确定以什么颜色填充这些像素；5.1扫描转换矩形5.2扫描转换多边形逐点判断法、扫描线算法、边缘填充算法5.3区域填充（种子填充法）递归填充算法、扫描线算法5.4以图像填充区域5.5字符的表示与输出5.6混淆与反混淆主要内容5.1扫描转换矩形方法：voidFillRectangle(Rectangle*rect,intcolor){intx,y;for(y=rect->ymin
2、;y<=rect->ymax;y++)for(x=rect->xmin;x<=rect->xmax;x++)SetPixel(x,y,color);}/*endofFillRectangle()*/问题：矩形是简单的多边形，那么为什么要单独处理矩形？比一般多边形可简化计算。应用非常多，窗口系统。边界如何处理？原则：左闭右开，下闭上开属于谁？5.2扫描转换多边形多边形的表示方法顶点表示点阵表示扫描转换多边形：将顶点表示形式转换成点阵表示形式三种方法：逐点判断法；扫描线算法；边缘填充法voidFillPolygonPbyP(Polygon*P,in
3、tpolygonColor){intx,y;for(y=ymin;y<=ymax;y++)for(x=xmin;x<=xmax;x++)if(IsInside(P,x,y))SetPixel(x,y,polygonColor);elseSetPixel(x,y,backgroundColor);}/*endofFillPolygonPbyP()*/#defineMAX100Typedefstruct{intPolygonNum;//多边形顶点个数Pointvertexces[MAX];//多边形顶点数组}Polygon;//多边形结构1、逐点判
4、断法逐个判断绘图窗口内的像素：如何判断点在多边形的内外关系？1）射线法2）累计角度法3）编码法IsInside(P,x,y)1）射线法步骤：从待判别点v发出射线求交点个数KK的奇偶性决定了点与多边形的内外关系奇异情况处理射线与多边形顶点相交时，如何算交点的个数2）累计角度法步骤从V点向多边形P顶点发出射线，形成有向角计算有向角的和，得出结论离散计算方法：编码方法3）编码方法：累计角度方法的离散方法Step:a.预处理，测试点在边上否？b.V为原点作局部坐标系,对象限按逆时针（或顺时针）编码；c.顶点编码Ipi，d.边编码。PiPi+1:△PiP
5、i+1=Ipi+1-Ipie.计算∑△PiPi+1（其中△PnPn+1=△PnP0)：若∑为0,V在P外；若∑为+/-4，V在P内；逐点判断法程序简单，速度太慢，效率低。P0P1P2vv01232、扫描线算法目标：利用相邻像素之间的连贯性，提高算法效率处理对象：非自交多边形（边与边之间除了顶点外无其它交点）基本原理一条扫描线与多边形的边有偶数个交点步骤(对于每一条扫描线):(1)求交点(2)交点排序(3)交点配对，填充区段。边的连贯性（确定交点）第一类交点：位于同一条边上的后继交点（中点算法）第二类交点：新出现的边与扫描线的交点（顶点即为交点）
6、交点的取整规则要求：使生成的像素全部位于多边形之内用于线画图元扫描转换的四舍五入原则导致部分像素位于多边形之外，从而不可用规则如下假定非水平边与扫描线y=e相交，交点的横坐标为x规则(1)：x为小数时，即交点落于扫描线上两个相邻像素之间(a)交点位于左边之上，向右取整(b)交点位于右边之上，向左取整规则(2)：交点位于边界上时，象素的取舍问题。边界象素：规定落在右上边界的象素不予填充。具体实现时，只要对扫描线与多边形的相交区间左闭右开规则(3)：扫描线与多边形的顶点相交时，交点的取舍，保证交点正确配对。解决方法：检查两相邻边在扫描线的哪一侧。只
7、要检查顶点的两条边的另外两个端点的Y值，两个Y值中大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。1）活化边：与当前扫描线相交的边。按交点x（x相同则按deltax）递增顺序存放在一个链表中；该链表称作活化边表（AEL)。-算法所涉及的数据结构：Ymax:与边相交的最高扫描线号X：在AEL中表示当前扫描线与边的交点的x坐标；初值为边的下端点的x坐标(存于ET中)。△X：边的斜率的倒数Nextedge:指向下一条边的指针AEL与ET的结点信息（p75）：typedefstruct{intymax;floatx,deltax;Edge*n
8、extEdge;}Edge;P0P1P2P3P4P5P6672）边的分类表（ET）按照边的下端点y坐标对非水平边进行分类的指针数组。下端点y坐标值等于
