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

编号 zgly0001607829

文献类型 期刊论文

文献题名 一种新的最小凸包算法及其应用

作者 程三友  李英杰 

作者单位 长安大学地球科学与资源学院  陕西省环境科学研究设计院 

母体文献 地理与地理信息科学 

年卷期 2009年05期

年份 2009 

分类号 TP301.6 

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

文摘内容 当前流行的最小凸包算法的时间复杂度相对较大,不适宜处理海量数据。该文提出一种新的平面离散点的最小凸包生成算法,其时间复杂度为O(nlogn)。该算法通过排序、分区、指针定位、一遍扫描离散点集,在运算过程中对凸包顶点进行动态增加或删除,可快速生成点集的最小凸包。最终,求离散分布的居民点点集的最小凸包实例表明,该算法应用效果较好。