凸包convex hull.pptVIP

凸包convex hull By 张芝源 概念 1 .点集Q的凸包(convex hull)是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。 2 .一组平面上的点，求一个包含所有点的最小的凸多边形，这就是凸包问题了。这可以形象地想成这样：在地上放置一些不可移动的木桩，用一根绳子把他们尽量紧地圈起来，这就是凸包了。 怎么从给定的点中找凸包呢？ 1.卷包裹算法 2. Graham扫描算法 卷包裹算法 可以说是一个很朴素的算法，其时间复杂度最坏情况为O(n^2)，其实现原理非常简单。就像是拿了一根绳子，以最左下方的点开始，围着所有点的外围围了一圈。 先找到横坐标最小的点中纵坐标最小的点，然后以该点作为基准点，对剩余的所有点找到相对当前点的最外侧的点，然后再次以该点作为当前点继续重复直到形成完整的凸包为止。 如何寻找最外侧的点？利用二维向量的叉积公式x1,y1*x2,y2=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单位的面积，问最多能养几只牛。 解法： 直