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

• 作者: 付梦印 周培德
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 多边形 凸壳 算法 复杂性
• 年，卷（期）: 2002,（3）
• 所属期刊栏目: 算法研究
• 页码范围: 1-2,44
• 页数: 3页
• 分类号: TP301.6
• 字数: 2921字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2002.03.001

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	付梦印	北京理工大学计算机系	117	1932	24.0	38.0
2	周培德	北京理工大学计算机系	28	414	12.0	20.0