快速凸包算法

《快速凸包算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、AdvancedGraphics孙晓鹏博士教授cadcg2008@gmail.com2011年11月16日第二章二维凸包2.4凸包的快速算法主要思想点集S的凸包是取决于凸包边界附近的点逐步丢掉凸包内部的点，只关注凸包附近的点，从而提高算法的效率最好情况O(nlogn)、最坏情况O(n2)2.4凸包的快速算法算法过程取两个极端点，它们是最右最下点pdr和最左最上点pul有向直线pdrpul将整个凸包被划分为右凸包和左凸包对右凸包和左凸包分别进行递归递归设S1是严格在直线pdrpul右边的点集（S1可能是空集）在S1中寻找距离直线pdrpul最远

2、的点，作为pdrpul右边的一个极端点b连接pdr和b，及b和pul把pdr右侧的点集记为A，pul右侧的点集的点记为B对边pdrb和点集A、对边bpul和点集B分别递归调用依次连接凸包上的顶点，得点集S1的凸包，即点集S的右凸包类似地，计算出点集S的左凸包，从而得到整个点集S的凸包2.4凸包的快速算法算法过程取两个极端点，它们是最右最下点pdr和最左最上点pul有向直线pdrpul将整个凸包被划分为右凸包和左凸包对右凸包和左凸包分别进行递归2.4凸包的快速算法算法过程递归设S1是严格在直线pdrpul右边的点集（S1可能是空集）在S1中寻找

3、距离直线pdrpul最远的点，作为pdrpul右边的一个极端点b连接pdr和b，及b和pul把pdrb右侧的点集记为A，bpul右侧的点集的点记为B对边pdrb和点集A、对边bpul和点集B分别递归调用2.4凸包的快速算法最好情况出现在每次划分均是平衡的,O(nlogn)最坏情况出现在每次划分点的分布都很极端,O(n2)2.5Graham算法20世纪60年代末贝尔实验室需要求解10,000个点的凸包O(n2)的方法太慢1972年Graham出O(nlogn)的二维凸包算法2.5Graham算法基本思想在凸包内部找到一个点o如S中任何三个不共线

4、的点的重心，O(1)将o作为极坐标的中心，计算每个点的极角θ对S中的点按θ升序排列（如pi，pi+1，pi+2），O(nlogn)计算相邻三点转角的凹凸性，删除内凹的点O(n)当点集内不再包含内凹的点时，得到凸包2.5Graham算法以极端点pi为初始点，依次对相邻三个点pi，pi+1和pi+2，计算pipi+1×pi+1pi+2如果在z轴上的投影大于零，即(pipi+1×pi+1pi+2)z＞0说明在pi+1处左转弯，多边形在该点上外凸，暂时保留这三点前进一步，同样去判断相邻三个点pi+1，pi+2和pi+3如果(pipi+1×pi+1pi

5、+2)z≤0说明在pi+1处右转弯，多边形在该点上内凹，把pi+1点从多边形边界中删除后退一步，同样去判断相邻三个点pi-1，pi和pi+2时间复杂度为线性O(n)凸包计算方法对比极端边算法O(n3)礼品包裹算法O(n2)快速算法最好情况O(nlogn)、最坏情况O(n2)Graham算法排序计算O(nlogn)、执行时间O(n)总的时间复杂度O(nlogn)第三章凸包扩展3.1多面体两个集合是同胚的(homeomorphic)指它们之间存在一个连续的一一映射并且这个映射的逆映射也是连续的两个同胚的集合允许它们各自拉伸和扭曲，但只要不撕裂，其

6、结果仍然同胚如果任一集合被撕裂了，映射的连续性便被破坏，两个集合就不再同胚了3.1多面体两个集合是同胚的(homeomorphic)三黑点的邻域都不能同胚于一个三维的半开半闭的半球a和b中黑点的邻域同胚于两个接触于一条线或一个点的三维的半开半闭的半球c中黑点的邻域是同胚于半个二维开圆盘3.1多面体3.1.1多面体定义三维空间中的多面体是由有限个平面多边形围成的区域，其边界满足下列三个条件多面体表面上的每一对面，它们或者是分离的、或者有一个公共顶点、或者有一条公共的边如果把多面体看成一个实心的实体，表面上任一点的足够小的邻域同胚于一个三维的如下

7、定义的半开半闭的半球。半开半闭的半球定义为x2+y2+z2＜r2和z≤０的交，其中r为半球的半径多面体表面是连通的，即表面上任意两点可通过完全在表面上的路径连接3.1多面体如果把多面体看成厚度为零的多边形围成的空间，第二个条件也可写为多面体表面上任一点，它在表面上的邻域同胚于一个开圆盘，开圆盘是二维的开圆如果一个表面上的每一个点都满足这个条件，那么这个表面就被称为二维流形(2Dmanifold)3.1多面体第３个条件表示顶点和边组成的图是连通的排除那些有“浮在”表面里面的顶点和边的物体3.1多面体多面体可以存在“通孔(hole)”，从多面体表

8、面的一面通到另一面多面体允许有任意多个这样的孔，孔的数目叫做这个体的亏格(genus)亏格为0的多面体在拓扑上同胚于球亏格为1的多面体在拓扑上同胚于圆环面凸多面体又