2.1.3 折半分治凸壳算法
基于分治技术与递归方法的折半分治凸壳算法,其算法效率高于卷包裹凸壳算法、格雷汉姆凸壳算法,且总运行时间为t(m)=O(m log m)。
一、折半分治凸壳算法描述
如图2.3所示,折半分治凸壳算法的算法思想可简述如下:
图2.3 凸壳Q的“Q上1、Q上2的上公切线,Q下1、Q下2的下公切线”示意图
第0步:使初始二维点集S={Pi(xi,yi)│1≤i≤m,3≤m<∞}的点Pj(xj ,yj ),满足xj ≤xj +1,其中1≤j≤m−1,3≤m<+∞。并以初始点集S的最左点P左、最右点P右为端点的线段作上下分界线,把S分为上下两个子点集S上、S下(例如图2.3中,当m=11时,X轴座标值最小、最大点P1、P11,分别为初始点集S的最左点P左、最右点P右,且除这两点P1、P11外,还把点集S分为上子点集S上={P2,P4,P6,P8,P9},下子点集S下={P3,P5,P7,P10})。
第1步:调用递归子算法UH(S上),以生成上凸壳Q上。
(1)如果当前m≤3,则当前点集S上中各点就是S上对应凸壳的各顶点,并返回调用点;否则,执行(2)。
(2)按点数近似等量分治原则,把当前点集S上折半划分为两个“中间工作子点集”S上1、S上2。
(3)以S上1为新S上,递归调用上凸壳生成递归算法UH(S上),并生成S上1的凸壳上1。
(4)以S上2为新S上,递归调用上凸壳生成递归算法UH(S上),并生成S上2的凸壳上2。
(5)构造凸壳上1和凸壳上2的上公切线(例如图2.3所示的上虚线Q8Q7),把凸壳上1、凸壳上2合并为上凸壳Q上。
第2步:调用递归算法UH(S下),以生成下凸壳。
(1)如果当前m≤3,则当前点集S下中各点就是S下对应凸壳的各顶点,并返回调用点;否则,执行(2)。
(2)按点数近似等量分治原则,把当前点集S下折半划分为两工作子点集S下1、S下2。
(3)以S下1为新S下,递归调用下凸壳生成递归算法UH(S下),并生成S下1的凸壳下1。
(4)以S下2为新S下,递归调用下凸壳生成递归算法UH(S下),并生成S下2的凸壳下2。
(5)构造凸壳下1和凸壳下2的下公切线(例如图2.3所示下虚线Q2Q3),把凸壳下1、凸壳下2合并为下凸壳Q下。
第3步:把上凸壳Q上与下凸壳Q下合而为一,并生成凸壳Q
(例如图2.3所示凸多边形Q1Q2Q3Q4Q5Q6Q7Q8)。
结束步:输出所求凸壳Q的各顶点Qi,1≤i≤n。
二、折半分治凸壳算法的特点与缺点
首先,折半分治凸壳算法是无误差的精确算法。
其次,它存在两个主要缺点:
(1)由于采用递归,故其算法效率不高。
(2)子凸壳无效边越多,则其效率越低。例如:仅就上凸壳生成处理而言,在“以上公切线QiQi+1为一腰、上下分界线为另一腰,而点Qi、Qi+1的Y向坐标线为上、下底”所构成梯形(实际上,完全可扩大到:在“以上公切线QiQi+1为一边,而以分界线P左P右为其对边;Qi+1P左为另一边,而以QiP右为其对边”所构成凸四边形P左P右Qi+1Qi)内,若所包含的S上1、S上2各自的点越多,则该算法所作的子凸壳的无效边就越多,因而会更降低其算法效率(如图2.3:细线所示非凸壳Q边的各无效边及其冗余处理,就颇为不少)。
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。