基于遗传算法的散乱点云最小包围盒求解

孙殿柱; 史阳; 刘华东; 李延瑞

基于遗传算法的散乱点云最小包围盒求解

山东理工大学机械工程学院, 淄博 255091

基金项目: 国家自然科学基金资助项目(51075247);山东省自然科学基金资助项目(ZR2010EM008)

详细信息

中图分类号: TP391.72
计量
- 文章访问数: 2111
- HTML全文浏览量: 220
- PDF下载量: 699
- 被引次数: 0
出版历程
- 收稿日期: 2012-08-16
- 修回日期: 2013-04-10
- 网络出版日期: 2013-08-30

Solution of minimum bounding box of scattered points based on genetic algorithm

School of Mechanical Engineering, Shandong University of Technology, Zibo 255091, China

摘要

摘要: 提出一种将遗传算法和O'Rourke算法相融合的最小包围盒求解算法,以O'Rourke算法中的体积函数作为遗传算法的目标函数,采用遗传算子指导解的搜索方向,通过新种群的迭代生成过程缩小搜索区域与体积误差,种群迭代结束后对最优个体解码获得最小包围盒.实验结果表明,该算法可在满足最小包围盒体积精度的同时显著提高算法的运行效率,能够有效处理各种复杂散乱点云数据的最小包围盒快速求解问题.
- 散乱点云 /
- 最小包围盒 /
- 遗传算法 /
- 体积函数
Abstract: An algorithm of minimum bounding box combining genetic algorithm with O'Rourke's algorithm was proposed, which regarded the volume function in O'Rourke's algorithm as the objective function and used the evolutionary factors to guide the searching directions. Through the process of the population's iterative generation, this algorithm narrowed the search area and the volume error. When the iterative process was over, the minimum bounding box was obtained by decoding the optimal individuals. The experimental results show that the algorithm can improve algorithmic efficiency and satisfy the volume accuracy simultaneously. The algorithm can deal with sorts of problems related to minimum bounding box fast solving of complex scattered point cloud.
- scattered points /
- minimum bounding box /
- genetic algorithm /
- volume function

HTML全文

参考文献(1)

[1] 章勤,黄琨,李光明.一种基于OBB的碰撞检测算法的改进[J].华中科技大学学报:自然科学版,2003,31(1):46-48 Zhang Qin,Huang Kun,Li Guangming.Improvement of collision-detection algorithm based on OBB[J].Journal of Huazhong University of Science and Technology:Natural Science Edition,2003,31(1):46-48(in Chinese) [2] Joseph O'Rouke.Finding minimal enclosing boxes[J].International Journal of Computer and Information Sciences,1985,14(3):183-199 [3] Chan C K,Tan S T.Determination of the minimum bounding box of an arbitrary solid:an iterative approach[J].Computers and Structures,2001,79(15):1433-1449 [4] 陈柏松,叶雪梅,安利.基于非线性主成分分析的最小包围盒计算方法[J].计算机集成制造系统,2010,16(11):2375-2378 Chen Baisong,Ye Xuemei,An Li.Minimum bounding box calculation based on nonlinear principle component analysis[J].Computer Integrated Manufacturing Systems,2010,16(11):2375-2378(in Chinese) [5] Dimitrov D,Knauer C,Kriegel K,et al.Bounds on the quality of the PCA bounding boxes[C]//Computational Geometry:Theory and Applications[D].Amsterdam:Elsevier,2009,42(8):772-789 [6] Vranic D V,Saupe D.3D model retrieval .Saxomy,Germany:University of Leipzig,2004 [7] Barber C B,Dobkin D P,Huhdanpaa H.The quickhull algorithm for convex hulls[C]//ACM Transactions on Mathematical Software.New York:ACM,1996,22(4):469-483 [8] Hamalainen T,Klapuri H,Saarinen J,et al.Accelerating genetic algorithm computation in tree shaped parallel computer[J].Systems Architecture,1996,42(1):19-36 [9] Chang Chunlin.A genetic algorithm for solving the two-dimensional assortment problem[J].Computers and Industrial Engineering,2006,50(1):175-184 [10] Wolpert D H,William G M.No free lunch theorems for optimization[J].IEEE Transaction on Evolutionary Computation,1997,1(1):67-82 [11] 王丰丰.求解动态优化问题的遗传算法的研究与实现[D].上海:上海交通大学,2010 Wang Fengfeng.Research and realization of the genetic algorithm for dynamic optimization problems[D].Shanghai:Shanghai Jiao Tong University,2010(in Chinese)

施引文献

资源附件(0)

访问统计