带孔多边形填充算法

《带孔多边形填充算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、带孔多边形填充算法一．基本原理用自上而下的每一条水平的扫描线扫描多边形，每一条扫描线被多边形分成几段，每一段要么在多边形内，要么在多边形外。在内的填充，在外的舍弃。见图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)(x0,y0)y11y-1dx(x1,y1)图22.活性边与活性边表为

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

3、P1àP6P5àP5P4àP4P3扫描线4的活性边表如下：P6P1àP4P3扫描线3的活性边表如下：P6P1àP3P2(满足上闭下开的原则)。扫描线2的活性边表如下：P1P2àP2P3(满足上闭下开的原则)。P4(11,8)9yP6(2,7)8765P5(5,5)4P3(11,3)3P2(5,1)2P1(2,2)111109876543210x图33．Y桶表为了方便活性边表的建立与更新，我们为每一条扫描线建立一个新边表，存放在该扫描线第一次出现的边。也就是说，若某边的较高端点为Ymax,则该边就放在扫描线Ymax的新边表中。这样，当我们按扫描线

4、从大到小顺序处理扫描线时，该边在该扫描线第一次出现。我们把这样的表称为Y桶表。例如，图3的多边形可以产生以下的Y桶表。Ymax8732P4P5P4P3P6P1P6P5P3P2P1P2图4:Y桶表一．数据结构/*多边形边表*/typedefstructLINE{inty;/*边所交的最高扫描线号(顶点的最大y值)*/doublex;/*当前扫描线与边的交点x值*/doubledx;/*从当前扫描线到下一扫描线之间的x增量*/intdy;/*边的两个顶点的y差值>=0*/structLINE*next;/*下一条边*/}LINE;/*Y桶表*/ty

5、pedefstructY_TUB{inty;/*该桶最大值*/structY_TUB*next;/*下一桶*/structLINE*line;/*该桶的边表*/}Y_TUB;/*活性边表*/typedefstructEXP_LINE{inty;/*当前扫描线*/structLINE*line;/*活性边*/}EXP_LINE;一．算法步骤1．首先生成如图4的多边形Y桶表2．取Y桶的Ymax值最大的一桶（或第一桶）的边表作为活性边表。取该桶的Ymax为第一条扫描线。3．清除活性边表中的水平线（水平边出链）及dy=0的边。4．计算出交点序列，并按点

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