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。
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。