一种构建平面离散点集凸包的算法研究

• 作者: 俞梅
• 来源期刊: 上海应用技术学院学报(自然科学版)
• 学科: 工学
• 关键词: 多边形 凸包 矢量算法
• 年，卷（期）: 2003,（2）
• 所属期刊栏目: 理论研究
• 页码范围: 118-120
• 页数: 3页
• 分类号: TH126
• 字数: 2251字
• 语种: 中文
• DOI: 10.3969/j.issn.1671-7333.2003.02.011

摘要

本文提出一种矢量运算方法确定平面离散点集凸包,其原理是在构建凸包前,通过矢量计算判别出位于凸包多边形内部的点,预先将其删去,保留凸包多边形外部边缘的点,从而减少了构建凸包的离散点数目,提高运算速度.新算法达到O(nlogn)时间复杂度下限,简单且易于实现.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	俞梅	上海应用技术学院机械与自动化工程学院	1	18	1.0	1.0