一种改进的最小凸包生成算法

摘要

为解决最小凸包算法在计算超过106数量级的点数时计算时间比较长的问题,提出一种将数据点集进行一次扫描,得到横向和纵向排序点表,并建立初始凸包,再运用增点法逐步从外向内判别数据点是否加入凸包表的改进算法.该方法稳定性高、计算速度快.%At present, there are various algorithms for producing the Minimum Convex Hull, but these algorithms consume relatively long computing time when the sum of spatial data points are more than 106. An improved algorithm which are of stability and efficiency is designed. Through scanning the data points one time, we can get two tables: Lateral Sorting Table and Longitudinal Sorting Table, and a Initial Minimum Convex Hull. After the scanning, we judge whether the current point can be classified in the Minimum Convex Hull based on Increase point Method.