KD ツリーによる最近点の検索の C# 分析例-C#.Net チュートリアル-php.cn

KD ツリーによる最近点の検索の C# 分析例

黄舟

リリース： 2017-10-05 15:32:02

オリジナル

2037 人が閲覧しました

この記事では主に、KD ツリーを通じて最も近い点を見つけるための C# を詳しく紹介します。興味のある方は参考にしてください。この記事では、まず Kd-Tree の構築方法を紹介し、次に検索プロセスを紹介します。 Kd-Tree のコード実装、そして最後に C# 言語を使用して私が実装した 2 次元 KD ツリーコードです。これは、私自身が初めて実装したツリー型のデータ構造でもあります。どうしても理解にズレが生じてしまいますので、修正をお願いいたします。

1. KD ツリーの概要

Kd ツリー (KD ツリー) は、K 次元ツリーとも呼ばれ、大規模な高精度の最近傍分析によく使用される高次元のインデックスツリーデータ構造です。 -次元データ空間最近傍検索を見つけて近似します。私が実装した KD ツリーは 2 次元の Kd ツリーです。目的は、点セット内で最も近い点を見つけることです。参考資料は Kd-Tree の Baidu Encyclopedia です。そしてコードは百度百科事典のロジックに従って整理されています。

2. KD ツリーの数学的説明

3. KD ツリーの構築方法

Kd ツリーを構築するために使用される 2 次元点集合を示します。三次元も同様です。

ツリー内の各ノードのデータ型:

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ツリー構築ロジックプロセス

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 ツリーの検索プロセス全体は、まず通常の検索に基づいて最も近い葉ノードを見つけます。ただし、この葉ノードは必ずしも最近接点であるとは限りません。次に、バックトラッキング操作を実行して、最も近い点を見つけます。

4.1 KDツリー探索ロジックプロセス

点集合に基づいて構築されたツリーtと探索点pに対して、ルートノードをノードtとして使用して次の操作を実行します

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);
  }
}

ログイン後にコピー

以上がKD ツリーによる最近点の検索の C# 分析例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。