寻求多边形链顶点凸壳的算法

提出一种计算简单多边形链顶点凸壳的算法,基本思想是分段计算,在每段的计算中,先分4种不同情况计算出边链L1,然后利用一种技巧将L1上的部分顶点排列成顶点角递增序列,构成边链L2,最后对L2进行倒查,删去非凸壳顶点,剩下的点即凸壳顶点.该算法不仅易于实现,而且其时间复杂性是线性的.