凸包问题

凸包问题是计算机几何中的一个典型问题

凸包问题的定义就是在平面上n个点组成的集合，其凸包就是包含这些点的最小凸多边形，凸多边形的任何一条边所在的直线把凸多边形全部划在同一个半平面内。

求凸包问题的算法有枚举法，分治法，格雷厄姆扫描法等

先介绍枚举法：

枚举法就是通过将每两个点都一遍一遍去尝试的求出满足条件的解

凸包的重要性质：

如果点集中的两个点的连线属于凸多边形的边，当且仅当点集中其余的点都在两个点连线的同一侧。

两个点（x1,y1）（x2,y2）的直线方程将平面分成了两个半平面，一个半平面满足ax-by<c,另一个满足ax-by>c

其中a = y2-y1 b = x2-x1 c = (x1*y2)-(x2*y1)

如果ax-by=c那么则说明第三点和前两点共线。

具体算法代码实现：

#include<iostream>
#include<algorithm>
#include<ctime>
#include<cstdlib>
using namespace std;
int i,j;

struct Point 
{
	int x;
	int y;
	int flag;	
};

struct Point point[100];

void ConvexHull(int n)
{
	int a,b,c;
	int sign1,sign2;
	for(i = 0;i<n;++i){
		for(j = i+1;j<n;j++){
			a = point[j].y - point[i].y;
			b = point[j].x - point[i].x;
			c = (point[i].x * point[j].y)-(point[i].y * point[j].x);
            sign1 = 0;      //分别记录直线两边的点的数量 
			sign2 = 0;			
			for(int k = 0;k<n;k++)
			{
				if((k == j) || (k == i)) continue;
				if((a*point[k].x-b*point[k].y) == c)
				{
					sign1++;
					sign2++;
				}
				if((a*point[k].x-b*point[k].y)>c)
				sign1++;
				if((a*point[k].x - b*point[k].y)<c)
				sign2++;
			}
			if(((sign1 == (n-2)) || (sign2 == (n-2))))
			{
				point[i].flag == 1;
				point[j].flag == 1;
				cout<<"极点坐标为:("<<point[i].x<<","<<point[i].y<<")";
				cout<<" "<<"("<<point[j].x<<","<<point[j].y<<")";
				cout<<endl;
			}
		}
	}
}

void random(int n) 
{
	srand((unsigned)time(0));
	for(int h = 0;h<n;h++)
	{
		point[h].x = 1+rand()%10;
		point[h].y = 1+rand()%10;
	}
}

int main()
{

	int n;
	cout<<"请输入一共有多少个点对："<<endl;
	cin>>n;
	random(n);
	for(int m = 0;m<n;m++)
	{
		cout<<"("<<point[m].x<<","<<point[m].y<<")";	
	}
	cout<<endl;
	ConvexHull(n);
	return 0;
}

 

运行结果展示：

分治算法之后补充