扫描线填充种子填充线宽和线型

《扫描线填充种子填充线宽和线型》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、学习内容3.4区域填充算法3.5线宽与线型的处理学习要点1、理解掌握面域填充的概念，区域多边形的分类，面域填充的步骤；2、理解扫描线填充算法的实质，掌握扫描线填充算法的过程；3、了解种子填充算法和图案填充算法。4、掌握线宽的处理以及线型的分类。一、扫描线填充算法区域是指相互连通的一组像素的集合。通常是由一个封闭的轮廓来定义，处于一个封闭轮廓线内的所有像素点即构成了一个区域。例如：矩形、圆、椭圆、多边形等等。1、扫描线填充算法的实质区域---多边形（凸、凹）、圆、椭圆、带孔的。区域填充---如何用一种颜色或图案填充二维区域。区域

2、填充分两步：确定需要填充那些像素确定需要那些颜色值（图案）911912345687100018764532逐点判断法逐个判断绘图窗口内的像素：逐点判断的算法虽然程序简单，但不可取。原因是速度太慢，主要是由于该算法割断了各象素之间的联系，孤立地考察各象素与多边形的内外关系，使得几十万甚至几百万个象素都要一一判别，每次判别又要多次求交点，需要做大量的乘除运算，花费很多时间。交点配对，1与2，3……，每对表示一个区间。排序，由于交点不一定由左到右求出，因此将求出的交点按x坐标值排序。1234算出交点；划分区间；分配颜色。求交点，即计

3、算扫描线与多边形各边的交点。(4)区间填充扫描线填充步骤911912345687100018764532问题一：991234568710001876453211交点的取舍:比较交点与两边上其余两顶点y值大小，确定交点个数取0、1、2。如果大于交点y值个数为2，则交点取两次，该点填充。如果大于交点y值个数为0，则交点取零次，该点不填充。2次如果大于交点y值个数为1，则交点取一次。0次0次1次扫描线与顶点相交时，交点个数的取舍？0121234301212343长方形面积S=(4-1)*(3-1)=6按照扫描线填充算法填充后为什么扩

4、大化？图形对象是用有限多个离散的像素表示，图形有大小、面积，但是点只有位置，而像素不仅有位置，还有大小。对于边界象素全部填充造成扩大化。S1=4*3=12S2=3*2=6问题二：多边形边界象素的取舍？“左闭右开”、“下闭上开”两个连贯性当前扫描线与各边的交点顺序，与下一条扫描线与各边的交点顺序很可能相同或类似。边的连贯性扫描线的连贯性xer=xdr+1/kryer=ydr+1kr为边的斜率减少求扫描线和多边形各边的交点的计算量2、扫描线填充算法具体实现911912345687100018764532如何刻画多边形的边一、边的分

5、类活化边表（活性边表）AEL（ActiveEdgeList）—按活化边与扫描线交点x坐标递增的顺序存放在一个链表中。对应于一条扫描线。有序边—在当前扫描线第一次出现的边。有序边表ET（EdgeTable）—按有序边与扫描线交点x坐标递增的顺序存放在一个链表中。仅对非水平边分析，对应于一条扫描线。活化边（活性边）—与当前扫描线相交的多边形的边。二、边的结构边结构上端点y坐标当前扫描线与边的交点扫描线间x增量xDxymaxLINK边的结构有四个域组成（除指针外顺序可以相互交换）：ymax边的上端点的y坐标（y的最大值）；x在ET中

6、表示边的下端点的x坐标，在AEL中则表示边与扫描线的交点的x坐标；Δx边的斜率的倒数(到下一条扫描线x的增量）；next指向下一条边的指针。算法：活化边表法－－通过单向链接表的操作得到扫描线与边的交点。原理：建立在图形的空间连贯性（边的连贯性）和扫描线的连贯性基础上，计算图形封闭区域边界与扫描线交点，将扫描线分成区间，并对区间进行填充。有序边表的建立注意：1边的分类；2边的排序（如果x坐标相等，则按Δx排序）；3边的结构；107-5/3e51020e6∧11120e3∧1175/4e4∧55/47e2∧^^^^^扫描线号^87

7、6543210^^^45-1e0通过有序边，利用边的连贯性建立活化边表。它记录了多边形边沿扫描线的交点序列。注意：1边的删除(将满足ymax=y的边删除）；2边的增加；3边的排序；4X值的累加；5边的结构；活化边表的建立活化边表的建立107-5/3e51020e6∧11120e3∧1175/4e4∧55/47e2∧^^^^^^876543210^^^45-1e0有序边表活化边表Y=14555/47e2e0∧-1Y=2433/44-15∧5/4e2e0Y=3338/44-15∧5/4e2e0Y=442-1543/4∧5/4102

8、0e2e0e6活化边表的建立有序边表活化边表Y=3338/44-15∧5/4e2e0Y=4543/4∧5/41020e2e6107-5/3e51020e6∧11120e3∧1175/4e4∧55/47e2∧^^^^^^876543210^^^45-1e0活化边表的建立有序边表