坐标排序的离散点凸包生成算法

发布时间：2018-05-28 17:28

  本文选题：凸包 + 排序　； 参考：《测绘科学》2017年02期

【摘要】：针对传统的凸包生成方法在数据量较大情况下效率下降明显的问题,该文提出了一种基于平面离散点快速生成凸包算法。基于凸包边界单调性对平面点集分区域按X轴方向排序的方法,较好地减少了传统凸包生成算法的计算量,实现了凸包求取的高效性。实验结果表明:该算法不仅可以快速有效地生成凸包,还能够保证结果的准确性,且效率较高。
[Abstract]:In order to solve the problem that the efficiency of the traditional convex hull generation method decreases obviously when the amount of data is large, a fast convex hull generation algorithm based on plane discrete points is proposed in this paper. Based on the monotonicity of convex hull boundary, the method of sorting the region of the plane point set according to the X axis direction can reduce the computational cost of the traditional convex hull generation algorithm and realize the high efficiency of the convex hull extraction. Experimental results show that the proposed algorithm not only can generate convex hull quickly and effectively, but also can ensure the accuracy of the result, and its efficiency is high.
【作者单位】： 兰州交通大学测绘与地理信息学院/甘肃省地理国情监测工程实验室;
【基金】：国家科技支撑计划项目(2013BAB05B01) 国家自然科学基金项目(41371435,41561090)
【分类号】：P208

【相似文献】

相关期刊论文 前10条

1 邬长安;王志平;;基于夹角的二维凸包改进算法[J];信阳师范学院学报(自然科学版);2007年04期

2 牟廉明;;k子凸包分类方法[J];山西大学学报(自然科学版);2011年03期

3 邹中柱;;凸函数类凸包中函数星形性的半径[J];湖南师范大学自然科学学报;1989年02期

4 宋丽;姜旭东;;卷包裹法求凸包问题算法分析与程序实现[J];牡丹江师范学院学报(自然科学版);2005年04期

5 易巧玲;刘良方;;凸包算法的线性实现[J];中国科技信息;2011年08期

6 刘人午;杨德宏;李燕;谌柯;;一种改进的最小凸包生成算法[J];大地测量与地球动力学;2011年03期

7 程三友;李英杰;;一种新的最小凸包算法及其应用[J];地理与地理信息科学;2009年05期

8 吕伟,梁友栋;一般欧氏空间点集凸包的快速实时算法[J];应用数学学报;1992年02期

9 姜勇彪;吴志春;郭福生;朱志军;;江西石城县通天寨龟裂凸包景观成因初探[J];东华理工大学学报(社会科学版);2013年03期

10 钱钊;刘润涛;;改进的点集凸包的增量算法[J];哈尔滨师范大学自然科学学报;2007年04期

相关会议论文 前2条

1 沈雪松;;窄边距深凸包门类零件的加工工艺[A];第九届机械加工技术学术年会论文集[C];2004年

2 吴芳;;锥台形凸包的冲制加工[A];第九届机械加工技术学术年会论文集[C];2004年

相关博士学位论文 前2条

1 吴雪刚;凸包算法和最近子空间分析及其在人脸识别中的应用[D];重庆大学;2014年

2 Daoussa Daniel;完全交曲面陈示性数的凸包[D];华东师范大学;2015年

相关硕士学位论文 前10条

1 王逊扬;基于最小凸包理论的相机自动标定方法研究[D];沈阳大学;2016年

2 张庆军;雷达连接器结构仿真及优化[D];电子科技大学;2015年

3 马远征;基于凸包算法的人脸识别方案[D];云南大学;2016年

4 孟迪;点集图形重建的算法研究[D];哈尔滨工业大学;2016年

5 赵敬红;优化技术在人脸识别中的应用[D];沈阳航空航天大学;2016年

6 毛鹏;快速凸包计算实现及其应用[D];西安电子科技大学;2013年

7 郝晓军;凸包算法的加速与改进研究[D];河北工业大学;2003年

8 郑福玉;凸包型仿生表面设计及水砂磨损行为[D];吉林大学;2006年

9 李志;快速三维凸包算法的研究与改进[D];上海师范大学;2011年

10 陈庆强;凸包算法在街面堵控系统中的研究与应用[D];东华大学;2014年

，

本文编号：1947568