文档介绍：第四章多边形扫描转换及图像区域填充
§1 引言
回忆一下第三章的一个例子
再看一幅画
§2 多边形扫描转换
把多边形的顶点表示转换为点阵表示
怎样转换?逐点?
z 扫描线转换算法
扫描线y=10
扫描线y=2
大概的过程
(1)求出当前一条扫描线与多边形各边的交点,
(2)然后根据交点进行配对,并对配对交点之间的区域
进行填充;
怎样配对?
配对原则:
要分极值点与非极值点,
极值点算两个点,也就是配对两次。
而非极值点算一个点,只能被配对一次。
水平边不作处理!
准备工作
建立两个表:
边的分类表ET(Edge Table)
边的活化链表AEL(Active Edge List)
ET和AEL中的基本单元是多边形的边。边的数据结构由以下
四个元素构成:
Ymax:边的上端点Y坐标
x:在ET中表示边的下端点的x坐标,在AEL中则表示边与
扫描线的交点的x坐标。
∆x:边的斜率倒数这四个元素能完整地表
next:指向下一条边的指针。示一条边?
边的分类原则
表ET是按边下端点的纵坐标y对非水平边进行分
类的指针数组:下端点的纵坐标y的值等于i的
边归入第i类
P2P3 P3P4
P5P6
P1P2
P0P1 P0P7
P0(7, 2)、P1(2, 5)、P2(2, 14)、P3(8, 8)、P4(10, 12)、P5(14, 12)、
P6(14, 6) 、P7(11, 6)、
具体执行过程如下:
Step1:取扫描线纵坐标y的初始值为ET表中非空元素的
最小序号。图中y=2。
Step 2:将边的活化链表AEL置为空。
Step 3:按从下到上的顺序对纵坐标值为yc的扫描线(当
前扫描线)执行下列步骤,直到ET和AEL都变成空为止。
(1)如ET中的第yc类元素非空,则将属于该类的所有边从ET
中取出并插入到边的活化链表AEL中,AEL中的各边按照x
值(当x的值相等时,按∆x的值)递增方向排序。
(2)若相对于当前扫描线yc,边的活化链表AEL非空,则将
AEL中的边两两依次配对。每一对边与当前扫描线的交点
所构成的区段位于多边形内,依次对这些区段上的点进
行着色。
(3)将边的活化链表AEL中满足yc=ymax的边删去。
(4)将边的活化链表AEL剩下的每一条边的x域累加∆x,即:
x:=x+∆x。
(5)将当前的扫描线的纵坐标值y累加1,即: yc= yc+1。