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

摘要：

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

关键词：简单多边形链、凸壳、算法、时间复杂性

所属期刊栏目：23

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：75-77