三维空间数据点边界快速查找算法设计与实现  

Design and realization of algorithms of quick searching boundary based on 3D cloud data

作　　者：杜娜[1] 袁晶[1] 董文忠 吴丽娟[1] 

机构地区：[1]沈阳师范大学物理科学与技术学院,沈阳110034 [2]兴城电视台,辽宁兴城125100

出　　处：《沈阳师范大学学报（自然科学版）》2015年第2期257-260,共4页Journal of Shenyang Normal University:Natural Science Edition

基　　金：辽宁省科技厅自然科学基金资助项目(201102205)

摘　　要：利用三维数据点对原始模型进行曲面重建时,快速查找边界点并拟合出边界边是曲面重建的重要环节。提出一种基于K近邻的三维空间数据点边界快速搜索算法,该方法首先找出所有空间数据点的K近邻,并对被测点区域进行八分,判断其任意相邻的2个区域是否有数据点,提高了边界点的查找精度;介绍了基于实验的数据点空洞半径的计算方法,详细说明了算法的设计步骤,给出了算法的运行结果,并对结果进行了比较分析;采用基于K近邻的新八分法查找边界点,对算法进行了改进,使其精确性优于原始四分法,使运算时间优于原始八分法。实验证明该算法边界提取精度较高、运行速度较快,尤其是在凹陷程度较大区域,能更精确地描绘出原始模型的轮廓,为边界曲线拟合提供了优质的边界点数据。It is an important part to find boundary points and to fit the boundary edge quickly in surface reconstruction, when surface are reconstructed by using the cloud data for the original model. An algorithm of fast search boundary was proposed in the paper. Firstly, to find K neighbors of all spatial data points, and divided area measured into eight parts, and to judge whether there are data points in two adjacent parts, to improve search accuracy. The calculation method of a cavity radius was introduced based on the experimental data, and design steps are described, the running results of the algorithm are also given, the results were compared and analyzed ones. The search algorithm for boundary points were improved by eight parts method combined with K nearest neighbor, making its accuracy better and computing time shorter than the original four parts. The experimental results demonstrate that the algorithm of boundary extraction has high precision, fast running speed, especially in the concave area, the original model profile can be described more accurately, and provided high quality data for the boundary fitting.

关 键 词：三维空间数据点 边界点 K近邻 八分法 边界拟合 

分 类 号：TP39[自动化与计算机技术—计算机应用技术]