基于橡皮筋划线后的多边形区域填充算法(有序边表)

如图对围出的多边形进行填充:
基于橡皮筋划线后的多边形区域填充算法(有序边表)
                                        图(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;//考虑端点情况,解决端点填充出界问题
                                   
            }

           
        }
   
上一篇:| dp-the Treasure Hunter


下一篇:SAP CRM AET Application Reference类型扩展字段的一个例子