一种给定平面点集凸壳算法

摘要

凸壳问题是计算机图形学、图像处理、模式识别等众多领域中的一个基本问题.将正切线算法应用到给定平面点集凸壳的计算中,并实现了正切线算法中新加入点的自动编号.通过极值点把点集分成若干个区域,对于点集中的每一个点,若落于中间区域,则淘汰掉该点;若落于其它区域,则通过该点与它所在区域的原单调段进行计算得到新单调段,从而得到给定平面点集的凸壳.算法效率高,在最坏情况下的时间复杂度为O(nlogm),m为凸壳的顶点数.