Exemple d'analyse C# de recherche du point le plus proche via l'arborescence KD

Cet article présente principalement C# pour trouver en détail le point le plus proche dans l'arbre KD. Il a une certaine valeur de référence. Les amis intéressés peuvent s'y référer

Cet article présente d'abord la méthode de construction, puis. présente le processus de recherche et l'implémentation du code de Kd-Tree, et donne enfin le code d'arborescence KD bidimensionnel que j'ai implémenté en utilisant le langage C#. C'est également la première structure de données arborescente que j'ai moi-même implémentée. Il y aura inévitablement des écarts de compréhension, alors corrigez-moi s'il vous plaît.

1. Introduction à l'arbre KD

Kd-Tree (arbre KD), c'est-à-dire un arbre à K dimensions, est un arbre d'index de haute dimension structure de données, souvent utilisée pour la recherche du voisin le plus proche et la recherche approximative du voisin le plus proche dans des espaces de données de grande dimension à grande échelle. L'arbre KD que j'ai implémenté est un arbre Kd bidimensionnel. Le but est de trouver le point le plus proche dans l’ensemble de points. Le matériel de référence est l’encyclopédie Baidu de Kd-Tree. Et le code est organisé selon la logique de l'Encyclopédie Baidu.

2. Explication mathématique de l'arbre KD

3. Méthode de construction de l'arbre KD

Ici, un ensemble de points bidimensionnels est utilisé pour construire un arbre Kd. Celui en trois dimensions est similaire.
Type de données de chaque nœud de l'arborescence :

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

Processus logique de construction d'arbre KD 3.1

• Tout convertir Mettez les points dans l'ensemble a

• Trouvez la variance xv pour les coordonnées X de tous les points de l'ensemble et trouvez la variance yv pour les coordonnées Y

• Si xv > yv, alors l'ensemble a est trié selon la coordonnée X. Si yv > xv, alors l'ensemble a est trié en fonction de la coordonnée y.

• Obtenir la médiane m de l'ensemble trié a. Utilisez ensuite m comme point d'arrêt et placez le point indexé par [0,m-2] dans l'ensemble a1. Mettez le point indexé par [m,a.count] dans l'ensemble de a2 (l'indice du point m est m-1).

• Construisez un nœud, la valeur du nœud est a[m-1], si le nombre de nœuds dans l'ensemble d'opérations est supérieur à 1, alors la paire de nœuds de gauche [0 , m-2] répète 2 à 5 étapes, le nœud droit répète les étapes 2 à 5 pour [m,a.count] sinon, le nœud est un nœud feuille.
  

3.2 Implémentation du code

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

Méthode de recherche dans l'arborescence KD

Le processus de recherche global de Kd-Tree trouve d'abord le nœud feuille le plus proche sur la base d'une recherche ordinaire. Mais ce nœud feuille n’est pas nécessairement le point le plus proche. Effectuez ensuite une opération de retour en arrière pour trouver le point le plus proche.

4.1 Processus logique de recherche d'arbre KD

• Pour l'arbre t construit en fonction de l'ensemble de points, et le point de recherche p Utilisez le nœud racine comme nœud t à. effectuer les opérations suivantes

• Si t est un nœud feuille. Obtenez ensuite la valeur du point de partage où la valeur du point n le plus proche est t, passez à l'étape 5 ; si t n'est pas un nœud feuille, passez à l'étape 3

• pour déterminer la méthode de division de t, Si la division est le long de l'axe des x, comparez la valeur x de p avec la valeur x du point de division du nœud. Sinon, comparez la coordonnée Y

• <.>Si la valeur de comparaison de p est inférieure à la valeur de comparaison de t, alors spécifiez t comme nœud enfant gauche de t. Sinon, spécifiez t comme nœud enfant droit de t, effectuez l'étape 2

• pour définir le point de récupération m et définissez m sur n

• calcul La distance d1 entre m et p, la distance d2 entre n et m.

• Si d1 >= d2 et qu'il y a un nœud parent, alors utilisez le nœud parent de m comme valeur de m et exécutez 5 étapes. S'il n'y a pas de nœud parent, obtenez le. point réel le plus proche TN ; Si d1 < d2 signifie que le point n n'est pas le point le plus proche, effectuez l'étape 8

• Si n a des nœuds frères, alors n = nœud frère de n ; n n'a pas de nœud frère, alors n = le nœud parent de n. Supprimez les n nœuds d’origine. Définissez la valeur de m sur le nouveau nœud n ; effectuez l’étape 6.

  
  

4.2 Implémentation du code

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!