C#通过KD树进行距离最近点的查找的实例分析

本文首先介绍Kd-Tree的构造方法，然后介绍Kd-Tree的搜索流程及代码实现，最后给出本人利用C#语言实现的二维KD树代码。这也是我自己动手实现的第一个树形的数据结构。理解上难免会有偏差，敬请各位多多斧正。

Kd-Tree（KD树），即K-dimensional tree，是一种高维索引树形数据结构，常用于在大规模的高维数据空间进行最邻近查找和近似最邻近查找。我实现的KD树是二维的Kd - tree。目的是在点集中寻找最近点。参考资料是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）。

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步

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树进行距离最近点的查找的实例分析的详细内容，更多内容请关注技术你好其它相关文章！