凸包问题之蛮力解法

chain

发布于 2018-08-02 14:53:08

1.6K0

文章被收录于专栏：开发 & 算法杂谈开发 & 算法杂谈

凸包问题

首先解释什么叫做凸包问题：

1 　点集Q的凸包（convex hull）是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。下图中由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。

2 　一组平面上的点，求一个包含所有点的最小的凸多边形，这就是凸包问题了。这可以形象地想成这样：在地上放置一些不可移动的木桩，用一根绳子把他们尽量紧地圈起来，并且为凸边形，这就是凸包了。

来自百度百科http://baike.baidu.com/view/707209.htm?fr=aladdin

首先解决凸包问题是用蛮力解决的，从图上可以很明显的看出，每个凸包点构成的三角形任意一点都不在任意三点构成的三角形内部（如果有的话，那么这个点就不是凸包点）

按照这个原理，我们就很容易的想到用四层循环解决问题

前三层用来选择三个点，最后一层用来筛选出不是凸包点（一个点在三角形内部，用面积或是其他数学知识可解决）

需要注意的是前三层选择点的时候，需要避开相同点和已经是凸包内部的点

非常简单、直接的算法，贴出部分代码（详细代码见底部链接）

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;
}

PointIsInner函数用来判断点是不是在三角形内部

#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;
}

主要函数都以贴出，供大家享用，下一篇讲解凸包GrahamScan解法。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2014年12月07日，如有侵权请联系 cloudcommunity@tencent.com 删除

人工智能