求平面点集凸壳的一个最优算法

• 作者: 岳昊 徐晓丹 郑永果
• 来源期刊: 福建电脑
• 学科: 工学
• 关键词: 凸壳 格雷厄姆方法 算法 时间复杂性 计算几何
• 年，卷（期）: 2005,（7）
• 所属期刊栏目: 研究与探讨
• 页码范围: 47-48
• 页数: 2页
• 分类号: TP3
• 字数: 2161字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-2782.2005.07.026

摘要

本文提出了一个求平面点集凸壳的格雷厄姆方法的一个改进算法.算法首先按照格雷厄姆方法将点集中的点进行分类;将分类后的点连成一个特殊的简单多边形;然后删去简单多边形的单个凹点、连续凹点;产生新的简单多边形;再删去新简单多边形的单个凹点及连续凹点;循环往复;最后得到的凸多边形即为点集凸壳的边界.本算法理论严密;易于理解;易于实现;时间复杂性也是.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	郑永果	山东科技大学信息科学与工程学院	77	543	11.0	19.0
2	岳昊	山东科技大学信息科学与工程学院	9	57	5.0	7.0
3	徐晓丹	山东科技大学信息科学与工程学院	2	18	2.0	2.0