junxnone / aiwiki

AI Wiki

https://junxnone.github.io/aiwiki

17 stars 2 forks source link

ML NNS KDTree #104

Open junxnone opened 3 years ago

junxnone commented 3 years ago

KDTree

Reference

Brief

KD - k-dimensional
- BSTree - Binary Sort Tree/Binary Search Tree
- 1970s 由 Jon Bentley 提出
分割 K 维数据空间的数据结构
用途: 搜索感兴趣数据
- 搜索最近邻点
- 搜索半径 R 内的点
- 搜索最近的 N 个点
构建 Pipeline
- 选取方差较大的轴作为分割轴顺序 - (x->y->z)
- 取分割轴的中位数为根节点
搜索 Pipeline

nn_kdtree

复杂度

Steps	复杂度
构建	O(log² n)
插入	O(log n)
删除	O(log n)
查询	O(n^1-1/k + k) k - 搜索的点数

Libraries

UseCase

三维点云中点的检索

K = 2
K=3