全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

一种高效的平面点集凸包递归算法

DOI: 10.3724/SP.J.1004.2012.01375, PP. 1375-1379

Keywords: 凸包,平面点集,主成分分析,光栅投影

Full-Text   Cite this paper   Add to My Lib

Abstract:

?凸包是计算几何的基本结构,在许多图形图像相关领域得到了广泛应用.本文提出了一种简单快速的平面点集凸包算法,使用了主成分分析法(Principlecomponentanalysis,PCA)对点集进行预处理,并研究了适用的排序规则和凸包边缘点判定原则.该算法已成功应用于一光栅投影三维形貌快速测量系统,对相位干涉图中密集残留点所形成的最小凸包进行提取.系统将提取的凸包区域进行掩码标记,从而避免密集残留点造成相位展开错误,保证了三维形貌重构的准确性.实验结果表明,该算法准确可靠,并且运行效率较高.

References

[1]  Jiang Jian. Search for convex of planar points. Journal of Chongqing Institute of Technology (Natural Science), 2007, 21(9): 15-17(江健. 寻找平面上点的凸壳. 重庆工学院学报(自然科学版), 2007, 21(9): 15-17)
[2]  Cheng San-You, Li Ying-Jie. A new algorithm of minimum convex hull and its application. Geography and Geo-information Science, 2009, 25(5): 43-45(程三友, 李英杰. 一种新的最小凸包算法及其应用. 地理与地理信息科学, 2009, 25(5): 43-45)
[3]  Chen Xue-Gong, Huang Shi-Feng, Li Yuan, Cao Jian. A fast algorithm for convex hull of the planar points. Computer and Information Technology, 2008, 16(3): 34-35(陈学工, 黄石峰, 李源, 曹建.一种平面点集凸壳的快速算法. 电脑与信息技术, 2008, 16(3): 34-35)
[4]  Jin Wen-Hua, He Tao, Tang Wei-Qing, Tang Rong-Xi. Simple fast convex hull algorithm of planar point set. Journal of Beijing University of Aeronautics and Astronautics, 1999, 25(1): 72-75(金文华, 何涛, 唐卫清, 唐荣锡. 简单快速的平面散乱点集凸包算法. 北京航空航天大学学报, 1999, 25(1): 72-75)
[5]  Shlens J. A tutorial on principal components analysis [Online], available: http://www.snl.salk.edu/~ shlens/pca.pdf, December 2, 2011
[6]  Bronnimann H, Iacono J, Katajainen J, Morin P, Morrison J, Toussaint G T. In-place planar convex hull algorithms. In: Proceedings of the 5th Latin American Symposium on Theoretical Informatics. Cancun, Mexico: Springer, 2002. 494-507
[7]  Wang Tao, Sun Chang-Ku, Shi Yong-Qiang, Wang Peng. Novel grating projection system based on assistant line and its calibration method. Acta Optica Sinica, 2011, 31(1): 0115002(王涛, 孙长库, 石永强, 王鹏. 基于辅助参考线的光栅投影轮廓测量系统及标定方法. 光学学报, 2011, 31(1): 0115002)
[8]  Gope C, Kehtarnavaz N. Affine invariant comparison of point-sets using convex hulls and Hausdorff distances. Pattern Recognition, 2007, 40(1): 309-320
[9]  Li Jiang, Sun Li-Jun. Pedestrian video detection algorithm based on convex hull clipping. Computer Engineering, 2010, 36(2): 173-175(李江, 孙立军. 基于凸包裁剪的行人视频检测算法. 计算机工程, 2010, 36(2): 173-175)
[10]  Zhou Pei-De, Fu Meng-Yin. Linear algorithms for finding the convex hull of a simple polygon. Computer Engineering and Science, 2002, 24(3): 1-2, 44(周培德, 付梦印. 寻求简单多边形凸壳的线性时间算法. 计算机工程与科学, 2002, 24(3): 1-2, 44)
[11]  Liu Xin, Liu Ren-Ren. An improved divide and conquer algorithm for computing the convex hull. Computer Engineering and Science, 2006, 28(8): 63-65(刘新, 刘任任. 一种改进的构建凸包的分治算法. 计算机工程与科学, 2006, 28(8): 63-65)
[12]  Akl S G, Toussaint T. A fast convex hull algorithm. Information Processing Letters, 1978, 7(5): 219-222
[13]  Bohm C, Kriegel H P. Determining the convex hull in large multidimensional databases. In: Proceedings of the 3rd International Conference on Data Warehousing and Knowledge Discovery. Munich, Germany: Springer, 2001. 294-306
[14]  Bronnimann H, Iacono J, Katajainen J, Morin P, Morrison J, Toussaint G. Space-efficient planar convex hull algorithms. Theoretical Computer Science, 2004, 321(1): 25-40

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133