多边形裁剪，通过矩形裁剪，去掉多边形的孔洞

std::vector<gpc_polygon*> splithole( double minX,double yMin,double maxX,double yMax,gpc_polygon &subject,gpc_polygon &clip)
{
	std::vector<gpc_polygon*> resultVec;
	//如果是多个part，那么怎么处理
	int i=0;
	int j=0;
	int nPos=0;
	std::vector<double> centeroidsX;
	std::vector<double> centeroidsY;
	std::vector<DFPoint>centeroid;
	int nParts=subject.num_contours;

	gpc_polygon *pReulst = new gpc_polygon();

	for(int k=0;k<nParts;k++)
	{
		//printf("%d",pShapeReadObject->panPartStart[k]);
		double sumX=0;
		double sumY=0;
		for(j=0;j<subject.contour[k].num_vertices;j++)
		{
			sumX+=subject.contour[k].vertex[j].x;
			sumY+=subject.contour[k].vertex[j].y;

		}
		double avgX=sumX/subject.contour[k].num_vertices;
		double avgY=sumY/subject.contour[k].num_vertices;
		centeroid.push_back(DFPoint(avgX,avgY,k));
	}
	std::sort(centeroid.begin(),centeroid.end());
	//水平方向的裁剪线，按照Y方向从小到大排序，值为Y轴值，首元素是
	//yMin，尾元素是yMax；
	std::vector<double> yClipLineVec;
	yClipLineVec.push_back(yMin - (1e-6));

	for(i=0;i<centeroid.size();i++)
	{
		double centerX = centeroid[i].x;
		double centerY=  centeroid[i].y;

		//计算排序前第i个是不是内环，内环其方向是逆时针方向
		//最好只裁剪内环的，而不是所有轮廓中心都作为裁剪线
		if(isClockWise(&subject.contour[centeroid[i].contour])==false)
		{
			//不是内环，说明不是洞，跳出处理,这一步需要谨慎处理，如果判断
			//内环不正确，可能需要所有中心点都处理一遍，即都裁剪一次
			//因此，把这句判断去掉，结果肯定正确，但是计算量会增加
			continue;
		};
		yClipLineVec.push_back(centeroid[i].y);
	}
	yClipLineVec.push_back(yMax+1e-6);


	if(yClipLineVec.size()<=2)
	{
		//不需要处理，没有发现任何洞
	}
	else
	{
		//开始裁剪，这里用的是最原始的裁剪，目前是按照，原始图，逐个区域裁剪，而不是针对剩下的
		//范围进行递归裁剪。可以改进，编译部分，同样有这个问题
		clip.num_contours=1;
		MALLOC(clip.hole, clip.num_contours * sizeof(int),
			"hole flag array creation", int);
		MALLOC(clip.contour, clip.num_contours
			* sizeof(gpc_vertex_list), "contour creation", gpc_vertex_list);

		clip.contour->num_vertices=4;
		MALLOC(clip.contour[0].vertex, clip.contour[0].num_vertices
			* sizeof(gpc_vertex), "vertex creation", gpc_vertex);

		for(i=0;i<yClipLineVec.size()-1;i++)
		{
			clip.contour[0].vertex[0].x = minX;
			clip.contour[0].vertex[0].y = yClipLineVec[i];

			clip.contour[0].vertex[1].x = maxX;
			clip.contour[0].vertex[1].y= yClipLineVec[i];

			clip.contour[0].vertex[2].x = maxX;
			clip.contour[0].vertex[2].y = yClipLineVec[i+1];

			clip.contour[0].vertex[3].x = minX;
			clip.contour[0].vertex[3].y=  yClipLineVec[i+1];

			gpc_polygon_clip(GPC_INT, &subject, &clip, pReulst);

			resultVec.push_back(pReulst);
		//	debug_out(&result);		
			//debug_out_mif(fpMif,fpMid,&result);
			//gpc_free_polygon(&result);
		}
	}
	gpc_free_polygon(&subject);
	gpc_free_polygon(&clip);  
}

//是否逆时针方向
bool isClockWise(double *pdx,double *pdy,int nNum)
{
	double dfSquare=0;
	//计算面积，对于交叉图形，可能不正确
	for(int i=0;i<nNum;i++)
	{
		double x1  =pdx[i];
		double y1  =pdx[i];
		double x2  =pdx[(i+1)%nNum];
		double y2  =pdx[(i+1)%nNum];
		double x3  =pdx[(i+2)%nNum];
		double y3  =pdx[(i+2)%nNum];

		//计算面积,带正负号
		dfSquare += (x1*y2   +   x2*y3   +   x3*y1   -   x1*y3   -   x2*y1   -   x3*y2)/2; 
	}
	return dfSquare>0;
}

 

 

 上面是GPC裁剪，去掉所有洞的代码，在GIS处理中经常遇到带孔的数据，有时需要把孔去掉。

isclockwise函数，用于判断是不是逆时针方向（函数名取错了），用的算法是：三角剖分一个多边形，按向量叉积计算并累加和，如果面积为正，那么是逆时针方向（即数学里称为正向，右手螺旋法则），如果是面积为负，那么顺时针方向（即反向）

 

去掉空洞的算法是：

   对所有空洞的中心点按Y方向排序，然后生成水平裁剪线，形成裁剪区域，执行裁剪算法。

 

AGG 也支持带洞的多边形填充。AGG也支持GPC裁剪算法，据说比GPC快10倍，当然，可能是因为使用的是屏幕坐标吧，而不是double类型的坐标

 

GIS中处理的面数据，还真不少是带洞的。