求平面点集凸壳的一个最优算法

本文提出了一个求平面点集凸壳的格雷厄姆方法的一个改进算法。算法首先按照格雷厄姆方法将点集中的点进行分类，将分类后的点连成一个特殊的简单多边形，然后删去简单多边形的单个凹点、连续凹点，产生新的简单多边形，再删去新简单多边形的单个凹点及连续凹点，循环往复，最后得到的凸多边形即为点集凸壳的边界。本算法理论严密，易于理解，易于实现，时间复杂性也是。