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