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

摘要

利用三维数据点对原始模型进行曲面重建时,快速查找边界点并拟合出边界边是曲面重建的重要环节.提出一种基于K近邻的三维空间数据点边界快速搜索算法,该方法首先找出所有空间数据点的K近邻,并对被测点区域进行八分,判断其任意相邻的2个区域是否有数据点,提高了边界点的查找精度;介绍了基于实验的数据点空洞半径的计算方法,详细说明了算法的设计步骤,给出了算法的运行结果,并对结果进行了比较分析;采用基于K近邻的新八分法查找边界点,对算法进行了改进,使其精确性优于原始四分法,使运算时间优于原始八分法.实验证明该算法边界提取精度较高、运行速度较快,尤其是在凹陷程度较大区域,能更精确地描绘出原始模型的轮廓,为边界曲线拟合提供了优质的边界点数据.