文档介绍：AdvancedGraphics孙晓鹏博士教授******@,只关注凸包附近的点,从而提高算法的效率最好情况O(nlogn)、最坏情况O(n2),它们是最右最下点pdr和最左最上点pul有向直线pdrpul将整个凸包被划分为右凸包和左凸包对右凸包和左凸包分别进行递归递归设S1是严格在直线pdrpul右边的点集(S1可能是空集)在S1中寻找距离直线pdrpul最远的点,作为pdrpul右边的一个极端点b连接pdr和b,及b和pul把pdr右侧的点集记为A,pul右侧的点集的点记为B对边pdrb和点集A、对边bpul和点集B分别递归调用依次连接凸包上的顶点,得点集S1的凸包,即点集S的右凸包类似地,计算出点集S的左凸包,,(S1可能是空集)在S1中寻找距离直线pdrpul最远的点,作为pdrpul右边的一个极端点b连接pdr和b,及b和pul把pdrb右侧的点集记为A,bpul右侧的点集的点记为B对边pdrb和点集A、,O(nlogn)最坏情况出现在每次划分点的分布都很极端,O(n2),000个点的凸包O(n2)的方法太慢1972年Graham出O(nlogn),O(1)将o作为极坐标的中心,计算每个点的极角θ对S中的点按θ升序排列(如pi,pi+1,pi+2),O(nlogn)计算相邻三点转角的凹凸性,删除内凹的点O(n)当点集内不再包含内凹的点时,,依次对相邻三个点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+2)z≤0说明在pi+1处右转弯,多边形在该点上内凹,把pi+1点从多边形边界中删除后退一步,同样去判断相邻三个点pi-1,pi和pi+2时间复杂度为线性O(n)战江识姜楷淡辈夷拷隙寨孵菌叙剁湖挣感纱流纶究苍哨哼皋泪畴此毋料蛰快速凸包算法快速凸包算法