Graham Scan 解决凸包问题

输入一个点集，输出一个构成能容纳所有点的最小多边形的顶点集合

1. Graham scan

1. 选择一个具有最小 y 坐标的点 p，如果有多个点，则选择最左边的点（x 坐标最小）

2. 将其他点按照 p -> i 向量的极角(polar angle) 排序

   极角即为向量与 X 轴正向 的夹角

3. 按顺序考虑其余点，如果出现顺时针的拐角则将该点忽略

2. 要点

2.1 寻找原点

将点按照 y 坐标优先进行排序；

即，先看 y 坐标，后看 x 坐标。

2.2 按照极角排序

使用基于逆时针转角（CCW）的方法

1. 如果 $q_1$ 在 $p$ 上方，$q_2$ 在 $p$ 下方，则 $q_1$ 极坐标较小

2. 如果 $q_1$ 在 $p$ 下方，$q_2$ 在 $p$ 上方，则 $q_1$ 极坐标较大

3. 否则，根据 $p \to q_1 \to q_2$ 的逆时针转角(ccw(p, q1, q2)) 确定极坐标大小

上述函数中，ccw(p, q1, q2) 返回 1，则 $q_2$ 较大；
返回 -1 则 $q_1$ 较大

3. 确定逆时针转角(CCW)

使用三角形有向面积进行判定

$\begin{aligned} 2 \times Area(a, b, c) = \begin{vmatrix} a_x & a_y & 1\\ b_x & b_y & 1\\ c_x & c_y & 1\\ \end{vmatrix} = \\ \begin{vmatrix} b_x - a_x & b_y - a_y \\ c_x - a_x & c_y - a_y \\ \end{vmatrix} \end{aligned}$

如果面积为正，则为逆时针
如果面积为负，则为顺时针
如果面积为 0，则三点共线

原理：根据空间向量的右手系可知，当法向量为负时，三点为顺时针；当法向量为正时，三点为逆时针。

而平面法向量和两个向量的叉乘正负一致，则可以通过求两个向量的叉乘判断顺逆时针的情况。

由向量叉乘的物理含义可知，向量的叉乘就是两个向量所在的平行四边形的面积

在三维条件下，叉乘为

$|a \times b| = \begin{vmatrix} i & j & k\\ a_x & a_y & a_z\\ b_x & b_y & b_z \end{vmatrix}$

取 $z = 0$ 这一平面，则

$|a \times b| = \begin{vmatrix} a_x & a_y\\ b_x & b_y\\ \end{vmatrix}$

到这一步不难看出，上面两倍三角形有向面积的二维行列式表达正是二维空间中向量的叉乘。

所以，三角形有向面积的正负就表明了三角形三个点的顺时针和逆时针的特性。

4. Corner Case

主要出现的 Corner Case 有：

1. 点数量不够

   只有至少不共线的 3 个点才能构成凸包

2. 共点问题

   有多个点重合

3. 共线问题

   有多个点的共线问题

4. 点集为空等其他情况

5. 实现流程

对于以上 Corner Case 有如下处理方法：

1. 检查 null

2. 检查点集数量

   3 个点及以上才有可能产生凸包

3. 遍历排序后的点集，直到第一个不与第一个点重复的点，如果所有点都重复，则退出

   由此可去除原点重复问题

4. 遍历剩下的点集，直到第一个与前两个不共线的点，将其的前一点作为凸包第二顶点

   前一点 即与原点共线的 最后一个点

5. 通过 CCW 来计算逆时针转角，抛弃小于等于 0 的点

   由于 CCW 可以表示共线情况，可以通过只要大于零的点即可避免途中出现的共线情况
   实际上，由于 CCW 使用三角形面积进行计算，所以，也可以解决共点问题