2维空间数据最小凸包生成算法优化

Study of Optimizing Method for Algorithm of Minimum Convex Closure Building for 2D Spatial Data

最小凸包是计算几何中得到广泛研究的问题之一 ,在地理信息系统中也有着广泛应用。探讨了 1种较为常用的最小凸包生成算法 ,提出点集分组计算和动态删除判定点的方法以提高算法的执行效率 ,并结合实例分析了算法的运行效率与凸包形态、分组子集的大小之间的关系。

The minimum convex closure is one of the widely studied problems in science of computing geometry, as well as extensively applied in many fields of GIS. One of the commonly used algorithm for building minimum convex closure has been discussed in this paper. In order to increase operation speed, the author put forward an improved method based on grouping data computing and removing useless points, and analyzed the relationships between algorithm efficiency with the convex closure characteristic and subset points number by some testing.