问题描述：找到包含点集Q的最小凸多边形。使得点集内的点均在凸多边形的边上或内部。

                     即集合内任意两点的连线均在凸多边形内部。

输入：平面上的n个点的集合Q

输出： CH(Q):Q的convexhull

（一）蛮力法思路：

找到点集内的内部点去掉，剩余未边界点。

内部点的判断：只要其中三点A,B,C构成的三角形包含的点P则P为内部点。

三角形内部点具体判断方法：

如果P在△ABC内部，则A，P两个点在BC同侧；P,B两个点在AC同侧；C,P两个点在AB同侧。转换为点与线关系的判断。

判断点P与直线AB的关系的方法：

AB的直线方程g(x,y)=0.

P(x0,y0)与AB共线，则g(x0,y0) = 0;

P(x0,y0)在直线AB一侧，则g(x0,y0) > 0 或g(x0,y0)<0

所以判断两个点P(x0,y0),Q(x1,y10)是否在直线AB的同侧只需要判断：g(x0,y0)*g(x1,y1)>0是否成立。

时间复杂度分析：对于任意四个点A,B,C,D均需要判断，所以T(n)=θ(n^4)

优化方式：固定一个点（min y点），遍历其余三个点，也可以找到所有内部点

（二）Graham-Scan算法

基本思想

–当沿着Convex hull逆时针漫游时，总是向左转

–在极坐标系下按照极角大小排列，然后逆时针方向漫游点集，去除非Convex hull顶点(非左转点)。

关于向左旋转，一会在讨论，先给出基本算法框架

数据结构：使用栈

1.  找出点集Q中y-坐标值最小的点P-₀

2.  按与P-₀极角(逆时针方向)大小排序Q中其余点，结果记为<P1, P2, …, Pm>；

3. Push(p0, S); Push(p1, S); Push(p2, S);

4. FOR i=3 TO m DO

5.   While Next-to-top(S)、Top(S)和pi形成非左移动 Do

6.       Pop(S);

7.    Push(pi, S);

8. Rerurn S.

关于建立极坐标和排序以及初始化栈即Step1,2,3如下图：

(--图片来源ppt 课件)

关于判断左转，我的想法是转换为判断点和线的关系：

如图判断在当前状态下p2是否要保留，判断p2和p0是否在p1，p3的同侧即可。P2和P0在P1P3的同侧所以P2不符合条件，Pop(p2).

同理判断P3在当前状态下是否保留，判断P3是否与P0位于P1P4同侧，不同侧所以进行保留。

所以第4-7步需要线性时间即可。（每个点最多进栈出栈一次）

但是第二步基于比较的排序最快需要O(nlogn).

所以时间复杂度T(n)=O(nlogn)。

注意事项：

1.      最后节点p10不用判断

2.      关于左转可能有别的思路，我也只是有这样的思路

（三）分治算法

先来看整体算法框架：

Preprocess: (T(n)=O(1))

1.如果|Q|<3, 算法停止；

2.如果|Q|=3, 按照逆时针方向输出CH(Q)的顶点;

Divide:( T(n)=O(n))

选择一个垂直于x-轴的直线把Q划分为基本相等的两个集合QL和QR, QL在QR的左边;

Conquer: (T(n)=2T(n/2))

递归地为QL和QR构造CH(QL)和CH(QR);

Merge: T(n)=O(n)

1.找一个QL的内点p;

2.在CH(QR)中找与p的极角最大和最小顶点u和v;

3.构造如下三个点序列：

(1) 按逆时针方向排列的CH(QL)的所有顶点,

(2) 按逆时针方向排列的CH(QR)从u到v的顶点,

(3) 按顺时针方向排列的CH(QR)从u到v的顶点;

4.合并上述三个序列;

5.在合并的序列上应用Graham-Scan.

详细说明如图

注意此处虽然同样用了Graham-Scan.但是输入数据已经为排序的了，所以可以在线性时间内完成，而不是O(nlogn)。

总时间复杂度T(n)=2T(n/2)+O(n)= O(nlogn)

总结：

分治算法和Graham-Scan时间复杂度均为O(nlogn)，而且事实上最佳状况也是O(nlogn)，

具体证明主要是基于排序问题的最佳时间复杂度为O(nlogn)。

凸包问题Finding the convex hull