如图对围出的多边形进行填充:
图(1)
结果如下:
图(2)
填充利用到扫描线算法
扫描线算法基本思想:
用水平扫描线从上到下(从下到上)扫描多条首位相连的线段构成的多边形,每根扫描线与线段产生交点。将交点按x坐标排序两两一对作为端点,将其中的点进行填色。多边形扫描完毕后,颜色填充完成。
填充基本步骤:
1⃣️:求交点
2⃣️:交点排序
3⃣️:颜色填充
这里求交点方法很多,我使用的是以斜率的倒数作为增量的方法求扫描线与多边形的交点(此方法避免了多次求交运算,大大减少计算量)
观察上图多边形,这里以上图多边形为例建坐标系,如下图,简单介绍一下增量求交的算法,绿色代表扫描线
图(3)
例如现在扫描线1与多边形有一个交点p1,用增量的方法求交点p2的坐标,我们发现y轴方向坐标变化很简单直接加1,而x轴方向两坐标之间的区别就是p2.x = p1.x + 1/k(p1,p2),及两交点之间横坐标差值为所在直线斜率的倒数k(p1,p2)=(y2-y1)/(x2-x1).
从一般的直线表达式推导一下,假设多边形某条边所在的直线方程是:ax + by + c = 0,
扫描线yi和下一条扫描线yi+1与该边的两个交点分别是(xi,yi)和(xi+1,yi+1),
则可得到以下两个等式: axi + byi + c = 0 (等式 1)
axi+1 + byi+1 + c = 0 (等式 2)
由等式1可以得到等式3: xi = -(byi + c) / a (等式 3)
由等式2可以得到等式4: xi+1 = -(byi+1 + c) / a (等式 4)
由等式 4 – 等式3可得到: xi+1 – xi = -b (yi+1 - yi) / a
由于扫描线存在yi+1 = yi + 1的关系,
将代入上式即可得到:xi+1 – xi = -b / a 即△x = -b / a,是个常量(直线斜率的倒数。
下面利用适当的数据结构对多边形的边、点进行存储,首先介绍“活动边表”AET,AET中存储当前交点的横坐标 x,斜率的倒数(增量)△x,以及当前扫描线与多边形相交的边的最高点ymax。每条边都和扫描线有个交点,扫描线填充算法只关注交点的x坐标。每当处理下一条扫描线时,根据△x直接计算出新扫描线与边的交点x坐标,可以避免复杂的求交计算。一条边不会一直待在“活动边表”中,当扫描线与之没有交点时,要将其从“活动边表”中删除,判断是否有交点的依据就是看扫描线y是否大于这条边两个端点的y坐标值,为此,需要记录边的y坐标的最大值。
设置边表集的如下结构体:
typedef struct XET
{
float x;
float dx,ymax;
struct XET* next;
}AET,NET;
扫描线5对应的“活动边表”由P4P3 、P4P2组成对应的“活动边表”如下图:
图(4)
为了方便活动边表的建立与更新,我们为每一条扫描线建议一个“新边表”NET,新边表与活动边表之间的具体操作:当算法处理到某条扫描线时,将这条扫描线的“新边表”中的所有边逐一插入到“活动边表”中。
而建立“新边表”的规则就是如果某条边的较低端点(y坐标较小的那个点)的y坐标与扫描线y相等,则该边就是扫描线y的新边,应该加入扫描线y的“新边表”(内容与活性边表的内容一样 x △x ymax)。上例中各扫描线的“新边表”如下图所示:
图(5)
更新的例子:观察扫描线5 所对应的活动边表(图4),不难发现,对应的交点横坐标x正是上一个扫描线4对应AET节点的x +△x ,扫描线4所对应的交点横坐标为:1 、23/3 —>扫描线5所对应的交点横坐标为:(1+1)、(23/3 - 2/3)
AET NET初始化代码如下:
//初始化AET表,即初始化活跃边表
AET *pAET = new AET;
pAET->next = NULL;
//初始化NET表,即初始化边表
NET *pNET[1024];
for( i = MinY;i <= MaxY; i++ )
{
pNET[i] = new NET;
pNET[i]->next = NULL;
}
AET更新代码以及填充代码如下:
//建立并更新活性边表AET
for( i = MinY; i <= MaxY; i++ )
{
//i表示每一个扫描线
//计算新的交点x,更新AET
NET *p = pAET->next;
while( p != NULL )
{
p->x = p->x + p->dx;
p = p->next;
}
//更新后新AET先排序/
AET *tq = pAET;
p = pAET->next;
tq->next = NULL;
while( p != NULL )
{
while( tq->next != NULL && p->x >= tq->next->x )
{
tq = tq->next;
}
NET *s = p->next;
p->next = tq->next;
tq->next = p;
p = s;
tq = pAET;
}
//先AET表中删除ymax==i的结点,对多边形顶点的处理,将顶点排除在填充区间外,删除边的终点以平衡交点的奇偶个数
AET *q = pAET;
p = q->next;
while( p != NULL )
{
if( p->ymax == i)
{
q->next = p->next;
delete p;
p = q->next;
}
else
{
q = q->next;
p = q->next;
}
}
//扫描线遇到端点,将NET中的新点加入AET,并用插入法按X值递增排序
p = pNET[i]->next;
q = pAET;
while( p != NULL )
{
while( q->next != NULL && p->x >= q->next->x)
{
q = q->next;
}
NET *s = p->next;
p->next = q->next;
q->next = p;
p = s;
q = pAET;
}
//配对填充颜色
p = pAET->next;
while( p != NULL && p->next != NULL )
{
for(float j = p->x;j <= p->next->x; j++)
{
glVertex2i(static_cast<int>(j),i);
}
p = p->next->next;//考虑端点情况,解决端点填充出界问题
}
}