Graham Scan - Graham扫描算法
问题
用Graham Scan算法求拥有个点的点集的凸包，任意两点的坐标不同。
解法
在二维平面上选取坐标最小，坐标最小的顶点，将其余个顶点按照以的顺时针方向排序。如图所示：
上图中以点为基准，对其余点排序的结果为。
根据Cross中向量叉积的知识，可知对于三个顶点组成的向量，设有以下情况：
(1) 若则在逆时针方向。如图：
(2) 若则在顺时针方向。如图：
(3) 若则与方向相同。对于向量完全相同的两顶点，按照到距离从近到远排序。如图：
排序时比较任意两点到的向量叉积都为负数，则整组顶点可以按照顺时针排列。设排列后的顶点顺序为。
设置一个空堆栈，初始时推入三个顶点，此时堆栈为。
然后遍历剩余顶点，对于每个顶点，考虑堆栈的头部顶点、次头部顶点，判断这三个点组成的两个向量和，前者是否在后者的顺时针方向，即满足
(1) 若不满足条件，说明不是凸包上的点，对堆栈进行出栈操作（推出头部顶点）。然后再重复判断的值，直到满足该条件为止；
(2) 若满足条件，说明是凸包上的点，将其推入堆栈中。然后继续考虑下一个顶点；
用伪代码来描述上述过程是
for i = 3 to n-1:
while stack.size() >= 2 and ccw(stack.nextTop(), stack.top(), p[i]) <= 0:
stack.pop()
stack.push(p[i])
end
遍历完点集中所有顶点后，堆栈中的点即为的凸包。该算法的时间复杂度为。