绪论:常见的查找最近邻点的方法有BST、KD-Tree、Octree.其中BST用于一维查找,KD-Tree用于K维(k=1就是1维,k=3就是三维),Octree用于三维。题主主要是为了做点云学习的一些基础知识,所以Octree详细讲解一下。
系列文章目录
后期会有呦
文章目录
一、为什么NN问题很重要(不直接使用FLANN,pcl等)
1.现成的库不够高效
2.建立在GPU上的NN library很有价值
二、BST、Kd-tree、Octree详解与代码解析
1.BST(二叉树)
-
BST是基于点的树结构。数据结构包含左节点、右节点、节点的值等。
-
搜索过程:①确定一个父节点Root(这关系着你的复杂度)
②规定一个逻辑关系:value>root.value放在左边,小于放在右边(左右自己决定,但是逻辑要保持一致)
③二叉树建立成功 -
分类(依据对于Root遍历的先后顺序):先序、中序、后序
-Que如何利用BST搜索点? 给了一个二叉树和一个key,如何判断哪个point=key,如果没有,return NULL
Ans:利用循环(GPU)或者递归(CPU)
懒得上代码了嘿嘿嘿,网上资源很多
2.Kd-tree(如何切空间,如何查询点)
- 分类:①点在超平面上②点在超平面内
- 核心:给定一个查询点,决定需不需要搜索某个区域
-
如何切空间:沿着x,y交替切。
最后的结果,之前就是两个轴轮换着切,至于结果为什么是下面这样子的,是因为我们把分割点数设为1.
-
如何查
①确定一个点,若该点O位于切分得的某个区域内,区域内的点A作为查询点,两点之间的距离OA作为初始的worst distance=OA。
②以查找点为圆心,两点之间欧式距离为半径,进行nearest-search,若新的点B到O的距离OB<OA,则更新worst distance=OB,缩小查找范围,
③以此类推查询完整个与圆相交的面内的点作为search result。
如下图所示为关键的几步示意图,还是按照KD-Tree的交替查找方式:
结论:KD-Tree结构很复杂,很难分析,主要因为其K和r很难决定,你说我取几个点合适,我半径worst distance多少,嘿,我不清楚。
依旧不放代码啊哈哈哈哈哈,
3.八叉树Octree(如何切空间,如何查询点,如何提前终止查询)
-
如何切空间:
-
先确定外围再平均切。外围由边缘的点组成。本例子设置leaf_size=1(切成一个点在一个区域内)
- -
如何用代码定义八叉树?
class Octant:
def_init_(self,children,center,extent,point_indices,is_leaf):
self.children=children
self.center=center
self.extent=extent
self.point_indices=point_indices
self.is_leaf=is_leaf
其实一开始是没有worst distance的,需要找到兴趣点所在区域的点与其之间的距离设置为worst distance。
- 终止条件:用Function函数决定终止与否**
Case1 :正方体与球体太远,无接触
Case2:不太远,是否与面有接触
Case3:正方体边和角点与球体是否有交集
最后,contain()函数可查看球体是否包含正方体
总结
简单的介绍了最近邻搜索不同维度的不同方法,详细介绍八叉树应用与三维点上的数据结构,空间切分,查找以及提前终止条件。作为个人的学习笔记,与大家共同探讨。