一种新的最小凸包算法及其应用  

A New Algorithm of Minimum Convex Hull and Its Application

作　　者：程三友[1] 李英杰 

机构地区：[1]长安大学地球科学与资源学院,陕西西安710054 [2]陕西省环境科学研究设计院,陕西西安710061

出　　处：《地理与地理信息科学》2009年第5期43-45,共3页Geography and Geo-Information Science

基　　金：长安大学校发展科技基金(07Z1503051001);国家高技术研究发展计划项目(2009ZX07212-002)

摘　　要：当前流行的最小凸包算法的时间复杂度相对较大,不适宜处理海量数据。该文提出一种新的平面离散点的最小凸包生成算法,其时间复杂度为O(nlogn)。该算法通过排序、分区、指针定位、一遍扫描离散点集,在运算过程中对凸包顶点进行动态增加或删除,可快速生成点集的最小凸包。最终,求离散分布的居民点点集的最小凸包实例表明,该算法应用效果较好。The popular minimum convex hull algorithm is not fit for processing mass data due to its big time complexity. Accordingly,a new minimum convex hull algorithm is put forward in this paper, which time complexity is small comparatively. The algorithm, based on ordering plane discrete point set, making suhareas and orientation by indicating pointer,increases convex hull vertexes and deletes convex hull vertexes dynamically in the process of scanning a discrete point set for getting its minimum convex hull vertex set. Time complexity of the algorithm is O（nlogn） merely. The algorithm has been applied to a discrete residential point set successfully.

关 键 词：最小凸包 离散点集 时间复杂度 

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