【摘要】：1972年，Graham在“An Afficient Algorithm for Determining the Convex Hull of a Finite Planar set”一文中，提出著名的格雷汉姆凸壳算法。第1步：求点集S中的各点相对于轴OX的倾角P∠iOX；按其倾角P∠iOX，升序排列点集S中其余各点，并仍记之为Pi。第i步：删除格雷汉姆三角形QiOQi+1的所有内点Pi；其中，2≤i≤n1。即如图2.2所示，如果某点Pi不是凸壳顶点，则它必为位于“原点O与凸壳最邻近的两个顶点Qi、Qi+1所成格雷汉姆三角形QiOQi+1”内的一个内点，故应删除这些内点Pi。
2.1.2 格雷汉姆凸壳算法
1972年，Graham在“An Afficient Algorithm for Determining the Convex Hull of a Finite Planar set”一文中，提出著名的格雷汉姆凸壳算法。
一、格雷汉姆凸壳算法描述
如图2.2所示，格雷汉姆凸壳算法的算法思想可概括为：
图2.2 格雷汉姆三角形示意图
第0步：任取点集S={Pi（xi，yi）│1≤i≤m，3≤m＜∞}的一个内点P0作为坐标原点O。
第1步：求点集S中的各点相对于轴OX的倾角P∠iOX；按其倾角P∠iOX，升序排列点集S中其余各点，并仍记之为Pi。其中，1≤i≤m且m≥3。
……
第i步：删除格雷汉姆三角形QiOQi+1的所有内点Pi（注意：各内点均记为点Pi）；其中，2≤i≤n−1。即如图2.2所示，如果某点Pi不是凸壳顶点，则它必为位于“原点O与凸壳最邻近的两个顶点Qi、Qi+1所成格雷汉姆三角形QiOQi+1”内的一个内点，故应删除这些内点Pi。
……
第n−1步：删除格雷汉姆三角形QnOQ1的所有内点Pn。
结束步：输出所求凸壳Q的各顶点Qi，1≤i≤n。
二、格雷汉姆凸壳算法的特点与缺点
首先，格雷汉姆凸壳算法是无误差的精确算法，其次，它存在三个主要缺点：
（1）凸壳的初始顶点Q1与其倾角P∠1OX并无必然的直接联系，故确定其初始顶点Q1的处理效率较低。
（2）格雷汉姆三角形内点的判定，是制约该算法效率提高的瓶颈。
（3）它只能进行串行计算，而不利于并行化，因为其凸壳当前顶点Qi+1依赖于前一顶点Qi。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
