凸包，可以被理解为在一块木板上钉上许多钉子，再用一根橡皮筋把最外面的钉子圈起来，就是所谓的凸包，如图所示



很多算法是基于凸包的，不一一介绍。

关于凸包的算法很多，这里不一一列举，仅介绍一种经典算法——Graham 扫描法
在这个算法中，要使用到栈的概念，PUSH和POP
PUSH是把一个变量压入栈中，存放在栈的最上方，POP则是把栈的最上面一个变量弹出

首先寻找一个最低的点(P0)，然后开始向P1连接
再把P1压入栈中
P2开始向P3连接
如果向P3连接的这条线是向左转，就压入栈中。
否则就POP出这个坐标，跳过这个坐标连接下一个点，如图所示



最后，正确的凸包坐标被全部压入栈中。



由于这是经典算法，算法的正确性证明略。

参考文献

[1] 《算法导论》第二版，作者Gxxx，Axxx……200X年XX出版社;

。。。。。。 其实没参考 = =