简单多边形凸包的算法

摘要：

给出了一种求任意简单多边形凸包的算法.算法中采用了逐次删除凹顶点排除非凸包上的点直至没有凹顶点,从而求得凸包的思想.其几何意义明显,易于编程实现.该算法的时间复杂度为顶点个数的线性次乘法、线性次减法及顶点个数与其对数乘积次比较.给出了准确的时间复杂度的上界.

关键词：多边形、凸包、算法

所属期刊栏目：7

分类号：TP317(计算技术、计算机技术)

资助基金：国家自然科学基金69705004;黑龙江省自然科学基金F9706

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

页数：共3页

页码：98-100