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

摘要

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