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

被引：20

作者：

程三友 ^{[1
]}

李英杰 ^{[2
]}

机构：

[1] 长安大学地球科学与资源学院

[2] 陕西省环境科学研究设计院

来源：

地理与地理信息科学 | 2009年 / 25卷 / 05期

关键词：

最小凸包; 离散点集; 时间复杂度;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

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

引用

收藏

页码：43 / 45

页数：3

相关论文

共 9 条

[1] 中国特大城市空间形态变化的时空特征 [J].

王新生 ;

刘纪远 ;

庄大方 ;

王黎明 .

地理学报, 2005, (03) :392-400

[2] 基于凸壳构造技术的领海基点选取问题研究 [J].

彭认灿 ;

王家耀 ;

田震 ;

郭立新 ;

陈子澎 .

测绘学报, 2005, (01) :53-57

[3] 一种实型数据的快速排序算法 [J].

江华 .

计算机工程, 2004, (13) :50-51

[4] 2维空间数据最小凸包生成算法优化 [J].

王杰臣 .

测绘学报, 2002, (01) :82-86

[5] 一种平面点集凸包与三角网格综合生成的算法 [J].

孔德慧 ;

马春玲 .

计算机研究与发展, 2000, (07) :891-896

[6] 确定多边形凸凹顶点的快速算法及其应用 [J].

马小虎 ;

潘志庚 ;

石教英 .

计算机工程与设计, 1998, (03) :3-5

[7] 一个改进的简单多边形凸包算法 [J].

吴中海 ;

叶澄清 ;

潘云鹤 .

计算机辅助设计与图形学学报, 1997, (01) :10-14

[8]

计算机图形学[M]. 高等教育出版社 , 潘云鹤主编, 2001

[9]

空间分析[M]. 高等教育出版社 , 郭仁忠著, 2001