凸包问题之GrahamScan解法

/* 计算凸包 */
void CalculateConvexHull2(struct Point *pArray,struct Polar *prArray,int length)
{
	//初始化
	InitializePolarCoordinates(pArray,prArray,length);

	struct Polar *start=prArray;

	//栈中最上面的两个点 
	struct Polar *p1=NULL,*p2=NULL;
	top=0;
	
	//最小的三个点压栈

	stack[top++]=start++;
	stack[top++]=start++;
	stack[top++]=start++;	

	while(start!=prArray+length) {
		//获取p1和p2
		p2=stack[top-1];
		p1=stack[top-2];

		//右转，弹出p2,压入p1
		while(IsRightTuring(start->p,p2->p,p1->p) > 0 ) {
			if(top<=2)
				break;
			top--;
			p2=stack[top-1];
			p1=stack[top-2];
		}

		//压入新的点
		stack[top++]=start++;
	}
	
}

/* 打印凸包点 */
void PrintConvexHull2(struct Point *pArray,struct Polar *prArray,int &length)
{
	CalculateConvexHull2(pArray,prArray,length);

	using std::cout;
	using std::endl;

	for(int i=0;i<top;i++) {
		cout<<stack[i]->p->x<<","<<stack[i]->p->y<<endl;
	}
	//更新长度
	length=top;
}

/* 排序选择Y轴最低的坐标点作为极坐标中心 */
static struct Point ChooseCentroid(struct Point *pArray,int length)
{
	qsort(pArray,length,sizeof(struct Point),PointYCompare);
	return pArray[0];
}

/* 直角坐标转化为极坐标 */
void PointToPolar(struct Point * ptArray,struct Polar *prArray,int length,struct Point centroid)
{
	for(int i=0;i<length;i++) {
		//在极坐标横轴上
		if(ptArray[i].y==centroid.y) {
			if(ptArray[i].x>=centroid.x)
				prArray[i].angle=0;
			else
				prArray[i].angle=180;
		}
		//90度
		else if(ptArray[i].x==centroid.x)
			prArray[i].angle=90;
		//其他
		else
			prArray[i].angle=arctan(ptArray[i],centroid);

		//长度暂时不用

		//指针指向
		prArray[i].p=&ptArray[i];
	}
}

/* 初始化极坐标系 */
static void InitializePolarCoordinates(struct Point *pArray,struct Polar *prArray,int length)
{
	//找极坐标中心
	struct Point centroid=ChooseCentroid(pArray,length);

	//直角坐标转化为极坐标
	PointToPolar(pArray,prArray,length,centroid);

	//极坐标排序
	PolarQuickSort(prArray,0,length-1);
}