资源描述：
《浅谈二维凸包及其应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、肉淡二维E包及其应用F0503028陆箴学号:5050309947【摘要】凸包是计算儿何中最普遍、最基本的一种结构，本文介绍了二维凸包的概念和性质，并介绍儿种求二维凸包的方法:Gift・Wrapping、Graham-Scan算法，以及这儿种算法的正确性和时间复杂度的分析，最示通过两个实例来简要介绍二维凸包的应用。【关键字】凸包、Gift-Wrapping>Graham-Scan、水平序、极角序【目录】1.凸包的概念和性质2.凸包的实顼3.算法的效母豆4.凸包的应用【正文】作为计算儿何中笫一个被深入研究的儿何模型，凸包以其优美的性质
2、带來了广泛的应用，本文将对这个儿何模型进行•简要的介绍。1.凸包的概念和性质我们首先从一个实例來引入凸包：【例1・1】假设你种了很多树，想用一个篱笆把所有的树都包在里面，出于经济考虑，显然这个篱笆应该是越小越好。给出树的坐标，求出篱笆的授小周长。如图1・1所示的篱笆是一个最小的篱笆。图1・1而这个篱笆就是这些树的凸包(ConvexHui1)。要定义凸包，首先我们来研究一下凸多边形。定义1凸多边形O整个图形在任一条边的一侧。定义2D是□多边形oVX,X2GZ),D.BIJ对于一个凸多边形，任意两个内点的中点，也在此图形内。更一半化地，
3、我们不仅考虑中点，还考虑所冇内分点，于是有如下定义。定义3D是凸多边形o▽兀]，上wZ),VAg[0,1],2兀+(1—久)兀2丘D因此定义2是定义3的一种特殊形式。如图1.2给出了凸图形和凹图形的图示：凹图形凸图形图1.2设S是平面(£)上的点集，用CH⑸表示点集S的凸包,BC1KS)表示S的凸包边界。定义4平而点集S的凸包CH(S)是包含S的最小凸集，凸包上的顶点称为极点。点集S的凸包是包含S的所冇，集的并，或者CH(S)是包含S的所冇半空间的交。二维中的半空间是半平面，它是指位于一条直线上及该线一侧的点的集合。定义5平面点集S
4、的凸包边界BCH(S)是一凸多边形，英顶点为S中的点。BCH⑸是包围S的最小凸多边形P,即不存在多边形P'，使得P二P=S成立。BCH⑸是具有最小面积并且封闭的凸多边形西P,或者是具有最小周长并封闭的凸多边形Po由此也验证了例1中最省材料的篱笆即为这些树的凸包。1.凸包的实现1.Gift-Wrapping算法Gift-Wrapping算法是凸包问题的最直观的一种解法Gift-Wrapping算法是Chand和Kapur于1970年提出的,其基本思想如下:首先过y坐标最小的点P】，画一水平直线1,显然该点是凸包的一个顶点。然后1绕P】
5、按逆时针方向旋转，碰到S中的笫二个点P2时，直线1改绕P2按逆时针方向旋转而在pi与P2之间留下一条线段，该线段为凸包的一条边。继续旋转下去，最示直线1旋转360。回到P1,便得到所要求的凸包。直线1绕点Pi,的旋转是通过如下方法实现的：首先连接Pi少非凸顶点pl,j=i+Vn，得到线段PrPj,然后求这些线段与1(pj},p)的夹角，组成最小夹角的另一端点PiH即凸包顶点。如图2.1所示,Gift-Wrapping算法的基本思想:(参考文献[2])图2・1Gift-Trapping算法的基本思想下而给出Gift-Wrapping算
6、法的实现步骤：(参考文献[3])Step1计算yi,y2・・・yn,中的最小值,其对于点设为Pi。Step2从pi向右引一条水平射线，记为lpioStep3计算"1刃与lpi的夹角的最小值所对应的点，记为P2。Step4j<-l,k<-3,m<-2oStep5以pjpj+代替pj-、pj，计算pj+'pi,pjpj+1的夹角最小值所対应的点，记为P“Step6j<-j+l,k<-k+l,gotostep5,直至pk为Pi。算法中的Step1耗费n-1此比较,Step2需要常数时间,Step3需计算夹角n-1次，然后耗费次比较可以求
7、得QrStep4〜6循环「2次，每次循环需要计算夹角n-i-1次,比较n-i-2次，i=l,n-2oStep7耗费常数时间。因此,算法的时间复杂度为0(n2)o2.Graham-Scan算法刚才讲的Gift-Wrapping算法虽然肓观易懂，但是时间复杂度很高，那么有没有其他更高效率的算法呢？Gift-Wrapping算法的每一步都确定性的得到一条最终凸包上的边，能否换个思路，不追求每步必朝最终凸包前进一步，而是考虑“临时凸包”或“局部凸包”。这种凸包是试探性增长的，目前凸包上的边不一定都是将來凸包上的边，而是通过逐步纠正错谋来逼近
8、“最终凸包”的。例如对于一个简单的凹多边形，我们尝试从5开始，沿着多边形的顺序，试探性地增长凸包，如图2.2所示：P3图2.2Graham-Scan:试探性增长凸包选择最低点P1作为起点，只要向左转就将这个点添加至临时凸包屮，继续扩展
