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

来源：计算机技术与发展杂志2017年第02期北京时间：

作者：马骏;蔺东杰[;凌广明

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

关键词：凸包;海量;平面点集;预处理;排序;快速