首页 > 代码库 > 凸包问题Finding the convex hull

凸包问题Finding the convex hull

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

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

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

输出: CH(Q):Qconvexhull


(一)蛮力法思路:

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

内部点的判断:只要其中三点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-0

2.  按与P-0极角(逆时针方向)大小排序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 课件)

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


(--图片来源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.

详细说明如图

(--图片来源ppt 课件)

注意此处虽然同样用了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