這篇文章主要為大家展示了“C#如何通過(guò)KD樹(shù)進(jìn)行距離最近點(diǎn)實(shí)現(xiàn)查找”，內(nèi)容簡(jiǎn)而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“C#如何通過(guò)KD樹(shù)進(jìn)行距離最近點(diǎn)實(shí)現(xiàn)查找”這篇文章吧。

成都創(chuàng)新互聯(lián)長(zhǎng)期為上1000+客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開(kāi)放共贏平臺(tái)，與合作伙伴共同營(yíng)造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為信宜企業(yè)提供專業(yè)的成都網(wǎng)站制作、網(wǎng)站建設(shè)，信宜網(wǎng)站改版等技術(shù)服務(wù)。擁有10多年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開(kāi)發(fā)。

1. KD樹(shù)介紹

Kd-Tree（KD樹(shù)），即K-dimensional tree，是一種高維索引樹(shù)形數(shù)據(jù)結(jié)構(gòu)，常用于在大規(guī)模的高維數(shù)據(jù)空間進(jìn)行最鄰近查找和近似最鄰近查找。我實(shí)現(xiàn)的KD樹(shù)是二維的Kd - tree。目的是在點(diǎn)集中尋找最近點(diǎn)。參考資料是Kd-Tree的百度百科。并且根據(jù)百度百科的邏輯組織了代碼。

2. KD樹(shù)的數(shù)學(xué)解釋

3. KD樹(shù)的構(gòu)造方法

這里是用的二維點(diǎn)集進(jìn)行構(gòu)造Kd-tree。三維的與此類似。
樹(shù)中每個(gè)節(jié)點(diǎn)的數(shù)據(jù)類型：

public class KDTreeNode
  {
    /// 

    /// 分裂點(diǎn)
    /// 
    public Point DivisionPoint { get; set; }

    /// 

    /// 分裂類型
    /// 
    public EnumDivisionType DivisionType { get; set; }

    /// 

    /// 左子節(jié)點(diǎn)
    /// 
    public KDTreeNode LeftChild { get; set; }

    /// 

    /// 右子節(jié)點(diǎn)
    /// 
    public KDTreeNode RightChild { get; set; }
  }

3.1 KD樹(shù)構(gòu)造邏輯流程

• 將所有的點(diǎn)放入集合a中

• 對(duì)集合所有點(diǎn)的X坐標(biāo)求得方差xv,Y坐標(biāo)求得方差yv

• 如果xv > yv,則對(duì)集合a根據(jù)X坐標(biāo)進(jìn)行排序。如果 yv > xv,則對(duì)集合a根據(jù)y坐標(biāo)進(jìn)行排序。

• 得到排序后a集合的中位數(shù)m。則以m為斷點(diǎn)，將[0,m-2]索引的點(diǎn)放到a1集合中。將[m,a.count]索引的點(diǎn)放到a2的集合中（m點(diǎn)的索引為m-1）。

• 構(gòu)建節(jié)點(diǎn)，節(jié)點(diǎn)的值為a[m-1],如果操作集合中節(jié)點(diǎn)的個(gè)數(shù)大于1，則左節(jié)點(diǎn)對(duì)[0，m-2]重復(fù)2-5步，右節(jié)點(diǎn)為對(duì)[m,a.count]重復(fù)2-5步；反之，則該節(jié)點(diǎn)為葉子節(jié)點(diǎn)。

3.2 代碼實(shí)現(xiàn)

private KDTreeNode CreateTreeNode(List pointList)
{
  if (pointList.Count > 0)
  {
    // 計(jì)算方差
    double xObtainVariance = ObtainVariance(CreateXList(pointList));
    double yObtainVariance = ObtainVariance(CreateYList(pointList));

    // 根據(jù)方差確定分裂維度
    EnumDivisionType divisionType = SortListByXOrYVariances(xObtainVariance,    yObtainVariance, ref pointList);

    // 獲得中位數(shù)
    Point medianPoint = ObtainMedian(pointList);
    int medianIndex = pointList.Count / 2;

    // 構(gòu)建節(jié)點(diǎn)
    KDTreeNode treeNode = new KDTreeNode()
    {
      DivisionPoint = medianPoint,
      DivisionType = divisionType,
      LeftChild = CreateTreeNode(pointList.Take(medianIndex).ToList()),
      RightChild = CreateTreeNode(pointList.Skip(medianIndex + 1).ToList())
    };
    return treeNode;
  }
  else
  {
    return null;
  }
}

4. KD樹(shù)搜索方法

Kd-Tree的總體搜索流程先根據(jù)普通的查找找到一個(gè)最近的葉子節(jié)點(diǎn)。但是這個(gè)葉子節(jié)點(diǎn)不一定是最近的點(diǎn)。再進(jìn)行回溯的操作找到最近點(diǎn)。

4.1 KD樹(shù)搜索邏輯流程

• 對(duì)于根據(jù)點(diǎn)集構(gòu)建的樹(shù)t,以及查找點(diǎn)p.將根節(jié)點(diǎn)作為節(jié)點(diǎn)t進(jìn)行如下的操作

• 如果t為葉子節(jié)點(diǎn)。則得到最近點(diǎn)n的值為t的分裂點(diǎn)的值，跳到第5步;如果t不是葉子節(jié)點(diǎn),進(jìn)行第3步

• 則確定t的分裂方式，如果是按照x軸進(jìn)行分裂，則用p的x值與節(jié)點(diǎn)的分裂點(diǎn)的x值進(jìn)行比較，反之則進(jìn)行Y坐標(biāo)的比較

• 如果p的比較值小于t的比較值，則將t指定為t的左孩子節(jié)點(diǎn)。反之將t指定為t的右孩子節(jié)點(diǎn)，執(zhí)行第2步

• 定義檢索點(diǎn)m，將m設(shè)置為n

• 計(jì)算m與p的距離d1,n與m的距離d2。

• 如果d1 >= d2且有父節(jié)點(diǎn),則將m的父節(jié)點(diǎn)作為m的值執(zhí)行5步，若沒(méi)有父節(jié)點(diǎn)，則得到真正的最近點(diǎn)TN; 如果d1 < d2就表示n點(diǎn)不是最近點(diǎn)，執(zhí)行第8步

• 若n有兄弟節(jié)點(diǎn)，則 n = n的兄弟節(jié)點(diǎn)；若n沒(méi)有兄弟節(jié)點(diǎn)，則 n = n的父節(jié)點(diǎn)。刪除原來(lái)的n節(jié)點(diǎn)。將m的值設(shè)置為新的n節(jié)點(diǎn)；執(zhí)行第6步。

4.2 代碼實(shí)現(xiàn)

public Point FindNearest(Point searchPoint)
{
  // 按照查找方式尋找最近點(diǎn)
  Point nearestPoint = DFSSearch(this.rootNode, searchPoint);
  
  // 進(jìn)行回溯
  return BacktrcakSearch(searchPoint, nearestPoint);
}


private Point DFSSearch(KDTreeNode node,Point searchPoint,bool pushStack = true)
{
  if(pushStack == true)
  {
    // 利用堆棧記錄查詢的路徑，由于樹(shù)節(jié)點(diǎn)中沒(méi)有記載父節(jié)點(diǎn)的原因
    backtrackStack.Push(node);
  }
  if (node.DivisionType == EnumDivisionType.X)
  {
    return DFSXsearch(node,searchPoint);
  }
  else
  {
    return DFSYsearch(node, searchPoint);
  }
}

private Point BacktrcakSearch(Point searchPoint,Point nearestPoint)
{
  // 如果記錄路徑的堆棧為空則表示已經(jīng)回溯到根節(jié)點(diǎn)，則查到的最近點(diǎn)就是真正的最近點(diǎn)
  if (backtrackStack.IsEmpty())
  {
    return nearestPoint;
  }
  else
  {
    KDTreeNode trackNode = backtrackStack.Pop();
    
    // 分別求回溯點(diǎn)與最近點(diǎn)距查找點(diǎn)的距離
    double backtrackDistance = ObtainDistanFromTwoPoint(searchPoint,     trackNode.DivisionPoint);
    double nearestPointDistance = ObtainDistanFromTwoPoint(searchPoint, nearestPoint);
    
    if (backtrackDistance < nearestPointDistance)
    {
      // 深拷貝節(jié)點(diǎn)的目的是為了避免損壞樹(shù)
      KDTreeNode searchNode = new KDTreeNode()
      {
        DivisionPoint = trackNode.DivisionPoint,
        DivisionType = trackNode.DivisionType,
        LeftChild = trackNode.LeftChild,
        RightChild = trackNode.RightChild
      };
      nearestPoint = DFSBackTrackingSearch(searchNode, searchPoint);
   }
   // 遞歸到根節(jié)點(diǎn)
   return BacktrcakSearch(searchPoint, nearestPoint);
  }
}

以上是“C#如何通過(guò)KD樹(shù)進(jìn)行距離最近點(diǎn)實(shí)現(xiàn)查找”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！