GIS中空间数据最小凸包串行算法的改进  

An improved approach of spatial data serial algorithm of minimum convex hull in GIS

作　　者：刘波[1] 万冉冉 阮见[3] 李大军[1] 刘明磊[1] 

机构地区：[1]东华理工大学测绘工程学院,南昌330013 [2]江西省基础地理信息中心,南昌330046 [3]东华理工大学软件学院,南昌330013

出　　处：《测绘科学》2015年第6期81-83,138,共4页Science of Surveying and Mapping

基　　金：国家自然科学基金项目(41201395);江西省数字国土重点实验室开放基金项目(DLLJ201308);江西省教育厅科技项目(GJJ14479)

摘　　要：针对传统最小凸包算法无法快速处理数据量较大的空间数据这一不足,该文通过分析最小凸包的性质,对传统的最小凸包串行算法进行改进,以提高最小凸包的构建效率。首先将空间点群分为绝对凸包顶点、可能凸包顶点、绝非凸包顶点三类,然后将大量的绝非凸包顶点剔除,仅仅判断可能凸包顶点中哪些点是构成最小凸包的顶点,最终和绝对凸包顶点构成所需要的最小凸包。通过对比分析,该文改进的方法原理正确,在遍历点的数量上较传统串行算法具有明显的优势,算法执行效率较高。In view of the shortcomings that traditional minimum convex hull algorithms could not quickly deal with large amount of spatial data, this paper improved the serial algorithm of minimum con- vex hull through analyzing the property of minimum convex hull to make the efficiency of getting the minimum convex hull better. Firstly, the large spatial data were divided into three parts, including absolute convex hull vertex, absolutely wrong convex hull vertex and possible convex hull vertex. Then, the absolutely wrong convex hull vertex were deleted, and the minimum convex hull that consists of points from possible convex hull vertex and absolute convex hull vertex was built. Through comparative analysis, this improved approach has obvious advantages on seeking spatial data, and efficiency of this algorithm execution is higher than the traditional serial algorithm.

关 键 词：最小凸包 串行算法 空间数据 地理信息系统 

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