安德鲁算法（Andrew’s Algorithm）是计算几何当中一种求凸包的算法。

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

简单来讲，对于一个二维空间的点集，这个点集当中的一些点总可以形成一个凸多边形，而这个凸多边形之内恰好可以包括除了组成凸包这个凸多边以外的所有点，而这个凸多边形就是凸包。

再形象的理解一下，凸包可以看成是再木板上钉了许多钉子，用一根橡皮经框住所有钉子是所得到的多边形。

如上图，红色点集当中的一些点可以组成黄色的凸多边，而这个凸多边恰好可以囊括所有的红色点集，这个多边形/组成多边形的点集就叫做凸包。

首先我们观察一下任何一个凸包，很明显的一个特点就是，凸包是凸多边 那么凸多边有什么用呢，我们来看看一个凸包上连续三点的一些关系。 我们让这连续的三个点分别为p0,p1,p2。 向量 a = p1 - p0; 向量 b = p2 - p0; 不难发现： p2在向量a的右端 也就是p2在向量a的顺时针方向。 用叉积来表示上面的语句：向量a X（叉乘） 向量b < 0

对于凸包上按照顺时针方向的每三个点，均满足这个规律。读者可自行试试。

倘若一个点不再凸包上，就不会满足这个规律。我们不妨尝试一下： 假如p0,p1为凸包上的点，p2不在凸包上。 对于向量a和向量b，好像没什么问题：p2也在向量a的顺时针方向

但是一但是下一个点呢？ 我们先假设这个绿色的点是在凸包内的，对于下一个点，对于这个点和之前凸包内连续的两点（就是上一次的p1和p2）来计算叉积。

这次的p2在由向量a的左侧，叉积值大于0，不满足我们的规律了。 所以一旦一个点不是组成凸包的点，那么经过这个点组成的多边形就不是凸多边形，更不是凸包了。

其中点是一个类，其中double x,y;存储其的坐标，下面重载了一些常用的运算。排序方法也在其中重载＜来定义。

而对于Vector，不难理解其就是一个点（向量可以移动，其的起点可以移动到原点，那么向量的表达就和点的表达方法一直）。

对于多边形，我们可以看成其是一系列点的集合，我们使用vector 来存储。

我们设原始的点集为多边形 p。

对于所有的二维坐标点，按照x从小到大排序，在x相同的情况下，对于y从小到大排序。

定义凸包上部为 ploygom u 首先先加入排序完的点集当中的头两个。

对于每一个点，我们取出当前以构建凸包内的最末尾的两个点，判断这个点是否与前两个点是否可以继续构造凸多边形。 如果是顺时针构造凸包，那就是这个点是否在前两个点组成的向量的顺时针方向。 如果是：将当前点加入凸包 如果不是：回溯，删除凸包内最后一个点，同时再取出删除后的凸包的最后两个点，再进行判断。直到不断删除之后凸包内只剩下一个点了 或者 当前点与最后两个点可以组成凸多边形。

那只有一直删掉凸包内最后一个点，不断判断，直到满足其是一个凸多边形为止。

如此，一直处理完所有的点。得到凸包上部u。

原理与创建凸包上部相同，因为是顺时针创建凸包，所以对于所有点需要从后向前向前存储。 同样的，一开始储存两个点。

然后按照创建凸包上部的方法创建凸包。