Convex Hull 凸包

凸包是在n个点中的所围成的最小凸多边形。
凸包不需要包含所有的点但是需要将所有的点围在凸包内。
凸包所围的多边形与橡皮筋的概念相似，例如将橡皮筋套在钉板上(红框)，橡皮筋所围的多边形与凸包相似。

凸多边形

凸多边形必须符合以下条件：

简易的判断法为，所有的角皆转向同样方向(顺时钟或逆时钟)。

Graham Scan Algorithm (Graham扫描)

Graham扫描是结合圆型扫描及上述的转向判断方法所得到的扫描法。
传送门：圆型扫描解释

步骤ㄧ：圆型扫描

圆型扫描可以确保所建立的图形为简单多边形。

步骤二：角度转向判断

依照圆型扫描后所确认的连接顺序开始製图，同时每连接一个点，都需要确定角度转向是否一致。
如果连接一点时转向改变，将开始追朔过去之前所连结的点，并将最后连接的点与上一点连接，直到转向一致为止。
转向完全一致且最后一点与第一点后，会建立出一个凸多边形(凸包)。

转向判断

同方向

如果连接下一点时转向同方向则继续连接，直到转向不同方向或连接至第一点。

不同方向

如果连接下一点时转向不同方向则追朔之前所连接的点。

移除上一步骤所连接的线，并且连接最后达到的点与上一阶段所达到的点，直到转向同方向。
当转向同方向时，继续连接下一点。

完整步骤图

传送门：[笔记本: 演算法] 多边形篇 Part 1 - Simple Polygon 简单多边形
传送门：[笔记本: 演算法] 多边形篇 Part 3 - Furthest Pair of Points 最远两点配对