C#经由过程KD树举行间隔近来点的查找的实例剖析【C#.Net教程】,csharp,.net,查找

这篇文章主要为人人细致引见了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树举行间隔近来点的查找的实例剖析的细致内容，更多请关注ki4网别的相干文章！