三维散乱点云拓扑近邻数据查询方法

摘要

本发明提供一种三维散乱点云拓扑近邻数据查询方法，其特征在于：采集三维散乱点云数据并基于R^*－tree组织三维散乱点云的动态空间索引结构，采用动态空心球扩展算法查询样点的k近邻点集，通过偏心扩展和自适应扩展获取样点拓扑近邻参考数据，生成样点拓扑近邻参考数据的Voronoi图，查询样点Voronoi邻域所对应的数据点，即为样点的拓扑近邻数据。采用本方法可快速准确获取任意复杂海量散乱点云的拓扑近邻数据。

主权项

1、一种三维散乱点云拓扑近邻数据查询方法，其特征在于步骤依次为：(1)采集三维散乱点云数据并基于R^*-tree组织三维散乱点云的动态空间索引结构；(2)采用动态空心球扩展算法查询样点的k近邻点集，具体是：基于三维散乱点云动态空间索引结构采用深度优先遍历算法查找包含样点的叶结点，计算其MBR的外接球半径r，以当前样点为球心，$r_1=r·\sqrt{\frac{k}{M}}$为半径，确定空间球区域，获取该空间球区域内的数据点，若其点数大于k，则从中查找与样点之间距离最近的k个点，否则以当前球半径为内径，以$r_2=r_1·\sqrt{\frac{k-n}{n}+1}$为外径，动态扩展空心球区域，其中n为已取得的近邻点数，直到球内包含的点数大于等于k个，从中查找与样点之间距离最近的k个点，获取样点的k近邻点集；(3)生成样点及其k个近邻点所组成点集的Voronoi图；(4)如果样点为非边界点且其Voronoi区域不封闭，则进行偏心扩展，否则直接执行步骤(5)；(5)进行自适应扩展，获取样点的拓扑近邻参考数据；(6)生成样点拓扑近邻参考数据的Voronoi图，查询与样点Voronoi区域相邻的区域所对应的数据点，即为样点的拓扑近邻数据。