一种新的点集平面点集凸壳构建算法

一种新的点集平面点集凸壳构建算法

0凸壳构建算法凸壳（cov博物馆）也称为凸壳，是指具有指定聚集距离的最小凸集合。在二维情况下,凸壳是由点集中部分点按一定方向顺次连接形成的凸多边形。凸壳是计算几何中一种最普遍、最基本的结构,许多问题可以归结为凸壳问题,凸壳在图像处理、模式识别、计算机图形学等领域有着广泛的应用。常见的凸壳构建算法包括“卷包裹”算法、格雷厄姆算法、分治算法和增量算法。“卷包裹”算法时间复杂度均为O(n2);格雷厄姆算法、分治算法、增量算法时间复杂度均为O(nlogn),但这些算法计算过程都较为麻烦。近年来,又有学者提出新的凸壳构建算法,如2000年周培德提出的Z3-2算法(称文献算法),2006年樊广佺等提出的八方向极值快速凸壳算法(称文献算法),2007年郝建强提出的利用正负划分性求平面点集凸包的算法(称文献算法),2010年吴文周等提出的算法(称文献算法)等。文献算法简化了凸壳计算过程,但由于该算法对凸壳特性利用仍不够(对不参与凸壳构建的点删除程度不够),计算效率仍不高,另外该算法在查找凸壳点的过程中对凸壳边进行不断分裂,随着凸壳边的增多,点到凸壳边距离的计算会变得越来越复杂;文献算法将构建凸壳由以往的四方向极值扩展到八方向极值,初步删除了更多不参与凸壳构建的点,但该算法仍具有与文献算法类似的缺点;文献算法本质上是文献算法的一个改进算法,它简化了求距离最大点过程,但整体运算过程并没有很大程度上的优化;文献算法创造性地应用了分治思想,单纯利用分治减小问题规模,提高了效率,该算法对凸壳点的查找利用了格雷厄姆方法,过程较为麻烦。本文算法在深入研究前人成果的基础上,充分利用凸壳特性,提出一种新的凸壳构建算法。该算法的内核算法极大地加快了求解进程,在凸壳求解过程中,角域以极快的速度收敛,从而迅速逼近凸壳边。为进一步减少绝对运算次数,算法又引入迭代处理思想,从而再次提高算法效率。本文的效率分析和实验测试表明,新算法是一个时间效率高、空间开销少、可行而且稳定的算法。1理论基础1.1y特征点的计算为方便算法依据定理的阐述,先引入几个相关概念,必要时,对这些概念在算法中的运用加以说明。定义1特征点。点集中,X坐标值或Y坐标值具有最值特性的点称为特征点。在二维情况下,对于任意一个给定的点集,总是存在4类特征点:X值最小点、X值最大点、Y值最小点和Y值最大点。把X值最小点和X值最大点统称为X特征点;Y值最小点和Y值最大点统称为Y特征点。显然,特征点位于点集的最小外界矩形上。一个点可以既为X特征点,也为Y特征点,点集中某类特征点也可以不止一个。本文算法中,如果点集中的某点既为X特征点,也为Y特征点,则对这一点分别按X特征点和Y特征点存储;如果点集中某类特征点不止一个,则选取其中一个作为特征点。最终的特征点总数按4个处理。定义2特征项。给特征点以最值特性的坐标项称为特征项。X特征点具有X特征项,Y特征点具有Y特征项。对各特征点按逆时针方向顺次连接,称位于同一条线段上的两特征点为相邻特征点。容易推知,相邻特征点的特征项必然不同。定义3特征轴。过特征点,按其特征项所作的水平线或垂直线称为特征轴,并且称特征轴与该特征点相互关联。对于一个特征点P,如果它具有X特征项,则它关联X特征轴,直线方程为X=P.x;如果它具有Y特征项,则它关联Y特征轴,直线方程为Y=P.y。定义4角域。连接相邻特征点,并分别作过这两个特征点的关联特征轴,形成的直角三角形区域称为角域。如果两相邻特征点对应同一个点,则角域收敛为一个点。定义5特征角。一个点和一个特征点的连线与该特征点的关联特征轴之间的夹角称为该点的特征角。点与X特征点的相连形成的特征角称为X特征角,记为α;点与Y特征点的相连形成的特征角称为Y特征角,记为β。称角域内的所有点中,α值最小的点为α最小点,β值最小的点为β最小点,α最小点和β最小点统称最小角点。特征角的计算方法为,设A为X特征点,B为Y特征点,P为角域内任意一点,则:⎧⎩⎨α(P)=arctan(|P.x−A.xP.y−A.y|),P.y≠A.yβ(P)=arctan(|P.y−B.yP.x−B.x|),P.x≠B.x(1){α(Ρ)=arctan(|Ρ.x-A.xΡ.y-A.y|),Ρ.y≠A.yβ(Ρ)=arctan(|Ρ.y-B.yΡ.x-B.x|),Ρ.x≠B.x(1)上式要求对角域内的任意点,存在P.y≠A.y且P.x≠B.x,事实上在运算中必然成立。当某点P存在P.y=A.y或P.x=B.x时,它必然位于当前角域边界外部,不会纳入当前角域的考察点集(这样的点会在之前的角域处理中被删除)。1.2混合式的聚合点pi、pj定理1点集的特征点一定位于凸壳上。证明由于特征点位于点集的最小外界矩形上,因此,特征点一定位于凸壳上。定理2角域内的最小角点一定位于凸壳上。证明假设角域内的α最小点(设为M)位于凸壳内,角域的X特征点为A。根据凸壳性质,角域内必然存在一点P,使得连接AP后,M位于AP左侧。根据α最小点的定义,M为角域内与X特征轴夹角最小的点,因此M必然位于角域内任意点与A连线的右侧,矛盾。因此,α最小点必定位于凸壳上。对于β最小点可采用同样的方法证明。定理3在角域内,设α最小点为Pi,β最小点为Pj,则:1)如果Pi=Pj,则插入Pi至凸壳后,该角域内的凸壳边构建完毕;2)如果Pi≠Pj,设A为角域内的X特征点,B为Y特征点,顺次连接A、Pi、Pj、B,则在连接线左侧的点不能参与凸壳构建,可以直接删除,且在剩余点集中,Pi是X特征点,Pj是Y特征点。证明首先证明1)。如图1(a),由于Pi=Pj,则点Pi既是α最小点又是β最小点,因此,该角域内不存在其他能参与凸壳构建的点,否则,与Pi既是α最小点又是β最小点矛盾,故此时该角域内的凸壳边构建完毕。接着证明2)。如图1(b),由于在角域内,连接A、B后,A、Pi、Pj、B左侧的点位于多边形APiPjB内部,故这些点不能参与凸壳构建,应予删除。根据特征角的性质,角域内的点必然位于按逆时针方向顺次连接特征点和最小角点构成的折线段(如图APiPjB)的左侧,即剩余点集应位于以两最小角点的连线(如图PiPj)为一条边、以最小角点与相应特征点的连线(如图APi、BPj)之交点为另一个顶点(设为M)的三角形内部。根据α最小点和β最小点的性质,Pi、Pj是三角形PiPjM范围内分别离X特征轴和Y特征轴最近的点,故Pi、Pj分别是剩余点集的X特征点和Y特征点。定理1和定理2给出了凸壳点的选取法则,定理3则回答了如何寻找满足条件的凸壳点以及何时可以终止对凸壳点的查找。定理3是一个重要定理,它说明了新角域的形成法则、新特征点的产生法则以及前后两代特征点之间的继承法则。思考定理3不难发现,而情形1)是情形2)的一种特例:当情形2)退化成情形1)时,新角域退化成一个点,则新的考察点集为空集,所以这个角域内的凸壳边构建完毕。2算法思想和算法描述2.1凸壳定位算法如果不考虑迭代思想,本文算法步骤应该是:首先找到点集内的4个特征点,分别连接相邻个特征点并利用特征轴构建4个(或3个或2个)角域,将点集加入角域(删除不能加入到任何角域的点),然后对各角域逐次查找α最小点和β最小点将其插入凸壳,根据定理3删除不会参与凸壳构建的点同时进行角域更新。角域不断收敛,当所有角域考察点集均为空集时,凸壳构建完毕。称上述过程描述的算法为本文算法的内核算法。内核算法总是会成对查找特征点,并且会最大限度地缩小问题规模点集。尽管内核算法实际上已经非常高效,但当算法的问题规模n很大时,算法中α、β的绝对运算次数仍然很大。考虑到本文算法对非凸壳点的强大的快速删除能力,将迭代思想运用于角域处理:由于凸壳上的顶点必然包含于其子凸壳顶点中,因此当进行角域处理时,如果角域内的点数量大于某个常数(称为问题规模限定数),可以先递归调用本文算法,得到一个子凸壳,将子凸壳的顶点作为角域的输入点集,再执行角域处理。2.2qp模型的建立下面采用伪代码的形式给出算法的完整描述:算法:GetConvexHull(P)。输入:P={pi|i=1,2,…,n};输出:Q={qi|qi∈CH(P),i=0,1,…}。定义算法的问题规模限定数BoundNum;1)检查P中点的数量n;if(n<4)thenQ=P,算法结束;2)在P中找到minY、maxX、maxY、minX4个特征点,依次存放于t、t、t、t、将t到t依次存放于Q;3)初始化4个数组corner、corner、corner、corner;3.1)while(P中的点没有处理完毕)if(pi位于某两相邻特征点连线t[k]t[k+1]的右侧)then将pi加入corner[k];if(pi均位于4条相邻特征点连线的左侧)then将pi从P中删除3.2)清空P4)fori=0to3/*对各角域执行角域处理*/4.1)将t[i]赋给T1,t[i+1]赋给T2,T1、T2为本角域两个初始特征点4.2)while(corner[i].size>0)if(corner[i].size=1)then将corner[i]中唯一的一个点加入Q,清空corner[i]if(corner[i].size>BoundNum)then初始化一个集合Temp递归调用本文算法,将返回结果赋给Temp清空corner[i],并将Temp中的元素赋给corner[i]找到当前角域的α最小点A和β最小点B将A、B按适当的顺序加入Q中,保持点按逆时针排列更新角域特征点T1、T2,使T1=A,T2=B定义变量j,初值为0while(j<corner[i].size)从corner[i]取出第j个点pjif(pj位于线段T1T2的左侧)then将pj从corner[i]中删除5)算法结束。3算法的复杂性分析3.1角域的调节作用本文算法可看成是对点集进行初始划分然后对各角域进行角域处理的过程,在角域处理过程中,不断查找当前角域的特征点并对角域进行更新,角域不断收敛,进而迅速逼近凸壳边界。由于算法在初始划分阶段对非凸壳点的删除比例以及角域处理过程中对非凸壳点的删除比例等都取决于点的分布情况,现运用概率统计相关方法来分析本文算法的时间复杂度。设算法初始输入点数为N,总的运算次数为T(N);初始划分的角域数量为k,经过初始划分后,剩余点数与初始输入点总数之比为a;在角域处理过程中,对问题规模为n的点集,基本运算次数为F(n)。由于算法在初始划分阶段需要遍历所有点以划分角域,然后执行角域处理,故:设角域处理时,问题规模限定数为B。对于点数为n的角域,当n<B时,基本运算次数为f(n),由于此时的过程是先求解n次α角和β角以得到最小α点和最小β点,如果它们对应同一个点(设这样的概率为p),则该角域处理结束,否则,以这两个点为新的X特征点和Y特征点对新的角域执行角域处理(设新角域点数与原角域点数之比为b);当n≥B时,则先递归调用本文算法以减小问题规模(设问题规模减小比例的平均值为c),然后执行与n<B时的相似的处理过程。则F(n)满足下式:F(n)={f(n),n＜BT(n)+f(cn),n≥BF(n)={f(n),n＜BΤ(n)+f(cn),n≥B;c∈(0,1)(3)f(n)满足下列关系式:{f(n)=n+p×0+(1−p)f(bn);p,b∈(0,1)f(0)=0(4){f(n)=n+p×0+(1-p)f(bn);p,b∈(0,1)f(0)=0(4)解f(n),再将f(n)代入式(2)得:F(n)={n1−(1−p)b,n＜BT(n)+cn1−(1−p)b,n≥BF(n)={n1-(1-p)b,n＜BΤ(n)+cn1-(1-p)b,n≥B;a,b,c,p∈(0,1)(5)由于经过初试划分之后,各角域内点的数量不尽相同,因此T(N)的表达式不易确定。下面考虑两种特殊情况,并且这两种情况下各角域内的点均匀分布。情况1n1到nk均小于B时。各角域的表达式为:F(ni)=ni1−(1−p)bF(ni)=ni1-(1-p)b;i=1,2,…,k(6)联立式(2)和式(6),解方程组得:T(N)=N⋅(1+a1−(1−p)b)Τ(Ν)=Ν⋅(1+a1-(1-p)b);a,b,p∈(0,1)(7)情况2n1到nk均大于或等于B且各角域内经过递归处理后,点的数量仍大于或等于B时(相当于是各角域内的点数均为无限多的情况)。各角域F(n)的表达式为:F(ni)=T(ni)+cni1−(1−p)bF(ni)=Τ(ni)+cni1-(1-p)b;i=1,2,…,k(8)联立式(2)和式(7),解方程组得:T(N)=N⋅{1+[1+c1−(1−p)b]⋅a1−a};Τ(Ν)=Ν⋅{1+[1+c1-(1-p)b]⋅a1-a};a,b,c,p∈(0,1)(9)由于a、b、c、p均与点的分布特点相关,而与点的数量N无关,因此,从式(7)和式(9)可知,上述两种情况下,算法时间复杂度均为线性次。由于上述两种情况代表了点数很少和点数极多两种极限情况,实际情况总是介于两者之间,且算法复杂度与点的分布无关,因此,本文算法时间复杂度为线性次,即O(n)。算法的具体运算次数与点的分布状态相关,不同状态分布的点,算法运行时间线性增长的情况会有不同。3.2角域的收敛显然,本文算法中占用空间最多的时候是刚开始时进行角域划分的时候,以后,随着算法的运行,角域逐渐收敛,所需要存储的点数也随之减少。因此,本文算法的空间复杂度为O(n)。4材料2.2不设置在真核和弘扬竞争优势的同时进行计算为评价本文算法运行效率,采用两种不同坐标尺度和分布特征的数据进行了实验,并与经典的Graham算法进行了对比。实验数据均采用计算机代码产生的随机点(随机方式不同),第一组数据坐标范围约为X∈(100,1600),Y∈(80,700),第二组数据坐标范围约为X∈(0,300000),Y∈(0,150000)。图2(a)、2(b)分别是对两组数据中,点数为200万的文件点及其凸壳可视化后的效果图,表1、2分别为对两组数据用Graham算法和本文算法将各数据测试多次后的时间统计表(由于当点数达到20万时,Graham算法运行速度较慢,与本文算法相比已经出现很大差距,对Graham算法进一步测试意义不大,因此,对于20万以上的数据,本文没有进行进一步实验)。本试验采用的计算机主频为2.2GHz,内存为2