详细过程可参考pdf文档或代码。
算法Bruteforce(Q)
输入 :平面上n个点的集合Q
输出 :CH(Q)，Q的凸包
1: For ∀A,B,C,D∈Q Do
2: If D位于ABC组成的三角形内(根据面积判定)
3: Then 从Q中删除该点
4: A←Q中横坐标最大的点
5: B←Q中横坐标最小的点
6: SL←{P|P∈Q且P位于AB直线的下方}
7: SU←{P|P∈Q且P位于AB直线的上方}
8: 对SL和SU分别升序排序
9: 输出A, SL, B, 逆序SU
算法Graham-Scan(Q)
输入 :平面上n个点的集合Q
输出 :CH(Q)，Q的凸包
1: 求Q中y坐标最小的点p0，若存在多个点，则选x坐标最小的
2: 按照与p0的极角逆时针排序其余点< p0, p1, …, pm>，
3: 如果存在极角相同的点，选择欧式距离更近的点在前
4: S.push(p0), S.push(p1), S.push(p2)
5: For i←3 To m Do
6: While S.next_to_top(), S.Top()和pi形成非左 Do
7: S.Pop()
8: S.push(pi)
9: Return S
算法Divide_and_conquer(Q)
输入 :平面上n个点的集合Q
输出 :CH(Q)，Q的凸包
• Preprocess:找到横坐标最大的点A和最小的点B，标记每个点是否访问，若全部访问则算法停止。(时间复杂度为O(n))；
• Divide:作直线AB，把凸包分为SL和SU上下两个子集，对每个部分求得点Pmax,使得SABPmax最大。将三角形三个点和三角形内部的点标记为已访问，删去所有三角形内部及边上的点。(时间复杂度为O(n))；
• Conquer: 进一步依据△ABPmax划分成左右两个部分，当作SL和SU，分治递归、不断重复。(时间复杂度为2T(n/2))。
