基于海量数据的二维凸包快速生成算法

• 作者: 凌广明 蔺东杰 马骏
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 凸包 海量 平面点集 预处理 排序 快速
• 年，卷（期）: 2017,（2）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 42-45
• 页数: 4页
• 分类号: TP301.6
• 字数: 3078字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2017.02.010

摘要

凸包算法是计算机几何的基本问题之一,在很多领域应用广泛.传统的凸包生成算法在处理大容量数据时,表现出的时间复杂度相对较高而且凸包生成速率较低,已经不能满足实际海量数据的需求.为解决这一问题,提出了一种面对海量数据的快速凸包生成算法.该算法通过对散乱点集分区、一遍扫描排序,确定散乱点集边界,快速处理边界点集中处于共线的点等一系列预处理操作,快速排除凸包内部的点,缩小了问题规模,避免了对不在凸包上的点集的扫描处理,明显地缩短了凸包的求取时间,可保证最小凸包的快速生成.该算法极其简单,时间复杂度较低,理论上可达到o(nlogn),有利于凸包生成速度的提高.与传统算法进行了同步对比实验,结果表明,该算法运行有效性较好,且具有较好的应用前景.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	马骏	河南大学计算机与信息工程学院	49	226	6.0	14.0
2	凌广明	河南大学软件学院	7	16	3.0	4.0
3	蔺东杰	河南大学计算机与信息工程学院	1	1	1.0	1.0