【摘要】：首先，卷包裹凸壳算法较真实地反映了凸壳的自然态同构化特点，是如图2.1所示橡皮带外绕法的圈绕朴素模拟与计算机实现。因此，它有两个主要缺点：若该转角设定过小，则凸壳精度较高但算法效率偏低；反之，若该转角设定过大，则凸壳算法效率较高而精度偏低。它只能进行串行计算，而不利于并行化，因其凸壳当前顶点Qi+1依赖于前一顶点Qi。
2.1.1 卷包裹凸壳算法
1970年，D. Chand和S.Kapur提出较有代表性的卷包裹凸壳算法。
一、卷包裹凸壳算法描述
如图2.1所示，卷包裹凸壳算法的算法思想可概括为：
第0步：取二维有限点集S={Pi（xi，yi）│1≤i≤m，3≤m＜∞}的点P1（x1，y1），使y1=min{yi│1≤i≤m，3≤m＜+∞}；显然，点P1就是凸壳Q的初始顶点Q1（即第1个顶点）；过点Q1画一水平直线L。
……
第i步：使L改绕顶点Qi按逆时针方向旋转若干个转角Δ，可碰到S中的第i+1个点Pi+1；而点P i+1就是凸壳Q的第i+1个顶点Q i+1，且线段Q iQ i+1就是凸壳Q的第i个边。其中，1≤i≤n−1；3≤n≤m＜+∞。
……
第n步：使L改绕顶点Qn按逆时针方向旋转若干个转角Δ而转回初始顶点Q1，且线段QnQ 1就是凸壳Q的第n条边。
结束步：输出所求凸壳Q的各顶点Qi，1≤i≤n。
二、卷包裹凸壳算法的特点与弱点
首先，卷包裹凸壳算法较真实地反映了凸壳的自然态同构化特点，是如图2.1所示橡皮带外绕法的圈绕朴素模拟与计算机实现。其次，它显然仅可无误差地确定其初始顶点Q1，而对其他顶点Qi的确定都可能存在误差（即：其凸壳精度、算法效率都取决于它每次按逆时针方向旋转时的固定转角）。因此，它有两个主要缺点：（1）若该转角设定过小，则凸壳精度较高但算法效率偏低；反之，若该转角设定过大，则凸壳算法效率较高而精度偏低。（2）它只能进行串行计算，而不利于并行化，因其凸壳当前顶点Qi+1依赖于前一顶点Qi。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
