欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2023-12-17 09:24:52
本文首先介绍kd-tree的构造方法,然后介绍kd-tree的搜索流程及代码实现,最后给出本人利用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 divisionpoint { get; set; }

    /// <summary>
    /// 分裂类型
    /// </summary>
    public enumdivisiontype divisiontype { 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));

    // 根据方差确定分裂维度
    enumdivisiontype divisiontype = sortlistbyxoryvariances(xobtainvariance,    yobtainvariance, ref pointlist);

    // 获得中位数
    point medianpoint = obtainmedian(pointlist);
    int medianindex = pointlist.count / 2;

    // 构建节点
    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树搜索方法

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.divisiontype == enumdivisiontype.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.divisionpoint);
    double nearestpointdistance = obtaindistanfromtwopoint(searchpoint, nearestpoint);
    
    if (backtrackdistance < nearestpointdistance)
    {
      // 深拷贝节点的目的是为了避免损坏树
      kdtreenode searchnode = new kdtreenode()
      {
        divisionpoint = tracknode.divisionpoint,
        divisiontype = tracknode.divisiontype,
        leftchild = tracknode.leftchild,
        rightchild = tracknode.rightchild
      };
      nearestpoint = dfsbacktrackingsearch(searchnode, searchpoint);
   }
   // 递归到根节点
   return backtrcaksearch(searchpoint, nearestpoint);
  }
}


5. 源码交流

https://github.com/creammilk/c-kd-tree

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。

上一篇:

下一篇: