多边形的扫描转换算法

1、二、多边形的扫描转换算法扫描转换算法步骤： step1找出扫描线与多边形边界线的所有交点；step2按x坐标增加顺序对交点排序；step3在交点对之间进行填充。（偶数） 二、多边形的扫描转换算法扫描转换算法步骤： step1找出扫描线与多边形边界线的所有交点；step2按x坐标增加顺序对交点排序；step3在交点对之间进行填充。（偶数） 二、多边形的扫描转换算法扫描转换算法步骤： step1找出扫描线与多边形边界线的所有交点；step2按x坐标增加顺序对交点排序；step3在交点对之间进行填充。（偶数） 二、多边形的扫描转换算法扫描转换算法步骤： step1找出扫描线与多边形边界线的所有交点；

2、step2按x坐标增加顺序对交点排序；step3在交点对之间进行填充。（偶数） 二、多边形的扫描转换算法扫描转换算法步骤： step1找出扫描线与多边形边界线的所有交点；step2按x坐标增加顺序对交点排序；step3在交点对之间进行填充。（偶数） 二、多边形的扫描转换算法扫描转换算法步骤： step1找出扫描线与多边形边界线的所有交点；step2按x坐标增加顺序对交点排序；step3在交点对之间进行填充。（偶数） 二、多边形的扫描转换算法扫描线经过顶点时的情况： 二、多边形的扫描转换算法扫描线经过顶点时的情况： 二、多边形的扫描转换算法顶点的种类： 1局部极大： 相邻顶点的y坐标，都小于该顶

3、点的y坐标 2局部极小： 相邻顶点的y坐标，都大于该顶点的y坐标 3 非局部极值点（特异点）22221正确的处理： 局部极大或局部极小：2个交点 非局部极值点：1个交点 二、多边形的扫描转换算法另一种更简单的处理方法：对非局部极值点的顶点，将其上面的边缩短两条相邻扫描线对应的一个单位。 对非极值点的简便处理2222局部极大或局部极小点，交点看做是二个22221局部极大或局部极小点，交点看做是二个非局部极值点，交点看做一个2222局部极大或局部极小点，交点看做是二个非局部极值点，交点看做一个非局部极值点将这些相邻边分割开来如何计算扫描线与多边形边界线的所有交点？ 若扫描线yi与多边形边界线交点的

4、x坐标是xi，则对下一条扫描线yi+l，它与那条边界线的交点的x坐标xi+1，可如下求出：ABC扫描线与多边形边的交点计算活跃(活性)边：与当前扫描线相交的边活跃(活性)边表AET：存贮当前扫描线相交的各边的表。 ymaxx 1/mnextymax:当前这条边的上端点的y坐标x: 当前边与扫描线交点的x坐标1/m:当前边的斜率的倒数next：指向下一条边的指针每次离开一条扫描线进入下一条之前，将表中有但与下一条扫描线不相交的边清除出表，将与下一条扫描线相交而表中没有的边加入表中。新边表ET：记录多边形的所有边，按y坐标递增排序ymaxxmin 1/mnextymax: 与较大的x坐标对应的端点

5、的y坐标xmin: 与较小的y坐标对应的端点的x坐标1/m: 斜率的倒数next：指向下一条边的指针新边表ET：每条边的记录信息：ET：AET指针初始化137-5/2e1576/4e60234920e25611130e5797-5/2e31176/4e4891011 ymax xmin 1/me1e6e2e5e3e4ET：AET指针初始化137-5/2e1576/4e60234920e25611130e5797-5/2e31176/4e4891011 ymax xmin 1/me1e6e2e5e3e4ET：扫描线137-5/2e1576/4e6137-5/2e1576/4e60234920e2

6、5611130e5797-5/2e31176/4e4891011 ymax xmin 1/me1e6e2e5e3e4ET：扫描线2341/2-5/2e1581/26/4e6扫描线137-5/2e1576/4e6137-5/2e1576/4e60234920e25611130e5797-5/2e31176/4e4891011 ymax xmin 1/me1e6e2e5e3e4ET：扫描线332-5/2e15106/4e6扫描线2341/2-5/2e1581/26/4e6137-5/2e1576/4e60234920e25611130e5797-5/2e31176/4e4891011 ymax x

7、min 1/me1e6e2e5e3e4ET：扫描线4920e25111/26/4e6扫描线332-5/2e15106/4e6137-5/2e1576/4e60234920e25611130e5797-5/2e31176/4e4891011 ymax xmin 1/me1e6e2e5e3e4ET：扫描线5920e25136/4e6扫描线4920e25111/26/4e6137-5/2e1576/4e60234920e25611130e5797-5/2e31176/4e4891011 ymax xmin 1/me1e6e2e5e3e4ET：扫描线6920e211130e5扫描线5920e25136

8、/4e6e1e6e2e5e3e4137-5/2e1576/4e60234920e25611130e5797-5/2e31176/4e4891011 ymax xmin 1/mET：扫描线7920e297-5/2e31176/4e411130e5扫描线6920e211130e5e1e6e2e5e3e4137-5/2e1576/4e60234920e25611130e5797-5/2e31176/4e4891011 ymax xmin 1/mET：扫描线8920e2941/2-5/2e31181/26/4e411130e5扫描线7920e297-5/2e31176/4e411130e5e1e6e2

9、e5e3e4137-5/2e1576/4e60234920e25611130e5797-5/2e31176/4e4891011 ymax xmin 1/mET：扫描线9920e292-5/2e311106/4e411130e5扫描线8920e2941/2-5/2e31181/26/4e411130e5e1e6e2e5e3e4137-5/2e1576/4e60234920e25611130e5797-5/2e31176/4e4891011 ymax xmin 1/mET：扫描线1011111/26/4e411130e5扫描线9920e292-5/2e311106/4e411130e5e1e6e2

10、e5e3e4137-5/2e1576/4e60234920e25611130e5797-5/2e31176/4e4891011 ymax xmin 1/mET：扫描线1111136/4e411130e5扫描线1011111/26/4e411130e5e1e6e2e5e3e4137-5/2e1576/4e60234920e25611130e5797-5/2e31176/4e4891011 ymax xmin 1/mET：扫描线12扫描线1111136/4e411130e5e1e6e2e5e3e4137-5/2e1576/4e60234920e25611130e5797-5/2e31176/4e4

11、891011 ymax xmin 1/me1e6e2e5e3e4AET指针初始化扫描线137-5/2扫描线1011111/26/4e1576/4e6扫描线2341/2-5/2e1581/26/4e6扫描线332-5/2e15106/4e6e4扫描线4920e25111/26/4e6扫描线5920e25136/4e65扫描线6920e211130e5扫描线7920e297-5/2e31176/4e411130e5扫描线8920e2941/2-5/2e31181/26/4e411130e5扫描线9920e292-5/2e311106/4e411130e511130e5扫描线1111136/4e411130e5扫描线12Polygonfill(EdgeTable ET,COLORREF color) 1.y=置y为边表ET中所有边的y 坐标中最小的值; 2.活跃边表AET初始化为空表; 3.若AET非空或ET非空，则做下列步，否则算法结束 3.1.将ET中相