计算几何–凸包（graham算法实现）

题目链接：LeetCode587 https://leetcode-cn.com/problemset/all/

题目描述

在一个二维的花园中，有一些用 (x, y) 坐标表示的树。由于安装费用十分昂贵，你的任务是先用最短的绳子围起所有的树。只有当所有的树都被绳子包围时，花园才能围好栅栏。你需要找到正好位于栅栏边界上的树的坐标。

示例 1:

输入: [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
输出: [[1,1],[2,0],[4,2],[3,3],[2,4]]
解释:

示例 2:

输入: [[1,2],[2,2],[4,2]]
输出: [[1,2],[2,2],[4,2]]
解释:
(即使树都在一条直线上，你也需要先用绳子包围它们。)
注意:

所有的树应当被围在一起。你不能剪断绳子来包围树或者把树分成一组以上。
输入的整数在 0 到 100 之间。
花园至少有一棵树。
所有树的坐标都是不同的。
输入的点没有顺序。输出顺序也没有要求。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/erect-the-fence

题目解析

算法分析

首先这是经典的计算几何模板题——求凸包，而对于第一次接触的话，需要掌握利用叉积求解两条线的顺逆关系的基础知识点，如果没有基础知识也没关系，计算几何的题目颇有一种Talk is free，show me your code的感觉，因为计算几何初期的理论都不难，而其代码实现难度却高于理论难度，所以可以先了解算法，然后再解析代码。

首先来一组样例：

求得凸包如下

解法步骤

第一步：
找到一个必定属于凸包的点，一般是纵坐标最小的点，若有多个再取横坐标最小，记为P0。

接下来，将其它点根据”“关于P0的角度”“排序（也就是极角，不懂极角也没事，先看图）：
排序依据： 与P0点（在这里我们称其为极点）建立一条边，按照该边关于x轴的逆时针方向（极角）从小到大排序，若角度一样，则距离近的在前。（勘误：这里的P1、P2、P3点的顺序搞反了）

这里有两个排序标准：
① 极角
② 距离
我们先考虑怎么利用极角求凸包：

算法核心

我们的算法是从P0开始不断产生凸包的边，假设现在已经得到P8为止之前的凸包。

现在，我们需要考虑P9点，我们发现P9点对于P7、P8这条边来说是一个朝内旋转的点，也就是说，选入P9点，满足凸包的外凸性质，所以我们将P9点也选进来。

接下来考虑P10点，容易发现，对于P10点来说，P9点变成了一个内凹的形状，显然不符合凸包的性质，于是，这个P9点我们不要了，更新成P10点。

这就是求解凸包的关键步骤，按照极角逆时针的顺序，每次判断下一个点是否构成一个凸的形状，若是，则直接选入，若不是，则将凹陷进去的点从已选序列中踢出（需要循环操作，因为新加的点可能造成之前连续一系列点的退出），而这关键就是判断凹凸的形状。

再举个例子，这里P1P2是一条已经形成的线段，我们考虑P3点，左边的情况，由于P2P3线段与P1P2线段显然是凸形的，所以可以选进来，而右图的情况，则需要先删除P2，再选入P3

这里再动画演示一下：

看到这里可能读者会问那么如何判断两条线段构成的朝向呢？
这里用到计算几何的基础知识点——向量的叉积，这里只简单解释为什么叉积能判断朝向，具体的还是需要读者从计算几何基础开始入门。

支线任务：浅谈叉积的意义

我们设计两条线：

两条线段：利用点相减的形式表示，则AC = C - A =（0, 2），AB = B - A =（1, 1）
线段a与线段b的叉积，记作a×b，公式：若a =（x1,y1），b= (x2,y2)，则
AC×AB = x1y2 - x2y1
所以样例中，AB×AC=1×2-0×1=1
扯了半天，我们得出：AB×AC的结果为1，大于0
根据结果的正负关系，我们可以推出AB与AC的关系：
①若结果大于0，则AC在AB的逆时针方向
②若结果小于0，则AC在AB的顺时针方向
③若结果等于0，则AC与AB平行（其实是共线，但是可能朝向相反）
或者我们验证一下这个结论，将AB×AC改为AC×AB，则得到结果：
AC×AB = 0×1-1×2 = -1，结果刚好相反，可以理解为交换了计算顺序，即是互换了线段位置，也符合结论。
至于为什么用两点相减表示线，用并将两条线的x与y交错相乘后得到的差便可以判断方向，这里面是计算几何的基础，需要读者自己研究相关内容，是一大领域。
但是对于本题，我们只需利用这么一个公式，哪怕对于其原理不理解也不影响本题的求解。

小细节：为什么极角相同得情况下要距离近的在前

首先，无论是近的在前，还是远的在前，按照我们的策略，都是可以得出凸包：
①若近的在前，则远的点其方向一定会使得近的点形成凹形，将近处的点作为内部点踢走
②若远的在前，则一系列点会出现共线的情况，乍一想如果让程序选择保留共线的点（也就是可能凸包的一条边上有多个点，这些点都进行保留而不是提出），则也可以形成凸包，但是在第一个与最后一个枚举点时会有比较麻烦的问题。
所以，一般选择近的在前，然后若出现共线的线段，则踢出，这样确保选出所有凸包的顶点，虽然像题目中是需要输出凸包边上的所有点的，那么我们可以考虑先利用凸包处理出所有的拐点，然后按照极角枚举，将刚好处于凸包边上共线点也一起加入。

代码实现

这里为了方便操作，定义了点的类型，并且重载了减法和叉积运算：

struct POINT{ //点的定义 
	int x, y;
    POINT operator - (const POINT &b){ //重载点的减运算
		POINT ans;
		ans.x = this->x - b.x;
		ans.y = this->y - b.y;
		return ans;
	}
    int operator * (const POINT &b){  //重载叉积运算
		return this->x*b.y-this->y*b.x;
	}
	void print(){printf("%d %d\n", this->x, this->y);}
	POINT(){this->x = 0; this->y = 0;}
	POINT(int a, int b){this->x = a;this->y = b;}
}List[MAXN];

同时将题目中的动态数组换成了数组：

for(int i = 0; i < n; i++){
	List[i].x = points[i][0];
	List[i].y = points[i][1];
}

首先，我们需要找到极点，这个简单，直接O(n)循环即可：

int k = 0;  //第一个点作为基准
for(int i = 1;i < n;i++)  //找最左下边的一个点，也就是起始开始枚举的点
	if(List[i].x+List[i].y < List[k].x+List[k].y)
		k = i;
swap(List[k],List[0]);  //将极点换到0号位置

接下来是根据极角的排序（极角相同的则近的在前），同样需要利用叉积，我们前面知道叉积的正负可以判断两线段的顺逆时针关系，于是可以利用叉积进行两条线段的顺序比较：

int cmp(POINT p1, POINT p2)  //相对于List[0]的极角排序
{
    int tmp = (p1-List[0])*(p2-List[0]); //计算p1和p2线段的叉积
    if(tmp > 0)  //若大于0，说明p2在p1的逆时针方向，即p2得极角更小，无需交换
        return 1;
    else if(not tmp && dis(p1,List[0]) < dis(p2,List[0]))
        return 1;  //若等于0，则根据距离判断，距离近的在前
    else 
        return 0;
}
sort(List+1,List+n,cmp);  //根据极角排序 

接下来是最核心的环节，从极角最小的p1开始，按照思路一个一个选点，而不符合的点有需要删除。
注意到每次操作都是最新的点，可以用栈实现。
以样例为例：

此时，我们的栈中已有元素：{P0,P1,P7,P8}
接下来，由于线段(P7,P9)在线段(p7,p8)的逆时针方向**（这里的顺逆时针是以P7点作为极点判断的），呈现凸形，所以选入点P9：{P0,P1,P7,P8,P9}

接下来考虑P10，由于线段(P8,P9)在线段(P8,P10)顺时针方向（这里的方向以P8作为极点判断）**，呈现凹形，所以P9是内部点，弹出P9，加入P10：{P0,P1,P7,P8,P10}

Stack[0] = 0; //先将前两个点放入栈中
Stack[1] = 1;
top = 2;
for(int i = 2;i < n;i++)  //程序核心，利用贪心思想取出所有凸包中的点
{
	//利用叉积判断判断与栈顶构成的两条线的顺逆关系，若呈凹形则踢出
	while(top > 1 && (List[Stack[top-1]]-List[Stack[top-2]])*(List[i]-List[Stack[top-2]]) < 0) 
		top--;
	Stack[top++] = i; //将最新点加入
}
for(int i = 0; i < top; i++){//此处与算法无关，将结果放回动态数组
	vector<int> tmp;
	tmp.push_back(List[Stack[i]].x);
	tmp.push_back(List[Stack[i]].y);
	ans.push_back(tmp);
}

最后结果：{P0,P1,P7,P8,P10,P12}
别忘了将凸包边上的点一起加入，这里可以采用按照极角顺序枚举的方式，判断共线：

for(int i = 1; i < top; i++){  //枚举每条边上的点，加入结果
	for(int j = Stack[i-1]+1; j < Stack[i]; j++){
		if((List[Stack[i]]-List[j])*(List[j]-List[Stack[i-1]])==0){
			vector<int> tmp;
			tmp.push_back(List[j].x);
			tmp.push_back(List[j].y);
			ans.push_back(tmp);
		}
	}
}
for(int j = Stack[0]+1; j < Stack[top-1]; j++){
	if((List[Stack[top-1]]-List[j])*(List[j]-List[Stack[0]])==0){
		vector<int> tmp;
		tmp.push_back(List[j].x);
		tmp.push_back(List[j].y);
		ans.push_back(tmp);
	}
	}

最终代码（丑了点）：

const int MAXN = 100039; 
int Stack[MAXN];//用来存放凸包的点
int top;//表示凸包中点的个数
struct POINT{ //点的定义 
	int x, y;
    POINT operator - (const POINT &b){ //重载点的减运算
		POINT ans;
		ans.x = this->x - b.x;
		ans.y = this->y - b.y;
		return ans;
	}
    int operator * (const POINT &b){  //重载点乘运算
		return this->x*b.y-this->y*b.x;
	}
	void print(){printf("%d %d\n", this->x, this->y);}
	POINT(){this->x = 0; this->y = 0;}
	POINT(int a, int b){this->x = a;this->y = b;}
}List[MAXN];
double dis(POINT x, POINT y){  //两点欧几里得距离
	return sqrt((y.y-x.y)*(y.y-x.y)+(y.x-x.x)*(y.x-x.x));
}
void swap(POINT& a, POINT& b){
    POINT tmp = a;a = b; b = tmp;
}
int cmp(POINT p1, POINT p2)  //相对于List[0]的极角排序
{
    int tmp = (p1-List[0])*(p2-List[0]);
    if(tmp > 0)
        return 1;
    else if(not tmp && dis(p1,List[0]) < dis(p2,List[0]))
        return 1;
    else 
        return 0;
}
class Solution {
public:
    vector<vector<int>> outerTrees(vector<vector<int>>& points) {
        int n = points.size();
        if(n<=3)return points;
        vector<vector<int>> ans;
        for(int i = 0; i < n; i++){
            List[i].x = points[i][0];
            List[i].y = points[i][1];
        }
        int k = 0;
        for(int i = 1;i < n;i++)  //找最左下边的一个点，也就是起始开始枚举的点
            if(List[i].x+List[i].y < List[k].x+List[k].y)
                k = i;
        swap(List[k],List[0]);
        sort(List+1,List+n,cmp);  //根据极角排序
        //for(int i = 0; i < n; i++)List[i].print();printf("\n");
        vector<int> tmp;
        Stack[0] = 0;
        Stack[1] = 1;
        top = 2;
        for(int i = 2;i < n;i++)  //程序核心，利用贪心思想取出所有凸包中的点
        {
            while(top > 1 && (List[Stack[top-1]]-List[Stack[top-2]])*(List[i]-List[Stack[top-2]]) <= 0)
                top--;
            Stack[top++] = i;
        }
        for(int i = 0; i < top; i++){
            vector<int> tmp;
            tmp.push_back(List[Stack[i]].x);
            tmp.push_back(List[Stack[i]].y);
            ans.push_back(tmp);
        }
        for(int i = 1; i < top; i++){
            for(int j = Stack[i-1]+1; j < Stack[i]; j++){
                if((List[Stack[i]]-List[j])*(List[j]-List[Stack[i-1]])==0){
                    vector<int> tmp;
                    tmp.push_back(List[j].x);
                    tmp.push_back(List[j].y);
                    ans.push_back(tmp);
                }
            }
        }
        for(int j = Stack[0]+1; j < Stack[top-1]; j++){
            if((List[Stack[top-1]]-List[j])*(List[j]-List[Stack[0]])==0){
                vector<int> tmp;
                tmp.push_back(List[j].x);
                tmp.push_back(List[j].y);
                ans.push_back(tmp);
            }
        }
        return ans;
    }
};