使用蛮力法、GrahamScan和分治法求解凸包问题——哈工大算法实验一
求解凸包问题
详细过程可参考pdf文档或源码，如果有用请点个star，地址:https://github.com/HuiyanWen/convex_hull
其他相关实验
使用A*算法求解迷宫路径问题——哈工大算法实验二
使用贪心近似、线性规划舍入法和精确法求解集合覆盖问题——哈工大算法实验三
随机快排和三路快排的实现——哈工大算法实验四
蛮力法
算法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
算法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))。