当前位置: 首页>开发笔记>正文

kd树的构建与搜索

kd树的构建与搜索

二、构建完kd树之后,如今进行最近邻搜索呢?

KD树的查找算法:

在k-d树中进行数据的查找也是特征匹配的重要环节,其目的是检索在k-d树中与查询点距离最近的数据点。

这里先以一个简单的实例来描述最邻近查找的基本思路。

例一:查询的点(2.1,3.1)(较简单)。

1、如图3所示,星号表示要查询的点(2.1,3.1)。通过二叉搜索,顺着搜索路径很快就能找到最邻近的近似点,也就是叶子节点(2,3)。

2、而找到的叶子节点并不一定就是最邻近的,最邻近肯定距离查询点更近,应该位于以查询点为圆心且通过叶子节点的圆域内。

3、为了找到真正的最近邻,还需要进行'回溯'操作:

             算法沿搜索路径反向查找是否有距离查询点更近的数据点。

此例中先从(7,2)点开始进行二叉查找,然后到达(5,4),最后到达(2,3),此时搜索路径中的节点为<(7,2),(5,4),(2,3)>,

首先以(2,3)作为当前最近邻点,计算其到查询点(2.1,3.1)的距离为0.1414,

然后回溯到其父节点(5,4),并判断在该父节点的其他子节点空间中是否有距离查询点更近的数据点。以(2.1,3.1)为圆心,以0.1414为半径画圆,如图3所示。发现该圆并不和超平面y = 4交割,因此不用进入(5,4)节点右子空间中去搜索。

4、最后,再回溯到(7,2),以(2.1,3.1)为圆心,以0.1414为半径的圆更不会与x = 7超平面交割,因此不用进入(7,2)右子空间进行查找。至此,搜索路径中的节点已经全部回溯完,结束整个搜索,返回最近邻点(2,3),最近距离为0.1414。

                                      图3

例二:查找点为(2,4.5)(叫复杂一点)。

一个复杂点了例子如查找点为(2,4.5)。

1、同样先进行二叉查找,先从(7,2)查找到(5,4)节点,在进行查找时是由y = 4为分割超平面的,由于查找点为y值为4.5,因此进入右子空间查找到(4,7),形成搜索路径<(7,2),(5,4),(4,7)>,

2、取(4,7)为当前最近邻点,计算其与目标查找点的距离为3.202。然后回溯到(5,4),计算其与查找点之间的距离为3.041。

       ((4,7)与目标查找点的距离为3.202,而(5,4)与查找点之间的距离为3.041,所以(5,4)为查询点的最近点;)

3、以(2,4.5)为圆心,以3.041为半径作圆,如图4所示。可见该圆和y = 4超平面交割,所以需要进入(5,4)左子空间进行查找。此时需将(2,3)节点加入搜索路径中得<(7,2),(2,3)>。

4、回溯至(2,3)叶子节点,(2,3)距离(2,4.5)比(5,4)要近,所以最近邻点更新为(2,3),最近距离更新为1.5。

5、回溯至(7,2),以(2,4.5)为圆心1.5为半径作圆,并不和x = 7分割超平面交割,如图5所示。

至此,搜索路径回溯完。返回最近邻点(2,3),最近距离1.5。

                   图4                                                                         图5

上述的kd树是完成最近邻的搜索,其实也可以找到最近的k个点。 


k-d树查询算法的简要说明:

  • 从root节点开始,DFS搜索直到叶子节点,同时在stack中顺序存储已经访问的节点。
  • 如果搜索到叶子节点,当前的叶子节点被设为最近邻节点。
  • 然后通过stack回溯:
    如果当前点的距离比最近邻点距离近,更新最近邻节点.
    然后检查以最近距离为半径的圆是否和父节点的超平面相交.
    如果相交,则必须到父节点的另外一侧,用同样的DFS搜索法,开始检查最近邻节点。
    如果不相交,则继续往上回溯,而父节点的另一侧子节点都被淘汰,不再考虑的范围中.
  • 当搜索回到root节点时,搜索完成,得到最近邻节点。

https://www.zydui.com/af754V28BBAFY.html
>

相关文章:

  • 树干结构剖面图
  • 木结构建筑的连接方式
  • 木结构连接节点图示
  • 构造平衡kd树
  • 近似最近邻搜索算法
  • k近邻法
  • 二叉搜索树建立
  • 二叉检索树
  • IQVIA醫藥咨詢隨筆雜談
  • 爬取英雄聯盟英雄皮膚數據
  • 英雄聯盟 連接服務器失敗 請檢查您的網絡 是否啟用修復程序進行修復,英雄聯盟玩不了,提示未知的directx錯誤...
  • 三位千萬富翁告訴你:錢是怎么賺來的
  • 芳香之城傳奇的美麗神話故事
  • Solid Converter PDF注冊碼
  • 修改linux下面的字符集
  • 30個不可思議的好玩又實用的HTML5移動應用
  • 安卓新出病毒幽靈推,回顧android歷史上的那些吸費病毒
  • 游戲編程技術貼:AI設計的若干規則闡述
  • mac啟動自動運行程序_什么啟動了,為什么在我的Mac上運行?
  • 什么是UserEventAgent,它為什么在Mac上運行?
  • 蔚來汽車新財報超預期,短期或難盈利互聯網造車行不通嗎?
  • 車行的進貨問題
  • spring BeanFactory 家族介紹
  • 地址家族/名字解析
  • VS中怎么調出資源方案管理器
  • 告別低效工作,幫你重新找回工作的掌控感
  • 從Mac連接Windows共享打印機(1)
  • c4d流體插件_Cinema 4D 流體模擬插件 TurbulenceFD C4D v1.0 Build 1425 Win64
  • 經典生活總結語錄(搞笑欣賞)
  • 項目打包打的是什么包_早安打工人是什么梗,朋友圈打工人文案語錄表情包!...
  • 前端學習從入門到高級全程記錄之25(webapi)
  • 中職計算機應用普測考試試題及答案,2017職稱計算機考試WPS_Office檢測練習及答案9...
  • 微型計算機的主板又稱為,供電設計比7999元的主板還猛,ROG M11A主板首次亮相
  • webStorm使用斷點
  • 逆風翻盤?順豐大股東聯手本來集團上演O2O+B2C生鮮大戲
  • 三國志戰略版:Daniel_“坦克兵種”象兵分析
  • RISK-V品牌的中國化歷程(下)
  • 網游找call通殺方法之另辟蹊徑