基于栅格划分构建平面点集凸壳的算法研究

• 作者: 刘玉树 张大远
• 来源期刊: 微机发展
• 学科: 工学
• 关键词: 凸壳 栅格 计算几何
• 年，卷（期）: 2004,（7）
• 所属期刊栏目: 理论、算法及智能研究
• 页码范围: 106-108
• 页数: 3页
• 分类号: TP301.6
• 字数: 3866字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2004.07.037

摘要

提出了一个构建平面点集凸壳的新算法.该算法用栅格阵列将待处理点集划分成若干个子集,这样凸壳可以由部分位于点集边缘的子集确定;然后按逆时针顺序逐步处理这些子集,得到一个包含待处理点集的简单多边形,删除凹顶点后就得到待处理点集的凸壳.由于只对点集边缘的点进行局部处理,从而提高了构建凸壳的效率.在最坏情况下该算法的时间复杂度为O(NlogN).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘玉树	北京理工大学计算机科学工程系	150	2634	25.0	46.0
2	张大远	北京理工大学计算机科学工程系	1	7	1.0	1.0