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

AN IMPROVED ALGORITHM FOR PRODUCING MINIMUM CONVEX HULL

作　　者：刘人午[1] 杨德宏[1] 李燕[1] 谌柯[2] 

机构地区：[1]昆明理工大学国土资源工程学院,昆明650093 [2]西华师范大学国土资源学院,南充637008

出　　处：《大地测量与地球动力学》2011年第3期130-133,共4页Journal of Geodesy and Geodynamics

基　　金：云南省自然科学基金(2000D0005Q)(2004D0007Q);四川省科技厅软科学规划项目(2008ZR0049);南充市科学技术局2008年度应用技术研究与开发项目(N2008-SF004)

摘　　要：为解决最小凸包算法在计算超过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.

关 键 词：最小凸包 算法 地理信息系统 计算机图形学 测绘 

分 类 号：P283.4[天文地球—地图制图学与地理信息工程]