三维散乱点云的Voronoi拓扑近邻点集查询算法  

An Algorithm Inquiring Voronoi Topological Neighbors for 3D Scattered Point-cloud

作　　者：孙殿柱[1] 刘健[1] 李延瑞[1] 孙永伟[1] 

机构地区：[1]山东理工大学机械工程学院,淄博市张店区张周路12号255091

出　　处：《武汉大学学报（信息科学版）》2011年第1期86-91,共6页Geomatics and Information Science of Wuhan University

基　　金：国家863计划资助项目(2006AA04Z105)

摘　　要：提出一种三维散乱点云的Voronoi拓扑近邻点集查询算法,该算法改进R*-tree建立三维散乱点云的空间索引结构,采用动态扩展空心球算法获取样点的k近邻点集,通过偏心扩展和自适应扩展获取样点拓扑近邻参考数据,生成该局部点集的Voronoi图,查询样点Voronoi邻域获取样点拓扑近邻点集。通过算法时间复杂度分析及相关实验,证明该算法可快速、准确地获取任意复杂散乱点云的Voronoi拓扑近邻点集。An algorithm inquiring topological neighbors for 3d scattered point-cloud based on the Voronoi Diagram of local point-set is proposed,which has four steps： first,R＊-tree was applied and improved to organize the spatial indexing structure of scattered point-cloud;second,the neighboring points set of the sampling point was gain according to the algorithm searching for k-nearest neighbors;third,the topological neighbors reference data of the sampling point were obtained through eccentric and adaptive expansion;fourth,the Voronoi topological neighbors inquiring was realized according to Voronoi diagram of topological neighbors reference data.It was proved that this algorithm can obtain topological neighbors of arbitrary complicated scattered point-cloud accurately and efficiently through analyzing time complexity and doing related experiments.

关 键 词：三维散乱点云 空间索引结构 偏心扩展 自适应扩展 Voronoi拓扑近邻 

分 类 号：P208[天文地球—地图制图学与地理信息工程]