凸包（Convex Hull）

凸包的定义

凸包（Convex Hull）是一个计算几何（图形学）中的概念。

在一个实数向量空间 \(V\) 中，对于给定集合 \(X\) ，所有包含 \(X\) 的凸集的交集 \(S\) 被称为 \(X\) 的凸包。 \(X\) 的凸包可以用 \(X\) 内所有点 \((X_1,...,X_n)\) 的凸组合来构造.

在二维欧几里得空间中，凸包可想象为一条刚好包着所有点的橡皮圈。

用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边形，它能包含点集中所有的点。

以左下角的点为初始点，剩下的点按照以初始点为中心逆时针的方向进行排序（如果共线的话距离初始点近的排在前面，使用向量叉乘判断）。
特判只有一个点或者两个点的情况。
不止两个点的话，按顺序枚举每个点作为新点，如果最后两个点与新点不构成逆时针（用向量叉乘判断）也就是凸包的话，删掉最后一个点，直到找到满足条件的新点，将新点加入。

注：部分资料来源于百度百科