C#-Beispielanalyse der Suche nach dem nächstgelegenen Punkt über den KD-Baum

Dieser Artikel stellt hauptsächlich C# vor, um den nächstgelegenen Punkt über den KD-Baum zu finden. Er hat einen gewissen Referenzwert.

Dieser Artikel stellt zunächst die Konstruktionsmethode von Kd-Tree vor stellt den Suchprozess und die Code-Implementierung von Kd-Tree vor und gibt schließlich den zweidimensionalen KD-Baumcode an, den ich mit der Sprache C# implementiert habe. Dies ist auch die erste baumförmige Datenstruktur, die ich selbst implementiert habe. Es wird zwangsläufig zu Abweichungen im Verständnis kommen, also korrigieren Sie mich bitte.

1. Einführung in den KD-Baum

Kd-Baum (KD-Baum), also K-dimensionaler Baum, ist ein hochdimensionaler Indexbaum Datenstruktur, wird häufig für die Suche nach nächsten Nachbarn und die Suche nach ungefähren nächsten Nachbarn in großen hochdimensionalen Datenräumen verwendet. Der von mir implementierte KD-Baum ist ein zweidimensionaler Kd-Baum. Der Zweck besteht darin, den nächstgelegenen Punkt in der Punktmenge zu finden. Das Referenzmaterial ist die Baidu-Enzyklopädie von Kd-Tree. Und der Code ist nach der Logik der Baidu-Enzyklopädie organisiert.

Mathematische Erklärung des KD-Baums

3. Konstruktionsmethode des KD-Baums

Hier wird eine zweidimensionale Punktmenge verwendet, um einen Kd-Baum zu erstellen. Das dreidimensionale ist ähnlich.
Datentyp jedes Knotens im Baum:

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 Logischer Prozess der KD-Baumkonstruktion

• Alle konvertieren Platzieren Sie die Punkte in Satz a

• Ermitteln Sie die Varianz xv für die X-Koordinaten aller Punkte im Satz und ermitteln Sie die Varianz yv für die Y-Koordinaten

• Wenn xv > yv, dann wird die Menge a nach der X-Koordinate sortiert. Wenn yv > xv, dann wird die Menge a nach der y-Koordinate sortiert.

• Ermitteln Sie den Median m der sortierten Menge a. Verwenden Sie dann m als Haltepunkt und fügen Sie den durch [0, m-2] indizierten Punkt in die a1-Menge ein. Fügen Sie den durch [m,a.count] indizierten Punkt in die Menge von a2 ein (der Index von Punkt m ist m-1).

• Konstruieren Sie einen Knoten, der Wert des Knotens ist a[m-1], wenn die Anzahl der Knoten im Operationssatz größer als 1 ist, dann ist das linke Knotenpaar [0 , m-2] wiederholt 2–5 Schritte, der rechte Knoten wiederholt die Schritte 2–5 für [m,a.count]; andernfalls ist der Knoten ein Blattknoten.
  

3.2 Code-Implementierung

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-Baumsuchmethode

Der gesamte Suchprozess von Kd-Tree findet zunächst einen nächstgelegenen Blattknoten basierend auf der normalen Suche. Dieser Blattknoten ist jedoch nicht unbedingt der nächstgelegene Punkt. Führen Sie dann einen Backtracking-Vorgang durch, um den nächstgelegenen Punkt zu finden.

4.1 KD-Baum-Suchlogikprozess

• Für den Baum t, der auf der Punktmenge und dem Suchpunkt p basiert, wird der Wurzelknoten als Knoten t verwendet Führen Sie die folgenden Operationen aus

• Wenn t ein Blattknoten ist. Ermitteln Sie dann den Wert des Teilungspunkts, bei dem der Wert des nächstgelegenen Punkts t ist, und fahren Sie mit Schritt 5 fort. Wenn t kein Blattknoten ist, fahren Sie mit Schritt 3 fort

• , um dies zu bestimmen die Aufteilungsmethode von t. Wenn die Aufteilung entlang der x-Achse erfolgt, vergleichen Sie den x-Wert von p mit dem x-Wert des Aufteilungspunkts des Knotens. Andernfalls vergleichen Sie die Y-Koordinate

• Wenn der Vergleichswert von p kleiner ist als der Vergleichswert von t, wird t als linker untergeordneter Knoten von t bezeichnet. Andernfalls geben Sie t als rechten untergeordneten Knoten von t an, führen Sie Schritt 2

• aus, um den Abrufpunkt m zu definieren, und setzen Sie m auf n

• Berechnung Der Abstand d1 zwischen m und p, der Abstand d2 zwischen n und m.

• Wenn d1 >= d2 und es einen übergeordneten Knoten gibt, dann verwenden Sie den übergeordneten Knoten von m als Wert von m und führen Sie 5 Schritte aus. Wenn es keinen übergeordneten Knoten gibt, erhalten Sie den realer nächstgelegener Punkt TN; Wenn d1 < d2 bedeutet, dass Punkt n nicht der nächstgelegene Punkt ist, führen Sie Schritt 8 aus.

• Wenn n Geschwisterknoten hat, dann ist n = Geschwisterknoten von n; n hat keinen Geschwisterknoten, dann ist n = der Elternknoten von n. Löschen Sie die ursprünglichen n Knoten. Legen Sie den Wert von m auf den neuen n-Knoten fest. Führen Sie Schritt 6 aus.
  

4.2 Code-Implementierung

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

Das obige ist der detaillierte Inhalt vonC#-Beispielanalyse der Suche nach dem nächstgelegenen Punkt über den KD-Baum. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!