目錄

前言

一、什么是KD樹

二、為什么要用KD樹

三、KD樹的基本思路

四、KD樹的幾種情況分析

4.1 另一子空間不存在更近的點

4.2?另一子空間存在更近的點

4.3 小結(jié)

五、KD樹的代碼（二維點，python版本）

六、KD樹的代碼（多維版本）

6.1 python版本

七、KD樹的應(yīng)用

7.1 找目標(biāo)平面或者空間中離目標(biāo)點的最近點

7.2?找目標(biāo)平面或者空間中離目標(biāo)點的若干個最近點

八、參考資料

前言

由于在做項目時遇到平面內(nèi)最近點求解的問題，需要用到KD樹簡化算法，減少計算資源，因此本文記錄這個過程中學(xué)到的知識。

一、什么是KD樹

kd-tree（k-dimensional樹的簡稱），kd樹就是一種對k維空間中的實例點進行存儲以便對其進行快速檢索的樹形數(shù)據(jù)結(jié)構(gòu)，可以運用在k近鄰法中，實現(xiàn)快速k近鄰搜索。構(gòu)造kd樹相當(dāng)于不斷地用垂直于坐標(biāo)軸的超平面將k維空間切分。k-d樹是每個節(jié)點都為k維點二叉樹。所有非葉子節(jié)點可以視作用超平面把空間分割成兩半空間。節(jié)點左邊的子樹代表在超平面左邊的點，節(jié)點右邊的子樹代表在超平面右邊的點。

二、為什么要用KD樹

主要是為了快速計算，節(jié)省計算資源。如前言中提到的例子，計算平面中一堆點中哪一個和目標(biāo)點最近的問題，如果使用常規(guī)方法需要計算所有點與目標(biāo)點的距離，然后進行比較，這樣在平面中點非常多的時候非常浪費計算資源，速度也很慢。為了解決這個問題，可以在這個過程中引入KD樹進行算法上的簡化。

三、KD樹的基本思路

下面是一個學(xué)習(xí)KD樹的經(jīng)典案例：

在二維平面上有以下六個點：(2,3），（5,4），（9,6），（4,7），（8,1），（7,2）

KD樹的目的要確定圖1中這些分割空間的分割線，確定步驟如下：

（1）第一步，將上述六個點的點集按照二維平面的第一維（x軸）對數(shù)據(jù)進行排序，排序結(jié)果為（2,3），（4,7），（5,4），（7,2），（8,1），（9,6）

（2） 第二步，取得上述點集的中位數(shù)處的點，偶數(shù)個數(shù)的中位數(shù)一般取大的那個，在上述點集中取到的為（7,2），在該點處對平面進行劃分，如圖1中（7,2）位置畫上一條豎線

（3）第三步，將由（7,2）劃分的左右兩平面中的剩余點按照二維平面的第二維（y軸）對數(shù)據(jù)排序，排序結(jié)果為左枝：（2,3），（5,4），（4,7）和右枝（8,1），（9,6）

（4）第四步，將左枝和右枝分別取中位數(shù)點作為新的節(jié)點，按照第一維繼續(xù)排序，直致每一個子枝上只剩一個點，這個點被稱作葉子。

上述過程畫成圖如下：

需要注意的是，每次劃分之后排序的邏輯是按照緯度一次類推的，在二維平面中就是按x,y,x,y,x,y....軸排序，如果在三維空間中就是x,y,z,x,y,z,x,y,z....軸排序。

進行完上述操作后就將數(shù)據(jù)劃分完畢，可以將目標(biāo)點放到該KD樹中比較了。

四、KD樹的幾種情況分析

4.1 另一子空間不存在更近的點

案例如下：

初始點集仍為(2,3），（5,4），（9,6），（4,7），（8,1），（7,2）六個點

目標(biāo)點為（2.1,3.1）

依據(jù)上述KD樹的搜索邏輯，操作如下：

（1）將初始點擊根據(jù)第一維（X坐標(biāo)）排序為（2,3）（4,7）（5,4）（7,2）（8,1）（9，6），其中位數(shù)取4，也就是（7,2）點，在上圖中 X=7 處畫上分割線

（2）判斷目標(biāo)點的X坐標(biāo)2.1小于（7,2），因此取劃分后的左側(cè)空間中的點（2，3）（4,7）（5,4）

（3）將上述點集根據(jù)第二維（Y坐標(biāo)）排序為（2,3）（5,4）（4,7），其中位數(shù)是2，即（5,4）點，在平面中畫上該線

（4）判斷目標(biāo)點的Y坐標(biāo)3.1小于（5,4），因此在劃分后的下方空間中

（5）此時改空間中僅有（2,3）一個點，到此結(jié)束劃分空間的操作

（6）計算此時得到的最后點與目標(biāo)點之間的距離為，暫時記錄下這個值tempDis

（7）下面開始進行回溯

計算目標(biāo)點（2.1,3.1）與最后的節(jié)點（5,4）之間Y軸的距離差記為dist，計算得0.9，這個值大于≈0.1414，不可能在節(jié)點（5,4）的上側(cè)空間有更近的點，因此在節(jié)點（5,4）下方空間中找到的點（2,3）已經(jīng)是最近的點。繼續(xù)回溯上一個節(jié)點（5,4），此時在X軸上的距離2.9>0.1414，不存在更近點的可能，因此回溯結(jié)束，最近的點為（2,3），最近的距離為。

實際情況中回溯時會碰到上述dist小于tempDis，有可能在上一節(jié)點的另一空間中存在更近點的可能，這種情況參見下面的案例。

4.2?另一子空間存在更近的點

案例如下：

初始點集為（5,3），（2.5,5），（8,4.5），（2,2），（3.5,8），（8,2.5），（5.5,7.5）

目標(biāo)點為（4.5,7.5）

依據(jù)KD樹的搜索邏輯，操作如下：

（1）將初始點擊根據(jù)第一維（X坐標(biāo)）排序為（2,2）（2.5,5）（3.5,8）（5,3）（5.5,7.5）（8，4.5），（8,2.5），其中位數(shù)取4，也就是（5,3）點，在上圖中 X=5 處畫上分割線

（2）判斷目標(biāo)點的X坐標(biāo)4.5小于（5,3），因此取劃分后的左側(cè)空間中的點（2，2）（2.5,5）（3.5,8）

（3）將上述點集根據(jù)第二維（Y坐標(biāo)）排序為（2，2）（2.5,5）（3.5,8），其中位數(shù)是2，即（2.5,5）點，在平面中畫上該線Y=5

（4）判斷目標(biāo)點的Y坐標(biāo)7.5大于（2.5,5），因此在劃分后的上方空間中

（5）此時改空間中僅有（2.5,8）一個點（點D），到此結(jié)束劃分空間的操作

（6）計算此時得到的最后點與目標(biāo)點之間的距離為≈2.06，暫時記錄下這個值tempDis

（7）下面開始進行回溯

計算目標(biāo)點（4.5,7.5）與最后的節(jié)點B（2.5,5）之間Y軸的距離差記為dist，計算得2.5，這個值大于2.06，不可能存在節(jié)點（2.5,5）的下側(cè)空間有更近的點；繼續(xù)回溯上一個節(jié)點A（5,3），此時在X軸上的距離dist（5-4.5=0.5）<2.06，所以在A的右側(cè)空間中有可能存在更近的點，我們進入到節(jié)點A的右側(cè)空間，繼續(xù)之前的操作，發(fā)現(xiàn)存在點E（5.5,7.5），其與目標(biāo)點S之間的距離為1,1<2.06，因此最近距離tempDis更新為1，最近點更新為（5.5,7.5），回溯結(jié)束。

4.3 小結(jié)

總結(jié)一下，在寫KD樹的代碼之前需要有一些準(zhǔn)備：

（1）定義一個節(jié)點的類，需要有該節(jié)點的點坐標(biāo)、左枝、右枝、劃分的維度（用于確認(rèn)需要根據(jù)哪個維度來對坐標(biāo)排序）

（2）確定遞歸的出口（當(dāng)劃分的點集中只有一個點時結(jié)束）

（3）計算中位數(shù)點的編號

（4）計算當(dāng)前劃分的維度

（5）計算兩個點的歐式距離（勾股定理）

（6）回溯獲得最近點的坐標(biāo)

五、KD樹的代碼（二維點，python版本）

import math

pts = [(5,3),(2.5,5),(8,4.5),(2,2),(3.5,8),(8,2.5),(5.5,7.5)]  #點集
targetPt = (4.5,7.5)  #目標(biāo)點

class Node():
    def __init__(self,pt,leftBranch,rightBranch,dimension):
        self.pt = pt
        self.leftBranch = leftBranch
        self.rightBranch = rightBranch
        self.dimension = dimension

class KDTree():
    def __init__(self,data):
        self.nearestPt = None
        self.nearestDis = math.inf
    
    def createKDTree(self,currPts,dimension):
        if(len(currPts) == 0):
            return None
        mid = self.calMedium(currPts)
        sortedData = sorted(currPts,key=lambda x:x[dimension])
        leftBranch = self.createKDTree(sortedData[:mid],self.calDimension(dimension))
        rightBranch = self.createKDTree(sortedData[mid+1:],self.calDimension(dimension))
        return Node(sortedData[mid],leftBranch,rightBranch,dimension)

    def calMedium(self,currPts):
        return len(currPts) // 2

    def calDimension(self,dimension):
        return (dimension+1)%2

    def calDistance(self,p0,p1):
        return math.sqrt((p0[0]-p1[0])**2+(p0[1]-p1[1])**2)

    def getNearestPt(self,root,targetPt):
        self.search(root,targetPt)
        return self.nearestPt,self.nearestDis
        
    def search(self,node,targetPt):
        if node == None:
            return
        dist = node.pt[node.dimension] - targetPt[node.dimension]
        if(dist > 0):#目標(biāo)點在節(jié)點的左側(cè)或上側(cè)
            self.search(node.leftBranch,targetPt)
        else:
            self.search(node.rightBranch,targetPt)
        tempDis = self.calDistance(node.pt,targetPt)
        if(tempDis < self.nearestDis):
            self.nearestDis = tempDis
            self.nearestPt = node.pt
        #回溯
        if(self.nearestDis > abs(dist)):
            if(dist > 0):
                self.search(node.rightBranch,targetPt)
            else:
                self.search(node.leftBranch,targetPt)

if __name__ == "__main__":
    kdtree = KDTree(pts) 
    root = kdtree.createKDTree(pts,0)   
    pt,minDis = kdtree.getNearestPt(root,targetPt)
    print("最近的點是",pt,"最小距離是",str(minDis))

六、KD樹的代碼（多維版本）

6.1 python版本

import math

pts = []  #點集，任意維度的點集
targetPt =   #目標(biāo)點，任意維度的點

class Node():
    def __init__(self,pt,leftBranch,rightBranch,dimension):
        self.pt = pt
        self.leftBranch = leftBranch
        self.rightBranch = rightBranch
        self.dimension = dimension

class KDTree():
    def __init__(self,data):
        self.nearestPt = None
        self.nearestDis = math.inf
    
    def createKDTree(self,currPts,dimension):
        if(len(currPts) == 0):
            return None
        mid = self.calMedium(currPts)
        sortedData = sorted(currPts,key=lambda x:x[dimension])
        leftBranch = self.createKDTree(sortedData[:mid],self.calDimension(dimension))
        rightBranch = self.createKDTree(sortedData[mid+1:],self.calDimension(dimension))
        return Node(sortedData[mid],leftBranch,rightBranch,dimension)

    def calMedium(self,currPts):
        return len(currPts) // 2

    def calDimension(self,dimension): # 區(qū)別就在于這里，幾維就取余幾
        return (dimension+1)%len(targetPt)

    def calDistance(self,p0,p1):
        return math.sqrt((p0[0]-p1[0])**2+(p0[1]-p1[1])**2)

    def getNearestPt(self,root,targetPt):
        self.search(root,targetPt)
        return self.nearestPt,self.nearestDis
        
    def search(self,node,targetPt):
        if node == None:
            return
        dist = node.pt[node.dimension] - targetPt[node.dimension]
        if(dist > 0):#目標(biāo)點在節(jié)點的左側(cè)或上側(cè)
            self.search(node.leftBranch,targetPt)
        else:
            self.search(node.rightBranch,targetPt)
        tempDis = self.calDistance(node.pt,targetPt)
        if(tempDis < self.nearestDis):
            self.nearestDis = tempDis
            self.nearestPt = node.pt
        #回溯
        if(self.nearestDis > abs(dist)):
            if(dist > 0):
                self.search(node.rightBranch,targetPt)
            else:
                self.search(node.leftBranch,targetPt)

if __name__ == "__main__":
    kdtree = KDTree(pts) 
    root = kdtree.createKDTree(pts,0)   
    pt,minDis = kdtree.getNearestPt(root,targetPt)
    print("最近的點是",pt,"最小距離是",str(minDis))

七、KD樹的應(yīng)用

7.1 Unity找目標(biāo)平面或者空間中離目標(biāo)點的最近點

同上相似，不再贅述。

7.2?找目標(biāo)平面或者空間中離目標(biāo)點的若干個最近點

八、參考資料

[1]?https://www.cnblogs.com/bambipai/p/8435797.html

[2]?kd-tree_百度百科文章來源地址http://www.zghlxwxcb.cn/news/detail-718433.html

到了這里，關(guān)于算法（1）：KD樹的原理與基本代碼的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！