凸包问题之蛮力解法

static void CalculateConvexHull(struct Point *pArray,int length)
{
	for(int x=0;x<length;x++) {
		if(mark[x])
			continue;
		for(int y=0;y<length;y++) {
			if(x==y || mark[y])
				continue;
			for(int z=0;z<length;z++) {
				if(x==z || y==z || mark[z])
					continue;
				for(int i=0;i<length;i++) {
					if(x==i || y==i || z==i || mark[i])
						continue;
					//在三角形内
					if(PointIsInner(pArray[x],pArray[y],pArray[z],pArray[i]))
						mark[i]=true;
				}
			}
		}
	}
}

/* 打印凸包点 */
void PrintConvexHull(struct Point *pArray,int &length)
{
	using std::cout;
	using std::endl;
	CalculateConvexHull(pArray,length);

	//凸包点缓冲区
	Point *tmp=new Point[length];
	int j=0;
	for(int i=0;i<length;i++) {
		if(!mark[i]) {
			cout<<pArray[i].x<<","<<pArray[i].y<<endl;
			tmp[j++]=pArray[i];
		}
	}
	//更新
	memcpy(pArray,tmp,sizeof(struct Point)*j);
	length=j;
}

#define edge(p1,p2) \
	sqrt(pow((double)(p1.x-p2.x),2)+pow((double)(p1.y-p2.y),2))

/* 是否在一条直线上 */
#define isOneLine(p1,p2,p3) \
	((double)(p2.y-p1.y)/(p2.x-p1.x)) - ((double)(p3.y-p2.y)/(p3.x-p2.x))

/* 计算三角形面积 */
static double TrangleArea(Point p1,Point p2,Point p3)
{
	//三点垂直共线
	if(p1.x==p2.x==p3.x)
		return 0;
	else if(p1.x!=p2.x || p1.x!=p3.x ||p2.x!=p3.x) {
		if(abs(isOneLine(p1,p2,p3))<0.000001)
			return 0;
	}
	double p1p2=edge(p1,p2);
	double p1p3=edge(p1,p3);
	double p2p3=edge(p2,p3);
	//海伦公式
	return Halen(p1p2,p1p3,p2p3);
}

/* 点是不是在三角形内 */
bool PointIsInner(Point p1,Point p2,Point p3,Point unknownP)
{
	//大三角形面积
	double a=TrangleArea(p1,p2,p3);
	//三个小三角形面积
	double a1=TrangleArea(p1,p2,unknownP);
	double a2=TrangleArea(p1,p3,unknownP);
	double a3=TrangleArea(p2,p3,unknownP);
	if(a==0 || a1==0 || a2==0 || a3==0)
		return false;
	//在三角形内部
	if(abs(a1+a2+a3-a)<0.000001)
		return true;
	return false;
}