概念
凸包(Convex Hull)是一个计算几何（图形学）中的概念。用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边型，它能包含点集中所有点的。
问题
给定平面的点集，求出凸包的所有顶点。
算法思路
Grahanm's Scan算法的主要思路如下：
1，选择P中y坐标最小的点为起始点p0，若有多个这样的点则进一步选取其中x坐标最小的点为p0;
2，设<p1,p2,……,pm>是P中剩余的点，对其按逆时针方向相对p0的极角进行从小到大排序，若有多个点有相同的极角，则离p0点近的排在前面；
3，设排序后的点的顺序为p1,p2,……,pm，分别计算向量p0p1与p1p2的叉积，二维矢量的叉积a × b = IaI•IbIsinθ，θ为从a到b的夹角，如果b在a的逆时针方向，则sinθ为正，叉积也就为正，在我们逆时针遍历的情况下，如果b在a的顺时针方向，则p1点必定不是凸包上的点，反之则是在凸包上的点。所以我们使用栈来保存凸包上的点，遍历过程中发现栈顶的点不是凸包上的点就pop出来，如果是就继续把接下来的点放入栈中。
图片可能更容易理解，这里就放几张别人博客的图片：
Grahanm's Scan
JAVA实现
import java.util.*;
public class Main {
static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "Point{" +
"x=" + x +
", y=" + y +
'}';
}
}
// 用于存储起始点
public static Point centerPoint;
// 叉积
public static int CJ(int x1, int y1, int x2, int y2){
return x1*y2 - x2*y1;
}
// 计算向量(p1->p2)和(p2->p3)两个向量的叉积
public static int compare(Point p1, Point p2, Point p3){
return CJ(p2.x-p1.x, p2.y - p1.y, p3.x-p2.x, p3.y-p2.y);
}
public static void main(String arg[]){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
List<Point> points = new ArrayList<>();
for (int i=0; i<n; i++){
int x = in.nextInt();
int y = in.nextInt();
Point point = new Point(x, y);
// 找到x,y都最小的点作为起始点
if (centerPoint == null || centerPoint.y>point.y || (centerPoint.y==point.y && centerPoint.x>point.x)){
centerPoint = point;
}
points.add(point);
}
// 把起始点拿出去
points.remove(centerPoint);
// 按照与起始点向量的极角排序
Collections.sort(points, (p1, p2) -> {
if (Math.atan2(p1.y- centerPoint.y, p1.x- centerPoint.x) != Math.atan2(p2.y- centerPoint.y, p2.x- centerPoint.x)){
// atan2可以计算极角
return Math.atan2(p1.y- centerPoint.y, p1.x- centerPoint.x) < Math.atan2(p2.y- centerPoint.y, p2.x- centerPoint.x)? -1 : 1;
}
// 极角相同与中心点距离越近，则x坐标也就越近
return Math.abs(p1.x- centerPoint.x) - Math.abs(p2.x- centerPoint.x);
});
// 用数组模拟栈
Point[] stack = new Point[n];
stack[0] = centerPoint;
// 栈顶指针
int top = 0;
// 遍历点集中每一个点
for (int i=0; i<points.size();){
//如果栈中元素大于等于2并且(p2->p3)在(p1->p2)的顺时针方向，栈顶的点抛出
while (top>=1&&compare(stack[top-1], stack[top], points.get(i)) < 0) top--;
// 找到在逆时针方向的点了，将p2放入栈顶
stack[++top] = points.get(i++);
}
// 输出栈中的所有点就是凸包上的点
for (int i=0; i<=top; i++){
System.out.println(stack[i]);
}
}
}
