多边形扫描线填充算法简单剖析（Scan-Line Filling）

   推荐博客：YangKang`s Blog

 

    很久一段时间没有更新自己的博客了，这期间的确很压抑，深深的陷入了一个矢量图填充的项目中。当多件事牵连在一起的时候，真一种捉襟见肘的感觉。不管怎样，也算是失之东隅，收之桑榆吧。

 

一、算法简析：

扫描线填充算法的基本思想是：用水平扫描线从上到下（或从下到上）扫描由多条首尾相连的线段构成的多边形，每根扫描线与多边形的某些边产生一系列交点。将这些交点按照x坐标排序，将排序后的点两两成对，作为线段的两个端点，以所填的颜色画水平直线。多边形被扫描完毕后，颜色填充也就完成了。扫描线填充算法也可以归纳为以下4个步骤：

（1）求交点。即扫描线和多边形的交点。

（2）交点排序。

（3）对排序后的点两两匹配。

（4）更新扫描线，判断是否完成多边形扫描。

 

算法的关键是第一步，求交点 。

如上图，可以发现多边形与扫描线的交点有如下 二个特点：

（1） 每次只有相关的几条边可能与扫描线有交点，不必对所有的边进行求交计算；

（2）相邻的扫描线与同一直线段的交点存在步进关系。

 

 

        第一个特点是显而易见的，为了减少计算量，扫描线算法需要维护一张“活动边Active Edge组成的表，称为“活化边表Active Edge Table（AET）”。例如扫描线4的“活化边表”  p1p2和p3p4两条边组成。

      第二个特点，可以进步证明：假设当前扫描线与多边形的某一条边的交点已经通过直线段求交算法计算出来，得到交点的坐标为（x, y），则下一条扫描线与这条边的交点不需要再求交计算，通过步进关系可以直接得到新交点坐标为（x + △x, y + 1）。△x为y增加1个单位时，x增加的单位。即多边形边界的斜率的倒数。

 

    总而言之，言而总之，“活动边表”是扫描线填充算法的核心，保证了填充时不需太多的求交点运算。为了方便活性边表的建立与更新，还需要建立一个边表NET（New Edge Table）来存放所有的边。

 

    再来讨论边的数据结构：扫描线填充算法只关注交点的x坐标，即交点的横坐标；处理下一条扫描线交点时，根据 △x直接得出；还需要边的最大y坐标y_max作为活边表和扫描结束的判断依据；了便于插入和修改，定义为链表结构。

 

    所以，我们定义边的数据结构如下，AET和NET的基本类型均为边类型Edge。

 

typedef struct tagEdge{
	int y_max;     // 边的最大y坐标
	float x;       // 与扫描线交点x坐标
	float dx;      // 斜率的倒数，Δx
	Edge * pNext;  // 下一条边
} Edge;

 

 

    边表NET是根据每条边的y_max为索引边类型Edge数组。看到这个结构是不是非常像HashMap。没错，这就是一个哈希表。但对其对象操作相当繁琐。

 

上图的多边形建立的NET如下：

 

   活化边表AET是根据NET中的所有边Edge类型的y_max进行判断，可能相交的直线添加到AET。如上图形的AET如下： 

 

接下来就是直接扫描处理了，将的得到的点两两连线。 

 

二、代码实现

 

//扫描线填充算法
CPtrArray & CShapeFiller::scanLineFill(CPtrArray &m_tranArrShape){
	CPtrArray *pArr = new CPtrArray();
	
	float y_max = (float)INT_MIN;    // y坐标值的最大值
	float y_min = (float)INT_MAX;    // y坐标值的最小值

	//获取y坐标值最大和最小值
	GetYMaxMin(y_max, y_min);

	//最大最小值取整
	int iy_max = (int)y_max;
	int iy_min = (int)y_min;

	//y_max	取整的误差
	float y_deviation = y_min - (float)iy_min;

/* -------------------------- 定义边表NET及活化边表AET ---------------------- */
	//活化边表AET:元素与当前扫描线相交  基本元素：边Edge. 
	//边表NET: 按边的下端点的Y坐标对非水平的边指针数组
	Edge *pAET=NULL;    // 活化边表的表头指针
	Edge **pNET=NULL;   // 边表的表头指针

	pAET = new Edge();  //初始化活动表头指针，第一个元素不用
	pAET->pNext = NULL;

/* ---------------------- 初始化边表NET --------------------------- */

	//边表NET数组的长度 
	int length = (iy_max-iy_min); 

	// 初始化边表NET，第一个元素不用
	pNET=new Edge*[length + 1];

	//初始化边表NET中的每一个指针元素，赋予内存空间
	for(int i = 0;i <= length;i++)
	{
		pNET[i] = new Edge();
		pNET[i]->pNext = NULL;
	}

	//将所有的边添加到NET边表中
	CreateNET(pNET,iy_min);
   
/* --------------------------- 扫描线填充 ----------------------- */
	// 扫描线填充，从最小y坐标开始扫描，下闭上开
	for(int i=iy_min;i < iy_max;i += 1)
	{
		//活动边表AET的头指针
		Edge *pEdgeFirst=pNET[i-iy_min];

		//初始化活化边表AET
		InitializeAET(pEdgeFirst,pAET);

		//对当前AET活化边表进行X坐标值升序排序
		SortAcendX(pAET);

		//添加间距参数判断
		//若间距为0 ，不填充
		if (lineSpacing ==0)
		{
			for(int i=0;i <=length;i++)
				if(pNET[i])
					delete pNET[i];

			if(pAET) 
				delete pAET;
			if(pNET)
				delete[] pNET; 

			//释放指针申请的内存空间
			m_tranArrShape.RemoveAll();
			return pArr;
		}
		else
		{  
			//间距不为0，填充实现
			if(i%lineSpacing==0)
			{
				
				// 遍历活边表，将坐标点存入CPtrArray对象中
				SavePoints(pAET,i,*pArr,y_deviation,x0,y0);
			}

		}

		// 更新扫描线
		UpdateScanLine(pAET,i);

	}

	// 删除边表
	for(int i=0;i <=length;i++)
		if(pNET[i])
			delete pNET[i];

	if(pAET) 
		delete pAET;
	if(pNET)
		delete[] pNET; 

	//释放指针申请的内存空间
	m_tranArrShape.RemoveAll();

	return *pArr;
}

 

 

    由于该项目有一定的特殊性，故洒家在此就不提供每个函数的详细代码。如需了解，欢迎一起交流。

 

三、问题解析

    然后，在此过程中遇到很多一个比较大的问题。当扫描线经过多边形顶点时，会出现缺填充或者误填充嗯的问题。

 

当时是想着判断交点奇偶性，上下顶点对填充没有影响，但是左右顶点对填充会有较大的影响。

 

左右顶点判断（逆时针为正）

左顶点――P1、P2和P3的y坐标满足条件：y1 < y2 < y3；

 

右顶点――P1、P2和P3的y坐标满足条件：y1 > y2 > y3；

 

左右顶点修正：

    对于左顶点的情况，采用的修正方法是修改以左顶点为终点的那条边的区间，将顶点排除在区间之外，也就是删除这条边的终点，这样在计算交点时，就可以少计算一个交点，平衡和交点奇偶个数。结合前文定义的“边”数据结构：AET，只要将该边的y_max修改为y_max – 1就可以了。右顶点不处理，左开右闭的策略。

  

   然而，这样虽然能够解决大多数的顶点缺填问题，但是对于几个左右顶点连续排列在一条水平线上时，会出现误填。

 

改进的算法：

   后来意识到扫描的基本思想的在图形的内部填充，填充图形也在图形内部，改进的算法是直接判断得到的两两匹配的点连成的线段是否在图形内部。从而，这个问题得到了完好的解决。

 

   以上算法的都是水平线填充，其实斜线填充经过坐标的一系列的平移旋转变换，最终也可以用以上的算法实现。 同时还要注意阈值处理，浮点型数据的精度问题。 

 

四、总结

    有时候，我们可能看到一些现象，遇到一些问题，形象化给我们的解决方案是：针对这些现象去解决这些问题，然后先天地给予各种前提，假设种种情景，然后经过这种自以为的这种逻辑判断，最后检验其正确性，殊不知，有些事情是设想之外的，或者说前提有无穷多。前提都不成立，结果又何从可信。正如扫描线相交于多边形顶点，单一顶点处理可能会解决所有问题，但任意的顶点组合怎么办呢？ 透过现象看本质，也许就会发现起初的前提只是冰山一角，

九牛一毛而已。透过浮云才能与真理的光芒相拥。

 

 

评论

4 楼 什么世道 2014-03-31  

发条源 写道

能留个联系方式吗？QQ什么的，新手求教，想请教你些问题~谢谢啦~

QQ:1009425612

3 楼 发条源 2014-03-25  

能留个联系方式吗？QQ什么的，新手求教，想请教你些问题~谢谢啦~

2 楼 什么世道 2014-01-27  

谢谢，美女过奖了。

GLC 写道

帅哥挺不错啊

1 楼 GLC 2014-01-27  

帅哥挺不错啊