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

この記事では主に、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ツリー構築ロジックプロセス

すべての点をセットaに入れる
セット内のすべての点のX座標の分散xvを計算する、Y 座標は分散 yv を求めます
xv > yv の場合、X 座標に従って集合 a を並べ替えます。 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 ～ 5 を繰り返します。 -2] の場合、右側のノードはペア [m,a.count] になります。それ以外の場合、ノードはリーフ ノードになります。

• 
  

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

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

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

tがaの場合葉のノード。次に、最も近い点 n の値が t である分割点の値を取得し、ステップ 5 に進みます。t が葉ノードでない場合は、ステップ 3 に進みます
。は x 軸に沿って分割されます。次に、p の x 値とノードの分割点の x 値を比較します。そうでない場合は、Y 座標を比較します。p の比較値が t の比較値より小さい場合、t が指定されます。 t の左の子ノードとして。それ以外の場合は、t を t の右側の子ノードとして指定し、手順 2
を実行して検索点 m を定義し、m を n
に設定し、m と p 間の距離 d1 と n 間の距離 d2 を計算します。そしてM。
d1 >= d2 で親ノードがある場合は、m の親ノードを m の値として使用し、親ノードがない場合は、d1 の場合に実際の最近接点 TN を取得します。 < 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);
    }
  }

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