凸包convexhullppt课件.ppt

凸包convex hullBy 张芝源概念•1 .点集Q的凸包(convex hull)是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内•2 .一组平面上的点，求一个包含所有点的最小的凸多边形，这就是凸包问题了这可以形象地想成这样：在地上放置一些不可移动的木桩，用一根绳子把他们尽量紧地圈起来，这就是凸包了怎么从给定的点中找凸包呢？1.卷包裹算法卷包裹算法2. Graham扫描算法扫描算法卷包裹算法卷包裹算法可以说是一个很朴素的算法，其时间复杂度最坏情况为O(n^2)，其实现原理非常简单就像是拿了一根绳子，以最左下方的点开始，围着所有点的外围围了一圈先找到横坐标最小的点中纵坐标最小的点，然后以该点作为基准点，对剩余的所有点找到相对当前点的最外侧的点，然后再次以该点作为当前点继续重复直到形成完整的凸包为止如何寻找最外侧的点？利用二维向量的叉积公式*=x1*y2-x2*y1，向量A乘以向量B 如果为正则为A逆时针旋转向B 否则为顺时针如下图所示，向量JK和JI的叉积为负数，因此JI在外侧这样得到的凸包是按照逆时针方向排序的H代表凸包上点的数目，这样时间复杂度为O(HN)。

Graham扫描算法扫描算法(Graham Scan Algorithm)Graham扫描算法维护一个凸壳凸壳 通过不断在凸壳中加入新的点加入新的点和去除影响凸性影响凸性的点 最后形成凸包这里主要介绍Graham，因为最坏情况下时间复杂度为O(NlogN)，而且实现简单起来不难，因此这是比赛时候的首选算法Graham算法先对点进行排序，有极角序和水平序两种排序方式我们仍然以左下方的点作为基准点来通过叉积进行排序利用STL里面的sort或者自己写个排序算法，排序所用时间为O(NlogN)，极角序列如左图所示：极角排序以参考点为极角坐标系原点极角坐标系原点 各个点的极角极角为关键字水平序如右图所示：以横坐标横坐标为第一关键字，纵坐标纵坐标为第二关键字，排序点集然后从第一个点开始 分别利用Graham扫描生成左链左链和右链右链排序之后有何作用？请看下一页Graham的栈扫描的栈扫描Graham的扫描是一个很优美的过程，用到的数据结构也很简单，仅仅是一个栈而已核心的思想是按照排好的序，依次加入新点得到新的边如果和上一条边成左转关系就压栈继续成左转关系就压栈继续，如果右转就弹栈直到和栈顶两点的边成左弹栈直到和栈顶两点的边成左转关系转关系 压栈继续。

压栈继续实现的时候我们不用存边，只需要含顺序在栈里存点，相邻两点就是一条边由于我们时时刻刻都保证栈内是一个凸壳时时刻刻都保证栈内是一个凸壳 所以最后扫描完毕，就得到了一个凸包栈扫描的过程如下面两图所示：（当搜索到点5，6的时候，该边向右转，点5出栈，边46还是向右转，再出栈，边36左转，因此继续下一步由于每点出栈入栈最多一次，因此时间复杂度为O(n)，算法总的时间复杂度为O(NlogN)给个完整的图演示一遍全过程:共线点问题共线点问题凸包有个很大的问题，就是当三点共线时候的处理问题而且Graham扫描算法的共线问题更复杂共线问题更复杂 ，所以需要仔细考虑1.排序时的共线问题排序时的共线问题如果极角相同 我们应该怎么定先后呢?我们得加上第二关键字距离第二关键字距离，比如极角相同，距离参考点近的先不过不管是近的先还是，远的先，开始和结束的两条边总是矛盾总是矛盾的我们必须对其中一条特殊处理，除了结束边外距离近的先结束边外距离近的先 结束边上距离远的先结束边上距离远的先这就是为什么极角排序不是很好实现的原因了2.扫描时的共线问题扫描时的共线问题如果需要保留共线的点就在到角相同时取距离最近的。

如果仅仅需要凸包极点就取距离最远的Graham模版（水平序）模版（水平序） by 吉林大学吉林大学:凸包问题:凸包问题一般有以下两类：1.求凸包面积周长2.求平面最远点对平面最远点对凸包面积周长凸包面积周长 我们先来看一个问题，POJ 1113 题意:有个贪心的国王叫他的建筑师给他的城堡周围建个围墙,他要求用最少的石头和劳动力来建造,而且要在距离城堡某个距离L之外建造解法： 这是一个凸包问题,就是给出一些点的坐标,然后求能围住所有这些点的最小周长,这里采用Graham扫描算法并采用水平序的排序方式(即按y坐标排序,坐标相同的再按x坐标排序)来求解,把扫描过程分成两步,右链和左链,先做左链,从最低点到最高点,再反向做左链(已经生成在右链上的点不需要考虑),从最高点到最低点. 由于建造的围墙距离城堡还有一个距离L,故要求的周长还要比已经求出来的凸包多一段距离,所以结果=凸包周长+圆的周长,圆半径是L,就是围墙离开城堡的距离.P.S：用吉林大学的模版可以迅速搞定该题目我们再来看一个问题，POJ 3348题意：一片草地上有n课树，现在你想用绳子圈出一个尽可能大的面积出来养牛。

已知每只牛需要50单位的面积，问最多能养几只牛解法：直接用什么卷包裹，graham扫描，步进法，快速扫描等任意方法找出凸包，然后直接计算面积即可无任何难度纯属水题计算面积有两个方法，一个是海伦公式算到你头脑爆炸，另外一个方法就是直接利用叉积的另外一个性质，叉积等于有向三角形面积的一半P.S：用吉林大学的模版还是可以迅速搞定…平面最远点对平面最远点对这回不先看问题了，我们先来想想，在一个点集中求两个距离最大的点的距离应该怎么求首先当然还是要先找出凸包然后很明显的，这两个点必定在凸包上，不然无解知道了点对在凸包上，接下来还要找出最远点对其中最朴素的方法就是直接枚举，如果点集比较诡异，像一个圆形一样（如下图），那么这种方法最坏的情况就会达到O(n^2)那么怎么解决这种问题呢？似乎讲到这里应该开始介绍旋转卡壳算法了不过其实除了旋转卡壳之外，还有别的方法也可以做出这个答案的简单的说，就是随机算法我当时过某题的随机方法，是先随机找一个点，然后找出跟该点距离最远的点然后以这个距离最远的点作为基准点，再找出距离该点距离最远的点，直到没有新的点出现此时，再随机选择一个点执行一样的步骤那么算法就是O(nT),其中T是随机的次数，这个随机的次数关系到你撞对答案的概率。

那么我一般推荐T是n的根号或者是一个固定的常数，这样过题的概率很大好了，还是继续讲旋转卡壳吧旋转卡壳算法：旋转卡壳算法：这是一个非常优美而高效的算法（演示图如下）：旋转卡壳算法旋转卡壳算法是解决一些与凸包有关问题的有效算法 就像一对卡壳卡住凸包旋转而得名被一对卡壳正好卡住的对应点对称为对踵点对踵点(Antipodal point)，，可以证明对踵点的个数不超过3N/2个 也就是说对踵点的个数是O(N)的，对踵点的个数也是解决问题的时间复杂度的保证如何寻找对踵点呢？如图所示，一个对踵点和对应边之间的距离比其他点要大如图所示，一个对踵点和对应边之间的距离比其他点要大也就是一个对踵点和对应边所形成的三角形三角形是最大的，我们可以据此得到对踵点的简化求法寻找对踵点寻找对踵点如果按照刚才的思路，只是单纯的根据边来寻找点，那么时间复杂度仍然是O(N^2)，因此我们必须想办法增强我们的效率我们可以发现，如果我们逆时针方向寻找边的对踵点的话，只要找到了第一个点，那么接下来的点必然也是按照逆时针方向顺序排列的于是根据这个性质，我们只要求出第一个对踵点，接下来的点都可以按顺序找出来，这样所用的时间复杂度只是O(N)。

最后在寻找点的时候同时计算点的距离，这样就可以在寻找点的同时算得最远点对P.S：一个点的对踵点并不是离这个点最远的点一个点的对踵点并不是离这个点最远的点!如图所示，此外，一个点的对踵点不如图所示，此外，一个点的对踵点不止一个！止一个！自己改的一份模版自己改的一份模版思路和刚才讲的差不多思路和刚才讲的差不多//旋转卡壳旋转卡壳,输入凸包输入凸包res，顶点个数为，顶点个数为n，按逆时针，按逆时针排列排列//输出输出直径的平方直径的平方,cross为叉积，为叉积，dist2为距离的平方为距离的平方double rotating_calipers(point res[],int n){ int q=1; double ans=0; res[n]=res[0]; for(int p=0;pfabs(cross(res[p+1],res[p],res[q]))) q=(q+1)%n; ans=max(ans,max(dist2(res[p],res[q]),dist2(res[p+1],res[q+1]))); } return ans;}旋转卡壳的应用旋转卡壳的应用旋转卡壳主要是用来求点集中最远点对的。

如POJ 2187，就是一道求最远点对的裸题学会了旋转卡壳用模版可以直接过具体参照codePOJ 3608，求两个凸包间的最短距离个人解法：先求出两个凸包，然后对其中一个凸包的左下方的基准点，对另外一个凸包求最小对应边然后再从另外一个凸包的左下方的基准点，对前个凸包求最小对应边最后比较求得的，各点间距离，各点线间距离，各边边间距离，最后得到两个凸包间的最短距离下图为三种情况）高维凸包目前得知的三维凸包的解法一般都是先构建最小凸包，然后增点，再构造凸包，把所有的点加入后求得三维凸包这种方法为朴素的方法，至于优化的方法，正在努力中…高维的连论文都看不懂…残念…Be continue…练习•Poj 1113 凸包周长（水题）•Poj 2187 凸包面积 （水题）•Poj 3348 最远点对•Poj 3608 凸包间最小距离（参考代码来自网上）•Poj 3528 三维凸包 （参考代码来自网上）•Hdu 3662 三维凸包（参考代码来自网上）P.S：稍后补上三份本人写的代码与思路。