OpenGL研究3.0 多边形区域填充

DionysosLai(906391500@qq.com)2014-06-22

         所谓多边形区域填充，就是将多边形内部区域，全部已同样色块填充。注意：这里讨论的多边形是简单多边形（即不考虑诸如五角星这种相交多边形）。简单多边形，分为凹多边形和凸多边形。

         多边形区域填充有以下几种方法：

1.      逐点扫描方法：

         原理：扫描多边形区域，逐点判断点是否在多边形内。

         难点：在于如何判断点是否在区域内;

         常用如何判断点是否在区域内方法：射线法、面积法。

         面积法原理:取一个点，连接多边形各个点，根据三个点形成一个三角形原理，我们可以求得三角形面积，判断面积的大小，就可以判断该店是否在多边形内了。

         射线法：这个方法，是我们这里要重点讲解的一个方法。原理：取一个点，向左或者向右做一条射线过去，判断射线与多边形的交点，根据多边形交点熟练和本身多边形边情况，判断点是否在多边形内。

         首先，射线从左向右，最左边点肯定在多边形区域为（我们这里假定射线方向水平向左），那么与多边形相交第一个点，必然表明射线右部分在多变形内，与多边形相交第二个点，表明射线右部分在多边形外面。因此，通过判断射线与多变的交点奇偶性，判断点是否在多边形内。

         这里，有几种特殊情况，如下图所示：

         图a，射线与多变形顶点相交，顶点算一个；图b，射线与多边形顶点的交点，不被计算在内（注意图a和图b的区别->顶点纵坐标大小区别）；图c和图d，射线与多边形一条边重合，这条边被忽略不计。

         因此，我们可以设计如下：取点向左做一条射线，1. 对于水平边不做考虑；2. 对于多边形顶点与射线交点情况，如果其纵坐标是所属边较大顶点，则计数（参考图a），否则不计数（图b）；3.对于点在多边形上情况，可直接判断点在多边形内。

         伪代码如下：

count ← 0;
以P为端点，作从右向左的射线L; 
for 多边形的每条边s
 do if P在边s上 
	  then return true;
	if s不是水平的
	  then if s的一个端点在L上
			 if 该端点是s两端点中纵坐标较大的端点
			   then count ← count+1
		   else if s和L相交
			 then count ← count+1;
if count mod 2 = 1 
  then return true;
else return false;

         相应代码如下：注：我是在coco2dx2.3版本内测试的，因此可能移植要改些类名。

///@brief 判断点是否在多边形
///@param[in] p0--要判断点， poly--多边形点集合， numberOfPoints--多边形点数量
///@return 2---点在多边形内， 1---点在多边边上，0---点不在多边形内
///@author DionysosLai,906391500@qq.com
///@retval 
///@post
///@version 1.0
///@data 2014-04-11
int HelloWorld::pointIsInPolygon(const CCPoint& p0, const CCPoint* poly, const unsigned int numberOfPoints)
{
	unsigned int count  = 0;		///< 用来标记射线L与多边形的交点数；
	CCSize	winsize = CCDirector::sharedDirector()->getWinSize();
	/// 已点p0向左向右做一条射线L；
	CCPoint leftPoint = ccp(-100.0f, p0.y);
	CCPoint rightPoint = ccp(winsize.width+100.0f, p0.y);

	/// 判断每条边
	for (unsigned int i = 0; i < numberOfPoints-1; i++)
	{
		/// 先判断点p0是否在边s上；
		if (pointIsAtLine(p0, poly[i], poly[(i+1)%(numberOfPoints)]))
		{
			CCLOG("Point is at the %dth line", i);

			return 1;
		}

		/// 判断边s是否是平行线；
		if (poly[i].y != poly[(i+1)%(numberOfPoints)].y)
		{		
			do 
			{
				/// 判断边s的是否有端点在L上 同时 再判断该点是否是边s纵坐标较大的一个点
				if (pointIsAtLine(poly[i], leftPoint, rightPoint))
				{
					if (poly[i].y > poly[(i+1)%(numberOfPoints)].y)
					{
						count += 1;
					}
					break;
				}	
				if (pointIsAtLine(poly[(i+1)%(numberOfPoints)], leftPoint, rightPoint))
				{
					if (poly[i].y < poly[(i+1)%(numberOfPoints)].y)
					{
						count += 1;
					}

					break;
				}	

				/// 如果边s没有端点在L上，则判断s与L是否相交
				if (segmentLineIsIntersect(leftPoint, rightPoint, poly[i], poly[(i+1)%(numberOfPoints)]))
				{
					count += 1;
				}	
			} while (0);
		}
	}

	if (1 == count%2)
	{
		CCLOG("Point is not in polygon!");
		return 0;
	}
	else
	{
		CCLOG("Point is in  polygon!");
		return 2;
	}
}

         这里有个pointIsAtLine，是用来判断点是否在边上函数；segmentLineIsIntersect，是用来判断两条线段是否相交函数。可参考我的另一边博文：http://blog.csdn.net/dionysos_lai/article/details/24418697计算几何文档一系列文章（目前只写了一篇，实际上是差不多写了常用几何算法，还没写成博文。怪楼主太懒了。）

         Ok，逐点扫描判断方法就是差不都这样了。

2.       扫描线算法

         逐点扫描算法，没有充分考虑到像素之间的连贯性，效率低。扫描线算法，就是要利用像素之间的连贯性，提高算法效率。

         所谓连贯性：有三个概念，1.边的连贯性，AB边与扫描线1相交，也可能与扫描线2相交；2.扫描线连贯性：当前扫描线与多边形边交点顺序，可能与下一条扫描线交点情况一致或者类似；3.区间连贯性：同一区间像素取同一颜色属性。

         扫描线原理：将整个多边形区域扫描问题分解到一条条扫描线问题，只要完成每条扫描线的绘制，就实现了多边形区域填充问题。一条扫描线与多边形有偶数个交点（0就不算了），按顺序每2个点形成一个区间，只要绘制这个区间即可。

         难点这与扫描线与多边形边交点判断，这个是高中问题了，通过线段一般方程ax+by+c=0,两立方程求解。不过这种方法，要计算各种参数，比较费时，更好的方法是分成各种情况分开讨论（虽然比较麻烦），可以关注我的《计算几何算法》系类文章。