Kdtree（K-dimension tree）学习
以下總結純屬個人學習理解，如有不對還望留言改正。參考文章博客地址如下：
https://blog.csdn.net/likika2012/article/details/39619687
https://blog.csdn.net/zhjchengfeng5/article/details/7855241
https://www.joinquant.com/view/community/detail/c2c41c79657cebf8cd871b44ce4f5d97
https://zhuanlan.zhihu.com/p/22557068
https://www.cnblogs.com/dirge/p/6091241.html
https://leileiluoluo.com/posts/kdtree-algorithm-and-implementation.html
感謝幾位大神的詳細總結；
首先要學習kdtree就要先理解二叉樹，因為實現kdtree的數據結構是基于二叉樹思想來實現的。
二叉樹顧名思義就是一個根節點有兩個子節點；二叉樹思想：
二叉查找樹（Binary Search Tree，BST），是具有如下性質的二叉樹（來自wiki）：
1）若它的左子樹不為空，則左子樹上所有結點的值均小于它的根結點的值；
2）若它的右子樹不為空，則右子樹上所有結點的值均大于它的根結點的值；
3）它的左、右子樹也分別為二叉排序樹；如圖所示：
一個二叉樹結構永遠滿足：即根結點的左子樹中所有結點的值均小于根結點的值，而根結點的右子樹中所有結點的值均大于根結點的值。將一個1維數據集用一棵BST樹存儲后，當我們想要查詢某個數據是否位于該數據集合中時，只需要將查詢數據與結點值進行比較然后選擇對應的子樹繼續往下查找即可，查找的平均時間復雜度為：O(logN)，最壞的情況下是O(N)。
Kd-Tree與一維二叉查找樹之間的區別：
二叉查找樹：數據存放在樹中的每個結點（根結點、中間結點、葉子結點）中；
Kd-Tree：數據只存放在葉子結點，而根結點和中間結點存放一些空間劃分信息（例如劃分維度、劃分值）；
節點的狀態：分裂點（split_point）?分裂方式（split_method）?? 左兒子（left_son）?右兒子（right_son）
? 我們建樹的規則就是節點的狀態中的：分裂方式（split_method）
? ? ? ? 想必讀者已經看見上面的關鍵字了：分裂點 分裂方式，為什么反復的出現分裂這兩個字呢？難道建一顆 K-D tree 還要分裂什么，分裂空間？
? ? ? ? 對，K-D tree的建立就是分裂空間的過程！
? ? ? ? 怎么建樹呢？
? ? ? ? 建樹依據：
? ? ? ? ? ? ? ? 先計算當前區間 [ L , R ] 中（這里的區間是點的序號區間，而不是我們實際上的坐標區間），每個點的坐標的每一維度上的方差，取方差最大的那一維，設為 d，作為我們的分裂方式（split_method ），把區間中的點按照在 d 上的大小，從小到大排序，取中間的點 sorted_mid 作為當前節點記錄的分裂點，然后，再以 [ L , sorted_mid-1 ] 為左子樹建樹
?， 以 [sorted_mid+1 , R ] 為右子樹建樹，這樣，當前節點的所有狀態我們便確定下來了：
? ? ? ? ? ? ? ? split_point= sorted_mid
? ? ? ? ? ? ? ? split_method= d
? ? ? ? ? ? ? ? left_son ? ?= ?[ L , sorted_mid-1 ]
? ? ? ? ? ? ? ? right_son = ?[ sorted_mid+1 , R ]
?
?
將其推廣到K維空間，即kdtree（一般常用即三維即可）。
總體思想就是：首先確定哪個維度的方差大，按照維度大的維度進行從小到大排序，尋找中點，在此維度上以該中點作為分割線，分別建立左右子樹；然后在左右子樹上重復此過程。
樹是建了，那么查詢呢?
? ? ? ? 查詢過程：
? ? ? ? ? ? ? ? 查詢，其實相當于我們要將一個點“添加”到已經建好的 K-D tree 中，但并不是真的添加進去，只是找到他應該處于的子空間即可，所以查詢就顯得簡單的毒攻了
? ? ? ? ? ? ? ? 每次在一個區間中查詢的時候，先看這個區間的分裂方式是什么，也就是說，先看這個區間是按照哪一維來分裂的，這樣如果這個點對應的那一維上面的值比根節點的小，就在根節點的左子樹上進行查詢操作，如果是大的話，就在右子樹上進查詢操作
? ? ? ? ? ? ? ? 每次回溯到了根節點（也就是說，對他的一個子樹的查找已經完成了）的時候，判斷一下，以該點為圓心，目前找到的最小距離為半徑，看是否和分裂區間的那一維所構成的平面相交，要是相交的話，最近點可能還在另一個子樹上，所以還要再查詢另一個子樹，同時，還要看能否用根節點到該點的距離來更新我們的最近距離。為什么是這樣的，我們可以用一幅圖來說明：
在查詢到左兒子的時候，我們發現，現在最小的距離是 r = 10 ，當回溯到父親節點的時候，我們發現，以目標點（10,1）為圓心，現在的最小距離 r = 10 為半徑做圓，與分割平面 y = 8 相交，這時候，如果我們不在父親節點的右兒子進行一次查找的話，就會漏掉
?（10,9） 這個點，實際上，這個點才是距離目標點 （10,1） 最近的點
由于每次查詢的時候可能會把左右兩邊的子樹都查詢完，所以，查詢并不是簡單的 log(n) 的，最壞的時候能夠達到 sqrt(n)。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>#define INT_INF 0x3fffffff
#define LL_INF 0x3fffffffffffffff
#define EPS 1e-12
#define MOD 1000000007
#define PI 3.141592653579798
#define N 60000using namespace std;typedef long long LL;//定義類型LL代表Long Long
typedef unsigned long long ULL;
typedef double DB;struct data//定義數據結構
{LL pos[10];int id;
} T[N] , op , point;int split[N],now,n,demension;
bool use[N];
LL ans,id;
DB var[10];bool cmp(data a,data b)//參數傳入結構
{return a.pos[split[now]]<b.pos[split[now]];//比較函數
}void build(int L,int R)
{if(L>R) return;int mid=(L+R)>>1;//求出 每一維 上面的方差for(int pos=0;pos<demension;pos++){DB ave=var[pos]=0.0;for(int i=L;i<=R;i++){ave+=T[i].pos[pos];}ave/=(R-L+1);for(int i=L;i<=R;i++){var[pos]+=(T[i].pos[pos]-ave)*(T[i].pos[pos]-ave);}var[pos]/=(R-L+1);}//找到方差最大的那一維，用它來作為當前區間的 split_methodsplit[now=mid]=0;for(int i=1;i<demension;i++){if(var[split[mid]]<var[i]) split[mid]=i;}//對區間排排序，找到中間點nth_element(T+L,T+mid,T+R+1,cmp);build(L,mid-1);build(mid+1,R);
}void query(int L,int R)
{if(L>R) return;int mid=(L+R)>>1;//求出目標點 op 到現在的根節點的距離LL dis=0;for(int i=0;i<demension;i++){dis+=(op.pos[i]-T[mid].pos[i])*(op.pos[i]-T[mid].pos[i]);}//如果當前區間的根節點能夠用來更新最近距離，并且 dis 小于已經求得的 ansif(!use[T[mid].id] && dis<ans){ans=dis; //更新最近距離point=T[mid]; //更新取得最近距離下的點id=T[mid].id; //更新取得最近距離的點的 id}//計算 op 到分裂平面的距離LL radius=(op.pos[split[mid]]-T[mid].pos[split[mid]])*(op.pos[split[mid]]-T[mid].pos[split[mid]]);//對子區間進行查詢if(op.pos[split[mid]]<T[mid].pos[split[mid]]){query(L,mid-1);if(radius<=ans) query(mid+1,R);}else{query(mid+1,R);if(radius<=ans) query(L,mid-1);}
}int main()
{while(scanf("%d%d",&n,&demension)!=EOF){//讀入 n 個點for(int i=1;i<=n;i++){for(int j=0;j<demension;j++){scanf("%I64d",&T[i].pos[j]);}T[i].id=i;}build(1,n); //建樹int m,q; scanf("%d",&q); // q 個詢問while(q--){memset(use,0,sizeof(use));for(int i=0;i<demension;i++){scanf("%I64d",&op.pos[i]);}scanf("%d",&m);printf("the closest %d points are:\n",m);while(m--){ans=(((LL)INT_INF)*INT_INF);query(1,n);for(int i=0;i<demension;i++){printf("%I64d",point.pos[i]);if(i==demension-1) printf("\n");else printf(" ");}use[id]=1;}}}return 0;
}
詳細解釋：詳細解釋：詳細解釋：詳細解釋：詳細解釋：詳細解釋：詳細解釋：
1維劃分原則：在構造1維BST樹時，一個1維數據根據其與樹的根結點和中間結點進行大小比較的結果來決定是劃分到左子樹還是右子樹
將二叉樹思想運用到kdtree中，首先需要確定怎樣劃分左子樹和右子樹，即一個K維數據是依據什么被劃分到左子樹或右子樹的。
K維劃分原則：將一個K維數據與Kd-tree的根結點和中間結點進行比較，只不過不是對K維數據進行整體的比較，而是選擇某一個維度Di（i代表維度x,y,z等），然后比較兩個K維數在該維度Di上的大小關系，即每次選擇一個維度Di來對K維數據進行劃分，相當于用一個垂直于該維度Di的超平面將K維數據空間一分為二，平面一邊的所有K維數據在Di維度上的值小于平面另一邊的所有K維數據對應維度上的值。也就是說，我們每選擇一個維度進行如上的劃分，就會將K維數據空間劃分為兩個部分，如果我們繼續分別對這兩個子K維空間進行如上的劃分，又會得到新的子空間，對新的子空間又繼續劃分，重復以上過程直到每個子空間都不能再劃分為止。（此過程會涉及兩個疑問：1.每次對子空間的劃分時，怎樣確定在哪個維度上進行劃分；2。在某個維度上進行劃分時，怎樣確保在這一維度上的劃分得到的兩個子集合的數量盡量相等，即左子樹和右子樹中的結點個數盡量相等）
針對于第一個疑問：
最簡單的方法就是輪著來，即如果這次選擇了在第i維上進行數據劃分，那下一次就在第j(j≠i)維上進行劃分，例如：j = (i mod k) + 1（此處是先+1再求余還是先求余數再+1，沒確定？？？？）。想象一下我們切豆腐時，先是豎著切一刀，切成兩半后，再橫著來一刀，就得到了很小的方塊豆腐。
可是“輪著來”的方法是否可以很好地解決問題呢？再次想象一下，我們現在要切的是一根木條，按照“輪著來”的方法先是豎著切一刀，木條一分為二，干凈利落，接下來就是再橫著切一刀，這個時候就有點考驗刀法了，如果木條的直徑（橫截面）較大，還可以下手，如果直徑較小，就沒法往下切了。因此，如果K維數據的分布像上面的豆腐一樣，“輪著來”的切分方法是可以奏效，但是如果K維度上數據的分布像木條一樣，“輪著來”就不好用了。因此，還需要想想其他的切法。
如果一個K維數據集合的分布像木條一樣，那就是說明這K維數據在木條較長方向代表的維度上，這些數據的分布散得比較開，數學上來說，就是這些數據在該維度上的方差（invariance）比較大，換句話說，正因為這些數據在該維度上分散的比較開，我們就更容易在這個維度上將它們劃分開，因此，這就引出了我們選擇維度的另一種方法：最大方差法（max invarince），即每次我們選擇維度進行劃分時，都選擇具有最大方差維度。
基于方差的維度選擇舉例：
假設有6個二維數據點{(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2)}，數據點位于二維空間內，如下圖所示。為了能有效的找到最近鄰，k-d樹采用分而治之的思想，即將整個空間劃分為幾個小部分，首先，粗黑線將空間一分為二，然后在兩個子空間中，細黑直線又將整個空間劃分為四部分，最后虛黑直線將這四部分進一步劃分。
? 6個二維數據點{(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2)}構建kd樹的具體步驟為：
- 確定：split域=x。具體是：6個數據點在x，y維度上的數據方差分別為39，28.63，所以在x軸上方差更大，故split域值為x；
- 確定：Node-data = （7,2）。具體是：根據x維上的值將數據排序，6個數據的中值(所謂中值，即中間大小的值)為7，所以Node-data域位數據點（7,2）。這樣，該節點的分割超平面就是通過（7,2）并垂直于：split=x軸的直線x=7；
- 確定：左子空間和右子空間。具體是：分割超平面x=7將整個空間分為兩部分：x<=7的部分為左子空間，包含3個節點={(2,3),(5,4),(4,7)}；另一部分為右子空間，包含2個節點={(9,6)，(8,1)}；
如上算法所述，kd樹的構建是一個遞歸過程，我們對左子空間和右子空間內的數據重復根節點的過程就可以得到一級子節點（5,4）和（9,6），同時將空間和數據集進一步細分，如此往復直到空間中只包含一個數據點。
與此同時，經過對上面所示的空間劃分之后，我們可以看出，點(7,2)可以為根結點，從根結點出發的兩條紅粗斜線指向的(5,4)和(9,6)則為根結點的左右子結點，而(2,3)，(4,7)則為(5,4)的左右孩子(通過兩條細紅斜線相連)，最后，(8,1)為(9,6)的左孩子(通過細紅斜線相連)。如此，便形成了下面這樣一棵k-d樹，如下左圖。右圖為? k-d樹的數據結構。
?
****基于上例延申的最近鄰查詢即k=1的Knn。給定點（2.1，3.1），查詢此點的最近鄰點。
星號表示要查詢的點（2.1,3.1）。通過二叉搜索，順著搜索路徑很快就能找到最鄰近的近似點，也就是葉子節點（2,3）。而找到的葉子節點并不一定就是最鄰近的，最鄰近肯定距離查詢點更近，應該位于以查詢點為圓心且通過葉子節點的圓域內。為了找到真正的最近鄰，還需要進行相關的‘回溯'操作。也就是說，算法首先沿搜索路徑反向查找是否有距離查詢點更近的數據點。
? ? 以查詢（2.1,3.1）為例：
- 二叉樹搜索：先從（7,2）點開始進行二叉查找，然后到達（5,4），最后到達（2,3），此時搜索路徑中的節點為<(7,2)，(5,4)，(2,3)>，首先以（2,3）作為當前最近鄰點，計算其到查詢點（2.1,3.1）的距離為0.1414，
- 回溯查找：在得到（2,3）為查詢點的最近點之后，回溯到其父節點（5,4），并判斷在該父節點的其他子節點空間中是否有距離查詢點更近的數據點。以（2.1,3.1）為圓心，以0.1414為半徑畫圓，如下圖所示。發現該圓并不和超平面y = 4交割,(注意此處是因為與右子空間無交集)，因此不用進入（5,4）節點右子空間中(圖中灰色區域)去搜索；
- 最后，再回溯到（7,2），以（2.1,3.1）為圓心，以0.1414為半徑的圓更不會與x = 7超平面交割，因此不用進入（7,2）右子空間進行查找。至此，搜索路徑中的節點已經全部回溯完，結束整個搜索，返回最近鄰點（2,3），最近距離為0.1414。*****定點（2，4.5），查詢此點的最近鄰點。
- 同樣先進行二叉查找，先從（7,2）查找到（5,4）節點，在進行查找時是由y = 4為分割超平面的，由于查找點為y值為4.5，因此進入右子空間查找到（4,7），形成搜索路徑<(7,2)，(5,4)，(4,7)>，但（4,7）與目標查找點的距離為3.202，而（5,4）與查找點之間的距離為3.041，所以（5,4）為查詢點的最近點；
- 以（2，4.5）為圓心，以3.041為半徑作圓，如下圖所示?？梢娫搱A和y = 4超平面交割，所以需要進入（5,4）左子空間進行查找，也就是將（2,3）節點加入搜索路徑中得<(7,2)，(2,3)>；于是接著搜索至（2,3）葉子節點，（2,3）距離（2,4.5）比（5,4）要近，所以最近鄰點更新為（2，3），最近距離更新為1.5；
- 回溯查找至（5,4），直到最后回溯到根結點（7,2）的時候，以（2,4.5）為圓心1.5為半徑作圓，并不和x = 7分割超平面交割，如下圖所示。至此，搜索路徑回溯完，返回最近鄰點（2,3），最近距離1.5。
- ******（上述兩次實例表明，當查詢點的鄰域與分割超平面兩側空間交割時，需要查找另一側子空間，導致檢索過程復雜，效率下降。）
總結
以上是生活随笔為你收集整理的Kdtree（K-dimension tree）学习的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： PCL两种方式的点云读写
- 下一篇： 将三维点云投影到XOZ面上