二维凸包问题

什么是二维凸包

假设墙上顶一组钉子，这些钉子的集合为X，我们用橡皮筋围住这些钉子，橡皮筋的形状就是凸包(来源于网络)。

---

向量的叉乘

对于两个向量$\overrightarrow{pq}$和$\overrightarrow{qr}$

• 如果$\overrightarrow{pq}$和$\overrightarrow{qr}$的叉积结果大于0，说明两者之间小于180度(以$\overrightarrow{pq}$方向为极轴，逆时针追踪$\overrightarrow{qr}$)，说明r在$\overrightarrow{pq}$的左边
• 如果$\overrightarrow{pq}$和$\overrightarrow{qr}$的叉积结果小于0，说明两者之间大于180度(以$\overrightarrow{pq}$方向为极轴，逆时针追踪$\overrightarrow{qr}$)，说明r在$\overrightarrow{pq}$的右边
• 如果$\overrightarrow{pq}$和$\overrightarrow{qr}$的叉积结果等于0，说明p,q,r三点在同一条线上

---

Gragam扫描法

算法流程：

• 找到一个一定在凸包中的初始点，比如最左下的点。
• 按拟时针逐个加入可能在凸包中的点。做法就是先把剩下的点集按照相对初始点的极角排序，如果极角相同，则按距离顺序近的在前。
• 我们从排序好的有序点中将前两个点放入结果栈中。然后从第三个点开始遍历剩余的有序点。假设当前点是a，上一个点是a-1，上上一个点是a-2。我们通过叉乘判断$\overrightarrow{a-2，a-1}$和$\overrightarrow{a-1，a}$的结果，如果叉乘结果小于等于0，说明a点没错。如果叉乘结果大于0，说明a-1就有问题，则把a-1点从结果栈中吐出，再判断新a-1点与a-2和a的叉乘结果，知道结果小于等于0.对于叉乘结果=0的特殊情况，那我们根据远近依次排序

详细解释可以看参考1、参考2。