基于有界k-d树的最近点搜索算法

被引：32

作者：

刘宇 ^{[1
]}

熊有伦 ^{[2
]}

机构：

[1] 华中科技大学机械科学与工程学院

[2] 数字制造装备与技术国家重点实验室

来源：

华中科技大学学报(自然科学版) | 2008年 / 07期

关键词：

逆向工程; 最近点搜索; 有界k-d树; 包围盒;

D O I：

10.13245/j.hust.2008.07.026

中图分类号：

TP391.41 [];

学科分类号：

080203 ;

摘要：

提出了一种基于有界k-d树的最近点搜索算法.算法的原理是:由根节点中的包围盒确定树中数据的空间范围,并在搜索过程中不断划分包围盒来缩小搜索范围,同时递归地计算查询点到包围盒的距离.结合优先级队列,基于有界k-d树的最近点搜索算法拓展到搜索按距离远近排列的多个最近点.实测和仿真分析表明,本搜索算法的计算效率高于传统的搜索算法.

引用

页码：73 / 76

页数：4