带孔多边形填充算法

1、带孔多边形填充算法基本原理用自上而下的每一条水平的扫描线扫描多边形，每一条扫描线被多边形E几段，每段要么在多边形内，要么在多边形外。在内的填充，在外的舍弃。见图1二.基本算法1. 水平扫描线与线段求交点假定当前扫描线 y与多边形的某一条边的交点 x坐标为x,那么下一条扫描线y-1与该边的交点不必从头算起，只要加上一个增量即可。设增量为dx,显然dx= -（x1-xO）/（y1-yO）结果是：若 y=yi ,x=xi,则当 y=yi-1 时，x=Xi-（x1-xO）/（y1-yO）yy-i2. 活性边与活性边表为了提高效率，在处理一条扫描线时，仅对与它相交的多边形的边进行求交运算。我 们把与当前

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

3、（满足上闭下开的原则）。扫描线2的活性边表如下：P1P2 P2P3 （满足上闭下开的原则）。9 P4（11,8）图33. Y桶表为了方便活性边表的建立与更新，我们为每一条扫描线建立一个新边表，存放在该扫描线第一次出现的边。也就是说，若某边的较高端点为Ymax,则该边就放在扫描线Ymax的新边表中。这样，当我们按扫描线从大到小顺序处理扫描线时，该边在该扫描 线第一次出现。我们把这样的表称为Y桶表。例如，图3的多边形可以产生以下的Y桶表。Y max图4 : Y桶表三.数据结构/*多边形边表*/typedef struct LINEint y;/*边所交的最高扫描线号（顶点的最大y值）*/doubl

4、e x; /*当前扫描线与边的交点x值*/double dx;/*从当前扫描线到下一扫描线之间的x增量*/int dy;/*边的两个顶点的y差值=0*/struct LINE *next;/*下一条边 */LINE;/*Y桶表*/typedef struct Y_TUBint y;/*该桶最大值*/struct Y_TUB *next; /* 下一桶 */ struct LINE*line;/*该桶的边表 */Y_TUB;/*活性边表*/typedef struct EXP_LINEint y;/*当前扫描线*/struct LINE *line;/* 活性边 */EXP_LINE;四.算法步骤1. 首先生成如图4的多边形Y桶表2. 取Y桶的Ymax值最大的一桶（或第一桶）的边表作为活性边表。取该桶的丫 max为 第一条扫描线。3. 清除活性边表中的水平线（水平边出链）及 dy=0的边。4. 计算出交点序列，并按点列x坐标递增重排点列，由点列中奇数点依次连线到偶数 点（如1-2 , 3-4, 5-6），即可填充该扫描线所在行。注意在连线填充时，最右边 一点不要填充，以达到左闭右开的结果。5. 扫描线下移，即y=y-1;6. 修改当前活性边表，如果下一桶存在并且 y值等于下一桶的 Ymax ,则在活性边表后加入下一桶