2007-08-23
凸壳串行算法介绍 - [Algorithms]
版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://conoon.blogbus.com/logs/7872461.html
关于凸壳的串行算法，可以说有好多种，有时间复杂度O(n^2)的，也有O(nlogn)的，下面依次介绍几种算法：
1，我认为最土的一种方法，时间复杂度为O(n^2) 叫做 卷包裹法
由Chand 和 Kapur 于1970年提出，基本思想：首先过y坐标最小的点p1画一条水平直线L,显然该点是凸壳的一个顶点。然后L绕p1按逆时针方向旋转，碰到S(顶点集合)中的第二个点p2时，直线绕p2按逆时针旋转而在p1,p2之间留下一条线，该线段为凸壳的一条边。继续旋转下去，最后直线L旋转360度回到p1,便得到所求的凸壳
直线L绕点pi旋转式通过一下方法实现的：首先连接Pi与非凸壳顶点Pj，j = i+1,...,n,得到线段PiPj,然后求这些线段与Ｌ(线段Pi-1Pi)的夹角，组成最小夹角的另一端点Pi+1就是凸壳顶点
这个很显然时间复杂度为O(n^2)，伪代码在此就省略了！
注意一点：就是当有三点或者以上的点共线时，如果只能算两个端点上的点，中间的其他点不计，在算法执行中要另外判断，当最小角度有好几个的时候，要选一个距离最远的一个点
2，最优的求凸壳算法：格雷厄姆方法
1972年，格雷厄姆发表的一篇题为"An efficient algorithm for determining the convex hull of a finite planar set"的著名论文中所提出的方法
主要依据是凸边的定义：凸多边形的各顶点必在该多边形的任意一条边的同一侧。
此方法步骤如下：
1，设凸集中y坐标最小的点为p1,把p1同凸集中其他各点用线段连接，并计算这些线段与水平线的夹角。然后按夹角大小及到p1的距离进行词典分类(先按夹角的大小排序，当夹角一样时，按到p1的距离进行排序)，得到一个序列p1,p2,...,pn，依次连接这些点，便得到一个多边形。p1点是凸壳边界的起点，p2与pn也必是凸壳的顶点。Pn+1 = P1！还不知道如何插入图片，现在先用如下简陋的图表示一下，按顶点编号连成一个多边形
。6
7 。 。4
。5
8 。 。3
。9 。2
。1
大概判断过程：
k=4,向前倒查，p1与p4在Pk-1Pk-2两侧，所以p3不在凸壳边界上，删去p3,原p4成为p3,之后p1和p4在Pk-1Pk-2同侧，p3暂时在边界上，继续查下去，最后可以得到凸壳的６个顶点
2，删去p3,p4,...,pn-1中不是凸壳上的点，方法如下：
begin
1 k = 4
2 j = 2
3 if P1 和 Pk 分别在线段Pk-j+1 Pk-j两侧 then 删去 Pk-1,后继顶点编号减1，k = k-1,j = j-1
else Pk-1暂为凸壳顶点，并记录
4 j = j+1 ,go to 3,直到 j = k-1
5 k = k+1,go to 2,直到 k = n+1//注意，因为节点编号随着节点的删除是在不断减少的，所以在算法过程中n也是在不断减少的
end
3,顺序输出凸壳顶点
其中：判断两点在某一个线段两侧还是同侧，用向量叉乘就行了
比如说有两点p,q，线段AB则计算向量pA,pB,qA,qB;在计算叉乘pA*pB,qA*qB如果同号说明在线段同侧，否则在异侧！另外如果计算出现零，则说明那一点在那个线段上，即出现多点共线的情况
算法分析：由于点集有n个点，步骤2中转移到2的次数不会超过n，每一个顶点至多删去1次，删去顶点的个数也不可能超过n。因此步骤2是线性时间复杂度；步骤1很显然涉及到角度的排序问题，为O(nlogn)复杂度；所以总共需要O(nlogn)时间，此算法为最优算法！因为可以证明凸壳的最优算法的下界就是OMIGA(nlogn)
3 分治算法
Preparata 和 Hong 1977年 把分治算法首先应用于凸壳问题，为了描述问题方便，还是假定没有3点共线(其实共线的处理方法也很简单)
算法：
输入： n个点集合
输出：返回凸壳的顶点列表
Procedure SEQUENTIAL CONVEX HULL(S,CH(S))
Begin
if |S|<= 3 then CH(S) = S
else /*把S分为两组大小近似的S1,S2,递归调用*/
1 SEQUENTIAL CONVEX HULL(S1,CH(S1))
2 SEQUENTIAL CONVEX HULL(S2,CH(S2))
3 ./*归并*/ O(n)
Merge CH(S1) and CH(S2) into CH(S)
end if
end
t(n) = O(nlogn)
下面介绍归并算法：
1,在S1内部找一个点p,必须是S中的点
2,if p 不在 S2的内部 then goto 4
3,p在S2内部，S1，S2的各顶点与p连接，并按夹角大小进行分类，得到S1,S2顶点的一个分类表，goto 5
//O(n)!相当于把2个按夹角分类的有序的顶点合并成一个按夹角有序的顶点
4,计算p与S2的正切线，得到正切点u，v。相当于通过删除若干条边使得把p添加到多边形S2中，再根据类似4的做法，得到一个按夹角分类的顶点分类表 //O(n)
5, 在顶点分类表上执行格雷厄姆方法的第二个步骤，就可以得到一个合并的凸壳了// O(n)
还有其他几种方法，包括实时凸壳算法，近似凸壳算法，在此就不介绍了，有可能会在其他环境下介绍
以上内容主要参考了 周培德 著的 计算几何-算法设计与分析 第二版的相关内容
随机文章：
收藏到：Del.icio.us
