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

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

针对传统最小凸包算法无法快速处理数据量较大的空间数据这一不足,该文通过分析最小凸包的性质,对传统的最小凸包串行算法进行改进,以提高最小凸包的构建效率。首先将空间点群分为绝对凸包顶点、可能凸包顶点、绝非凸包顶点三类,然后将大量的绝非凸包顶点剔除,仅仅判断可能凸包顶点中哪些点是构成最小凸包的顶点,最终和绝对凸包顶点构成所需要的最小凸包。通过对比分析,该文改进的方法原理正确,在遍历点的数量上较传统串行算法具有明显的优势,算法执行效率较高。

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.