平面点集凸壳的快速算法

• 作者: 曲仕茹 赵军
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 平面点集 凸壳 简单多边形 凹顶点
• 年，卷（期）: 2009,（1）
• 所属期刊栏目: 理论研究
• 页码范围: 56-58
• 页数: 3页
• 分类号: TP301.6
• 字数: 3012字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2009.01.016

摘要

提出一种计算平面点集凸壳的快速算法.利用极值点划分出四个矩形,它们包含了所有凸壳顶点,通过对矩形中的点进行扫描,排除明显不是凸壳顶点的点,剩余的点构成一个简单多边形.再利用极点顺序法判断多边形顶点的凹凸性并删除所出现的凹顶点,最终得到一个凸多边形即为点集的凸壳.整个算法简洁明了,避免了乘法运算(除最坏情况外),从而节省计算时间.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	曲仕茹	西北工业大学自动化学院	115	966	17.0	23.0
2	赵军	兰州交通大学数理与软件工程学院	28	187	8.0	12.0