一种给定平面点集凸壳算法

• 作者: 张显全 蒋联源 郭明明 陈发住
• 来源期刊: 信息技术
• 学科: 工学
• 关键词: 凸壳 单调段 极值点 正切线算法
• 年，卷（期）: 2007,（9）
• 所属期刊栏目: 基金项目
• 页码范围: 5-7
• 页数: 3页
• 分类号: TP301.6
• 字数: 2982字
• 语种: 中文
• DOI: 10.3969/j.issn.1009-2552.2007.09.002

摘要

凸壳问题是计算机图形学、图像处理、模式识别等众多领域中的一个基本问题.将正切线算法应用到给定平面点集凸壳的计算中,并实现了正切线算法中新加入点的自动编号.通过极值点把点集分成若干个区域,对于点集中的每一个点,若落于中间区域,则淘汰掉该点;若落于其它区域,则通过该点与它所在区域的原单调段进行计算得到新单调段,从而得到给定平面点集的凸壳.算法效率高,在最坏情况下的时间复杂度为O(nlogm),m为凸壳的顶点数.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张显全	广西师范大学计算机科学系	49	500	13.0	20.0
2	蒋联源	广西工学院计算机工程系	8	135	5.0	8.0
3	陈发住	广西高速公路管理局西南处	1	9	1.0	1.0
4	郭明明	广西师范大学计算机科学系	3	41	3.0	3.0