Graham‘s Scan法求解凸包问题

问题背景

• 关于凸包
  假设平面上有p0~p12共13个点，过某些点做一个多边形，使这个多边形能把所有点都“包”起来，当这个多边形为凸多边形时，我们称之为“凸包”
• 凸包问题
  在二维坐标系上，每个点都能用坐标(x,y)表示
  给出点的数目与各点的坐标，求构成凸包的点
  

Graham’s Scan法

先找到凸包上的一个点，从那个点开始按逆时针方向逐个找凸包上的点

步骤

1. 将所有点放在二维坐标系中，则纵坐标最小的点一定是凸包上的点，如图中p0

2. 将所有点的坐标进行平移，使p0作为原点，如上图

3. 计算各个点相对于p0的辐角 $\alpha$，按辐角从小到大的顺序对各个点进行排序。当 $\alpha$ 相同时，距离p0比较近的点排在前面。例如上图得到的结果为p1、p2、p3、p4、p5、p6、p7、p8。由几何知识可以知道，第一个点p1和最后一个点p8一定是凸包上的点

4. 现在我们知道了凸包上的第一个点p0和第二个点p1，我们把他们依次放在栈里面。

5. 将当前点初始化为p2，并进行如下操作：

    a. 判断栈顶的两个点形成的向量与栈顶点和当前点形成的向量之间是否是逆时针关系，即叉乘后得到的向量是否是逆时针方向。（这个问题的另一个表述是连接栈顶的两个点得到一条直线，看当前点是否在这个直线的左边）
    
    b.若是，则当前点为凸包上的点，将其压入栈中。并将排序中其后的点作为当前点，继续进行a的判断，直到遍历所有点。
    
    c. 若不是，则栈顶元素不是凸包上的点，将栈顶元素弹出。当前点不变，继续进行a的判断，直到是逆时针关系。
   

6. 最终遍历完后，栈中的元素就是构成凸包的点

流程图

代码链接

凸包问题的Graham’s Scan法求解