寻求简单多边形凸壳的线性时间算法

被引：9

作者：

周培德

付梦印

机构：

[1] 北京理工大学计算机系

来源：

计算机工程与科学 | 2002年 / 03期

关键词：

多边形; 凸壳; 算法; 复杂性;

D O I：

暂无

中图分类号：

O18 [几何、拓扑];

学科分类号：

摘要：

本文提出在线性时间内构造简单多边形顶点凸壳的两种算法。第一个算法的基本思想是利用一种技巧对多边形顶点进行筛选 ,使剩余顶点的角的大小排成递增序 ,然后用Graham扫描方法删去非凸壳顶点 ,最后得到多边形凸壳的顶点序列。第二个算法不断删去多边形的凹点及新产生的凹点 ,最后得到凸壳顶点序列。这两种算法简单 ,易于实现 ,时间复杂性都是O(n)

引用

页码：1 / 2+44 +44

页数：3