求平面点集凸壳的一种新算法

• 作者: 刘润涛 安晓华 王三
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 点集 单调链 凸壳
• 年，卷（期）: 2009,（3）
• 所属期刊栏目: 研究、探讨
• 页码范围: 58-59,69
• 页数: 3页
• 分类号: TP391
• 字数: 3024字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2009.03.016

摘要

在研究了大量的求平面点集凸包的算法基础上,提出了一种新的构造平面点集的凸壳算法.此算法先求出四个极值点,构造出一个四边形.对于四边形外面的点依次用二分法进行判断是属于哪个线段区域;对于一个线段区域上的点只需要找出右侧的点,分别和线段的两个端点连接得到新的多边形链,依次这样处理每个点,直到结束.这样就得到四个简单多边形单调链.然后对单调链求凸点,时间复杂度为O(n),最后求得的每个凸点就是平面点集的凸壳,此算法总的时间复杂度不超过0(nlogn).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘润涛	哈尔滨理工大学信息与计算科学研究所	47	396	11.0	18.0
2	安晓华	哈尔滨理工大学应用科学学院	4	40	3.0	4.0
3	王三	哈尔滨理工大学应用科学学院	4	20	3.0	4.0