C#透過KD樹進行距離最近點的查找的實例分析

這篇文章主要為大家詳細介紹了C#透過KD樹進行距離最近點的查找，具有一定的參考價值，有興趣的小夥伴們可以參考一下

本文首先介紹Kd-Tree的建構方法，然後介紹Kd-Tree的搜尋流程及程式碼實現，最後給出本人利用C#語言實現的二維KD樹代碼。這也是我自己動手實現的第一個樹形的資料結構。理解上難免會有偏差，敬請各位多多斧正。

1. KD樹介紹

Kd-Tree（KD樹），即K-dimensional tree，是一種高維索引樹狀資料結構，常用於在大規模的高維資料空間進行最鄰近查找和近似最鄰近查找。我實現的KD樹是二維的Kd - tree。目的是在點集中尋找最近點。參考資料是Kd-Tree的百度百科。並且根據百度百科的邏輯組織了程式碼。

2. KD樹的數學解釋

#3. KD樹的建構方法

這裡是用的二維點集來建構Kd-tree。三維的與此類似。
樹中每個節點的資料類型：

public class KDTreeNode
  {
    /// <summary>
    /// 分裂点
    /// </summary>
    public Point pisionPoint { get; set; }

    /// <summary>
    /// 分裂类型
    /// </summary>
    public EnumpisionType pisionType { get; set; }

    /// <summary>
    /// 左子节点
    /// </summary>
    public KDTreeNode LeftChild { get; set; }

    /// <summary>
    /// 右子节点
    /// </summary>
    public KDTreeNode RightChild { get; set; }
  }

3.1 KD樹建構邏輯流程

• 將所有的點放入集合a中

• 對集合所有點的X座標求方差xv,Y座標求得方差yv

• 如果xv > ; yv,則對集合a依X座標進行排序。如果 yv > xv,則對集合a依y座標進行排序。

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

• 建構節點，節點的值為a[m-1],如果運算集合中節點的數量大於1，則左節點對[0，m-2]重複2 -5步，右節點為對[m,a.count]重複2-5步；反之，則該節點為葉子節點。
  

3.2 程式碼實作

#

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

    // 根据方差确定分裂维度
    EnumpisionType pisionType = SortListByXOrYVariances(xObtainVariance,    yObtainVariance, ref pointList);

    // 获得中位数
    Point medianPoint = ObtainMedian(pointList);
    int medianIndex = pointList.Count / 2;

    // 构建节点
    KDTreeNode treeNode = new KDTreeNode()
    {
      pisionPoint = medianPoint,
      pisionType = pisionType,
      LeftChild = CreateTreeNode(pointList.Take(medianIndex).ToList()),
      RightChild = CreateTreeNode(pointList.Skip(medianIndex + 1).ToList())
    };
    return treeNode;
  }
  else
  {
    return null;
  }
}

4. KD樹搜尋方法

#Kd-Tree的整體搜尋流程先根據普通的查找找到一個最近的葉子節點。但是這個葉子節點不一定是最近的點。再進行回溯的操作找到最近點。

4.1 KD樹搜尋邏輯流程

• 對於根據點集建構的樹t,以及查找點p.將根節點作為節點t進行如下的操作

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

• ##則確定t的分裂方式，如果是依照x軸進行分裂，則用p的x值與節點的分割點的x值進行比較，反之則進行Y座標的比較

• 如果p的比較值小於t的比較值，則將t指定為t的左孩子節點。反之將t指定為t的右孩子節點，執行第2步

• 定義檢索點m，將m設定為n

• 計算m與p的距離d1,n與m的距離d2。

• 如果d1 >= d2且有父節點,則將m的父節點作為m的值執行5步，若沒有父節點，則得到真正的最近點TN;如果d1 < d2表示n點不是最近點，執行第8步驟

• #若n有兄弟節點，則n = n的兄弟節點；若n沒有兄弟節點，則n = n的父節點。刪除原來的n節點。將m的值設定為新的n節點；執行第6步。

  
  

4.2 程式碼實作

public Point FindNearest(Point searchPoint)
{
  // 按照查找方式寻找最近点
  Point nearestPoint = DFSSearch(this.rootNode, searchPoint);
  
  // 进行回溯
  return BacktrcakSearch(searchPoint, nearestPoint);
}


private Point DFSSearch(KDTreeNode node,Point searchPoint,bool pushStack = true)
{
  if(pushStack == true)
  {
    // 利用堆栈记录查询的路径，由于树节点中没有记载父节点的原因
    backtrackStack.Push(node);
  }
  if (node.pisionType == EnumpisionType.X)
  {
    return DFSXsearch(node,searchPoint);
  }
  else
  {
    return DFSYsearch(node, searchPoint);
  }
}

private Point BacktrcakSearch(Point searchPoint,Point nearestPoint)
{
  // 如果记录路径的堆栈为空则表示已经回溯到根节点，则查到的最近点就是真正的最近点
  if (backtrackStack.IsEmpty())
  {
    return nearestPoint;
  }
  else
  {
    KDTreeNode trackNode = backtrackStack.Pop();
    
    // 分别求回溯点与最近点距查找点的距离
    double backtrackDistance = ObtainDistanFromTwoPoint(searchPoint,     trackNode.pisionPoint);
    double nearestPointDistance = ObtainDistanFromTwoPoint(searchPoint, nearestPoint);
    
    if (backtrackDistance < nearestPointDistance)
    {
      // 深拷贝节点的目的是为了避免损坏树
      KDTreeNode searchNode = new KDTreeNode()
      {
        pisionPoint = trackNode.pisionPoint,
        pisionType = trackNode.pisionType,
        LeftChild = trackNode.LeftChild,
        RightChild = trackNode.RightChild
      };
      nearestPoint = DFSBackTrackingSearch(searchNode, searchPoint);
   }
   // 递归到根节点
   return BacktrcakSearch(searchPoint, nearestPoint);
  }
}

以上是C#透過KD樹進行距離最近點的查找的實例分析的詳細內容。更多資訊請關注PHP中文網其他相關文章！