当y=8时的有效边表如下图所示：
2.3.3 边表
有效边表给出了扫描线和有效边交点坐标的计算方法，但是没有给出新边出现的
位置坐标。为了方便有效边表的建立与更新，就需要构造一个边表（Edge Table， ET），用以存放扫描线上多边形各条边的信息。由于水平边的1/k为∞，并且水平边本身就是扫描线，所以在建立边表时不予考虑。
边表的构造分为4个步骤：
6
① 首先构造一个纵向链表，链表的长度为多边形占有的最大扫描线数，链表的每
个结点，称为一个桶，对应多边形覆盖的每一条扫描线。
② 将每条边的信息装入与该边最小y坐标(ymin)相对应的桶中。也就是说，若某
边的较低端点为ymin，则该边就放在相应的y=ymin的扫描线桶中。
③ 每条边的数据形成一个结点，内容包括该扫描线与该边的初始交点x(即较低
端点的x坐标值)，该边最大y坐标值ymax，以及斜率的倒数1/k和下一个边结点的指针next:
④ 同一桶中若干条边按x|ymin由小到大排列，若x|ymin相等，则按1/k由小到大排
序。
从上面可以看出，边表是有效边表的特例，有效边表和边表可以使用同一个数据
结构来表示。
对于多边形P0P1P2P3P4P5P6，它的边表结构如下图所示：
7
三、详细设计
3.1 改进的有效边表算法的实现
改进的有效边表算法具体实现过程如下： ① 初始化边表ET。
为了方便边表的建立，可以定义sort()函数对多边形的边进行排序，保证边表中每个桶中的边是有序的。同时定义一个creat_edge_table()函数，该函数需要多边形的顶点信息作为参数传入，并返回一个边表指针。
② 初始化有效边表AET。从ET表中取出第一个不为空的桶与AET表合并。
为了初始化AET表，可以定义一个init_active_table()函数，该函数传入边表指针作为形参，返回一个有效边表指针。 ③ 从AET表中取出交点进行填充。
填充时设置一个布尔值b（初值为假），令指针从有效边表的第一个结点（也就是扫描线与有效边的交点）开始遍历。每访问一个结点，把b取反一次。若b为真，则把从当前结点的x值开始（设为x1）到下一结点的x值结束(设为x2)的区间[x1, x2]用多边形色填充。填充时为了避免多边形区域扩大化，需要对区间边界进行如下处理：
若x是整数，则按“左闭右开”的原则处理，即左边界上的x（x1）不变，右边界上的x（x2）减1；若x不是整数，左边界上的x（x1）向右取整，右边界上的x（x2）向左取整。 ④ 更新AET表。
设当前AET表中扫描线为y，首先更新扫描线为y=y+1，然后删除AET表中所有ymax=y的边结点；再根据xi+1=xi+1/k计算并修改AET表中各边结点的x坐标，同时合并ET表对应于扫描线y的桶中的边，按次序插入到AET表中，形成新AET表。此步骤满足多边形的“下闭上开”原则。
此过程用到自定义的函数update_active_table()。
⑤ 判断AET表是否为空。若为空，则结束；否则转到③
8
delete_edge()、add_edge()、
3.2 有效边表算法程序流程图
开始输入多边形顶点信息AET是否为空构造边表是结束否ET取出交点进行填充初始化有效边表AET更新AET表
四、测试结果
为了便于观察多边形的填充，本程序将像素点进行放大处理，400 x 300的分辨率投影到20 x 15，并绘制出网格，使用OpenGL画出多边形的边框。使用了Sleep()函数来延时生成像素点，并且每填充一个像素点刷新一次，给人动态直观的感受。
① 在不处理边界的情况下，如下图所示，多边形的区域可能会扩大化。
9
② 对边界进行处理后，结果如下：
10
计算机图形学课程设计有效边表填充算法的实现
