目录

凸包概念

算法思路

算法过程

1、准备数据

2、数据处理

2.1 获取左下角的点

2.2 坐标点移动至左下角点坐标系中

2.3 坐标点排序 

3、Graham算法

3.1 判断点与线（栈顶点和原点连线）的关系

3.2 计算夹角（顺逆时针旋转）

 3.3.算法主体

执行结果

凸包概念

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

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

算法思路

首先找到数组中位于左下角的点，并将其移动至数组首位；然后将所有点移动至以左下角点为坐标原点的坐标轴上；再对数组进行排序（按照与x轴夹角大小排序）；对排序完成的数组进行计算，求解凸包。

（1）创建凸包节点栈，并将排序后数组中的第二个值入栈（第一个值为坐标原点，无需入栈），开始凸包计算。

（2）判断数组中下一个点是否在前一点与坐标原点连线的左侧或连线上。若不在，转至步骤（3）若在转至步骤（4）

（3）栈顶点不符合要求，需要移除，并重新执行步骤（2）

（4）判断当前点p与栈中顶部两个点p1（top点）p2（顶部第二个点）的关系。

如果向量p2p1与向量pp1是逆时针旋转（即正角），或者点p、p1、p2三点连线；点入栈。

否则（顺时针旋转，负角），栈顶点p1出栈，p入栈。

（5）当遍历完数组所有值时，程序结束。栈中存储着凸包图形结点。

动态过程（源自数学：凸包算法详解 - 爱国呐 - 博客园）

备注：以下结构体、函数均为自定义结构体及函数。

算法过程

1、准备数据

//默认的输入列表
Point* init()
{
	Point p1(1, 3);
	Point p2(2, 2);
	Point p3(4, 9);
	Point p4(3, 5);

	Point* plist = new Point[5];
	plist[0] = p1;
	plist[1] = p2;
	plist[2] = p3;
	plist[3] = p4;

	return plist;
}

2、数据处理

2.1 获取左下角的点

void getPole(Point* &plist, int size)
{
	for (int i = 0; i < size; i++)
	{
		if (plist[i].y < plist[0].y || (plist[i].y == plist[0].y && plist[i].x < plist[0].x))
			Swap(plist[i], plist[0]);
	}
}

2.2 坐标点移动至左下角点坐标系中

void DealData(Point* &plist, int size)
{
	Point p = plist[0];
	for (int i = 0; i < size; i++) {
		plist[i].x -= p.x;
		plist[i].y -= p.y;
	}
}

2.3 坐标点排序 

void Sort(Point* &plist, int size)
{
	for (int i = 1; i < size - 1; i++)
		for (int j = 1; j < size - i; j++) {
			if (Compare(plist[j], plist[j + 1]))//plist[i] 
3、Graham算法 
3.1 判断点与线（栈顶点和原点连线）的关系 
//点与线的关系 0 共线，负 点在向量（原点与栈顶点连线）的右侧，正 左侧
int PointLine(Point v1, Point v2) {
	return v1.x*v2.y - v1.y*v2.x;
}
 
3.2 计算夹角（顺逆时针旋转） 
//向量叉乘
double cross(Point v1, Point v2) {
	return v1.x*v2.y - v1.y*v2.x;
}
//向量点乘
double multi(Point v1, Point v2) {
	return v1.x*v2.x + v1.y*v2.y;
}
//计算夹角
double getangle(Point p, Point p1, Point p2) {
	Point v1(p2.x - p1.x, p2.y - p1.y);
	Point v2(p.x - p1.x, p.y - p1.y);
	double the = atan2(cross(v1, v2), multi(v1, v2));
	return the;
}
 
 3.3.算法主体 
	//逆时针找数据
	stack stack;
	stack.push(pl[0]);
	stack.push(pl[1]);
	for (int i = 2; i < psize; i++) {
		//cout << "第" << i << "个点：" << " " << pl[i].x << " " << pl[i].y << endl;
		if (PointLine(stack.top(), pl[i]) < 0)//在栈顶点与原点连线的右边
		{
			//cout << "出栈：" << stack.top().x << " " << stack.top().y << endl;
			stack.pop();
			
			stack.push(pl[i]);
			//cout << "入栈：" << stack.top().x << " " << stack.top().y << endl;
		}
		else if(PointLine(stack.top(), pl[i]) == 0) {//点在线上
			stack.push(pl[i]);
			//cout << "入栈：" << stack.top().x << " " << stack.top().y << endl;
		}
		else {//点在线的左侧
			Point p1 = stack.top();
			stack.pop();
			Point p2 = stack.top();
			if (getangle(pl[i], p1, p2) < 0) {//逆时针旋转
				stack.push(p1);
				stack.push(pl[i]);
				//cout << "入栈：" << stack.top().x << " " << stack.top().y << endl;
			}
			else {//顺时针旋转
				//cout << "出栈：" << p1.x << " " << p1.y << endl;
				stack.push(pl[i]);
				//cout << "入栈：" << stack.top().x << " " << stack.top().y << endl;
			}
		}		
	}
 
完整代码如下：
 
#include 
#include 
using namespace std;
#include 
#include 
//Graham扫描法求解凸包问题
struct Point {
	int x, y;
	Point(int x, int y) :x(x), y(y) {}
	Point() {}
};
//默认的输入列表
Point* init()
{

	Point p1(1, 3);
	Point p2(2, 2);
	Point p3(4, 9);
	Point p4(3, 5);

	Point* plist = new Point[5];
	plist[0] = p1;
	plist[1] = p2;
	plist[2] = p3;
	plist[3] = p4;

	return plist;
}
void Swap(Point &p1, Point &p2) {
	Point tmp = p2;
	p2 = p1;
	p1 = tmp;
}
//计算左下角点
void getPole(Point* &plist, int size)
{
	for (int i = 0; i < size; i++)
	{
		if (plist[i].y < plist[0].y || (plist[i].y == plist[0].y && plist[i].x < plist[0].x))
			Swap(plist[i], plist[0]);
	}
}
//比较a,b与x轴夹角的大小
double Compare(Point a, Point b)
{
	double cosa = a.x / sqrt(a.x*a.x + a.y*a.y);
	double cosb = b.x / sqrt(b.x*b.x + b.y*b.y);
	return cosa < cosb;
}
//冒泡排序
void Sort(Point* &plist, int size)
{
	for (int i = 1; i < size - 1; i++)
		for (int j = 1; j < size - 1 - i; j++) {
			if (Compare(plist[j], plist[j + 1]))//plist[i] Graham(Point* pl, int psize) {
	getPole(pl, psize);//处理数据，极点至首位
	Point pole = pl[0];//坐标原点

	DealData(pl, psize);//将极点为坐标原点处理各点坐标

	Sort(pl, psize);//按极角排序
    stack stack;
	//逆时针找凸包结点
    stack.push(pl[0]);
	stack.push(pl[1]);
	for (int i = 2; i < psize; i++) {
		if (PointLine(stack.top(), pl[i]) < 0)//在栈顶点与原点连线的右边
		{
			stack.pop();
			stack.push(pl[i]);
		}
		else if(PointLine(stack.top(), pl[i]) == 0) {//点在线上
			stack.push(pl[i]);
		}
		else {
			Point p1 = stack.top();
			stack.pop();
			Point p2 = stack.top();
			if (getangle(pl[i], p1, p2) < 0) {//逆时针旋转
				stack.push(p1);
				stack.push(pl[i]);
			}
			else {
				stack.push(pl[i]);
			}
		}		
	}

    int pnum = stack.size();
    //顺时针获取栈内元素
	vector plist;
	for (int i = 0; i < pnum; i++)
	{
		plist.push_back(Point(stack.top().x + pole.x, stack.top().y + pole.y));
		stack.pop();
	}

	return plist;
}

int main()
{
	Point* plist = init();
    //执行算法
	vector pl = Graham(plist, 4);//输入点的列表、点的个数

	cout << "最终结果为：n";
	for (int i = 0; i < pl.size(); i++) {
		cout << "第" << i << "个点：" << pl.at(i).x << " " << pl.at(i).y << endl;
	}

	return 0;
}
 
执行结果 
 
 算法参考：
 
凸包算法（Graham扫描法）_よろしくお願いします-CSDN博客_graham扫描法
 
​​​​​​凸包算法（Graham扫描法）详解 - 踩在浪花上 - 博客园