基本思想：

用水平扫描线从上到下（或从下到上）扫描由多条首尾相连的线段构成的多边形，每根扫描线

与多边形的某些边产生一系列的交点。将这些交点按照x坐标排序，将排序后的点两两配对，作

为线段的两个端点，以所填的颜色画水平直线。

步骤

1.求交，计算扫描线与多边形的交点。

2.交点排序，对第1步得到的交点按照x从小到大排序

3.颜色填充，对排序后的交点两两组成一个水平线段，以画线段的方式进行颜色填充。

4.完成多边形扫描，就结束算法，否则，继续1

 有效边

多边形与当前扫描线相交的边成为有效边(active edge)。在处理一条扫描线时仅对有效边进行

求交运算，避免与多边形所有边求交，提高效率。

x ymax 1/k next

桶表与边表

有效边给出了扫描线与有效边交点的计算方法，但没有给出新边出现的位置坐标。为了确定在

哪条扫描线上加入了新边，就需要构造一个边表（edge table ET),用以存放扫描线上多边形各

条边出现的信息。水平边本身就是扫描线在建立边表时可以不予考虑。

桶表与边表的表示法

桶表是按照扫描线顺序管理边出现的一个数据结构。首先，构造一个纵向扫描线链表，链表的

长度为多边形所占有的最大扫描线数，链表的每个节点称为桶(bucket）,对应多边形覆盖的每一

条扫描线。

将每条边的信息链加入该边最小y坐标对应的桶处。

对每一条扫描线，如果新增多条边，按照x|ymin 坐标递增的顺序存放在一个链表中，若x|ymin 相等，

则按照1/k递增，就形成边表。

x|ymin ymax 1/k

next