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

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

提出一种三维散乱点云的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.