带孔多边形填充算法

带孔多边形填充算法
一． 基本原理
用自上而下的每一条水平的扫描线扫描多边形，每一条扫描线被多边形分成几段，每
一段要么在多边形内，要么在多边形外。在内的填充，在外的舍弃。见图1

图1
二． 基本算法
1. 水平扫描线与线段求交点
假定当前扫描线y与多边形的某一条边的交点x坐标为x,那么下一条扫描线y-1与该
边的交点不必从头算起，只要加上一个增量即可。设增量为dx,显然dx= -(x1-x0)/(y1-y0)
结果是：若y=yi ,x=xi,则当y=yi-1时，x=xi-(x1-x0)/(y1-y0)

图2
2. 活性边与活性边表
为了提高效率，在处理一条扫描线时，仅对与它相交的多边形的边进行求交运算。我
们把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在
一个链表中，称此链表为活性边表。
由于边的连贯性（即当某条边与当前扫描线相交时，它很可能也与下一条扫描线相
交），以及扫描线的连贯性（当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺
序很可能相同或非常类似），在当前扫描线处理完毕之后，我们不必为下一条扫描线从头开
始构造活性边表，而只要对当前扫描线的活性边表稍作修改，即可更新得到下一条扫描线的
活性边表。
例如,(见图3)
扫描线6的活性边表如下：P6P1 P6P5 P5P4 P4P
3

扫描线4的活性边表如下：P6P1P4P3

扫描线3的活性边表如下：P6P1P3P2 (满足上闭下开的原则)。
扫描线2的活性边表如下：P1P2P2P3 (满足上闭下开的原则)。

y-1
(x0,y0)
(x1,y1)
y
dx
1
图3
3．Y桶表
为了方便活性边表的建立与更新，我们为每一条扫描线建立一个新边表，存放在
该扫描线第一次出现的边。也就是说，若某边的较高端点为Ymax,则该边就放在扫描线
Ymax的新边表中。这样，当我们按扫描线从大到小顺序处理扫描线时，该边在该扫描
线第一次出现。我们把这样的表称为Y桶表。
例如，图3的多边形可以产生以下的Y桶表。

图4 : Y桶表
三．数据结构
/*多边形边表*/
typedef struct LINE{
int y; /*边所交的最高扫描线号(顶点的最大y值)*/
double x; /*当前扫描线与边的交点x值*/
double dx; /*从当前扫描线到下一扫描线之间的x增量*/
int dy; /*边的两个顶点的y差值>=0*/
struct LINE *next; /*下一条边*/
}LINE;

y
0
1 2 3 4 5 6 7 8 9 10 11
1
2
3 4 5 6 7 8 9 P2(5,1) P1(2,2) P3(11,3)
P4(11,8)

P5(5,5)
P6(2,7)

x

8 7 3 2 P4P5 P4P3
P6P1 P6P5
P3P2
P1P2

Ymax
/*Y桶表*/
typedef struct Y_TUB{
int y; /*该桶最大值*/
struct Y_TUB *next; /*下一桶*/
struct LINE *line; /*该桶的边表*/
}Y_TUB;

/*活性边表*/
typedef struct EXP_LINE{
int y; /*当前扫描线*/
struct LINE *line; /*活性边*/
}EXP_LINE;

四．算法步骤
1． 首先生成如图4的多边形Y桶表
2． 取Y桶的Ymax值最大的一桶（或第一桶）的边表作为活性边表。取该桶的Ymax为
第一条扫描线。
3． 清除活性边表中的水平线（水平边出链）及dy=0的边。
4． 计算出交点序列，并按点列x坐标递增重排点列，由点列中奇数点依次连线到偶数
点（如1-2，3-4，5-6 …），即可填充该扫描线所在行。注意在连线填充时，最右边
一点不要填充，以达到左闭右开的结果。
5． 扫描线下移，即y=y-1;
6． 修改当前活性边表，如果下一桶存在并且y值等于下一桶的Ymax ,则在活性边表后加
入下一桶的边表（下一桶边表入链）。
7． 重复3-6步，直到当前活性边表为空。
(注：该算法由于最后一条扫描线使活性边的dy=0而不处理，这就产生了上闭下开的结
果)