多边形扫描转换算法的改进

X-扫描转换算法效率低下，主要原因时求交。为避免求交运算，需引进特殊得数据结构。

可以从三个方面考虑加以改进：

1、在处理一条扫描线时，仅对与它相交的多边形的边（有效边）进行求交运算

2、考虑扫描线的连贯性：即当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序很可能相同或非常相似

3、多边形的连贯性：即当某条边与扫描线相交时，它很可能也与下一条扫描线相交

数据结构：

1、活性边表（AET）：把与当前扫描线相交得边称为活性边，并把它们按与扫描线交点x坐标递增得顺序存放在一个链表中。

2、结点内容（一个结点在数据结构里可用结构来表示）

x：当前扫描线与边得交点坐标

Δx：从当前扫描线到下一条扫描线间x得增量

ymax：该边所交的最高扫描线的坐标值ymax

next：指向下一个结点

随着扫描线的移动，扫描线与多边形的交点和上一次交点相关：

设边的直线斜率为k：

即Δx=1/k

另外，需要知道一条边何时不再与下一条扫描线相交，以便及时把它从有效边表中删除出去，避免下一步进行无谓的计算

例：

此时活性链表为：

为了方便活性边表的建立与更新，需构造一个新边表（NET），用来存放多边形的边的信息：

1、首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点称为一个吊桶，对应多边形覆盖的每一条扫描线

2、NET挂在与该边最低端y值相同的扫描线桶中。即存放在该扫描线第一次出现的边

ymax：该边最大的y值

xmin：该边较低点的x坐标值

1/k：该边的斜率

next：指向下一条具有相同较低端y坐标的边的指针

上图的NET为：

从这个NET表里可知多边形是从哪里开始的，在这个表中只有1，3，5，7处有边，从y=1开始做，而在1这条线上有两条边进来了，然后就把这两条边放进活性边表来处理

每做一次新的扫描线时，要对已有的边进行三个处理：

1、是否被去除掉

2、如果不被去除，第二就要对它的数据进行更新。所谓更新数据就是更新x值，即：x+1 / k

3、看是否有新的边进来，新的边在NET里，可插入排序插进来

void polyfill (polygon, color)
    int color; 多边形polygon;
    { for (各条扫描线i )
        { 初始化新边表头指针NET[i]；
          把ymin = i 的边放进边表NET[i];
         }
       y = 最低扫描线号；
       初始化活性边表AET为空；
       for (各条扫描线i )
       {
           把新边表NET[i] 中的边结点用插入排序法插入AET表，使之按x坐标递增顺序排列；
           遍历AET表，把配对交点区间(左闭右开)上的象素(x,y)，用putpixel(x,y,color) 改写象素颜色值；
           遍历AET表，把ymax= i 的结点从AET表中删除，并把ymax>i
           结点的x值递增x；
           若允许多边形的边自相交，则用冒泡排序法对AET表重新排序；
       }
} /* polyfill */

多边形扫描转换算法的缺点时无法实现对未知边界的区域填充