KD TREES (3-D) Voisins les plus proches Rechercher

Question

Je regarde la page Wikipedia sur KD trees Voisins les plus proches Rechercher.

Le pseudo-code donné dans Wikipedia fonctionne lorsque les points sont en 2-D (x, y).

Je veux savoir, quels changements dois-je faire, lorsque les points sont 3-D (x, y, z). J'ai beaucoup googlé et j'ai même passé par des questions similaires lien dans le débordement de la pile, mais je n'ai pas trouvé la mise en œuvre en 3-d où, toute question précédente prend des points 2-D comme entrée, pas le 3-D points que je cherche.

Le pseudo-code Wiki pour la construction de l'arbre KD est ::

function kdtree (list of points pointList, int depth) 
{ 
    // Select axis based on depth so that axis cycles through all valid values 
    var int axis := depth mod k; 

    // Sort point list and choose median as pivot element 
    select median by axis from pointList; 

    // Create node and construct subtrees 
    var tree_node node; 
    node.location := median; 
    node.leftChild := kdtree(points in pointList before median, depth+1); 
    node.rightChild := kdtree(points in pointList after median, depth+1); 
    return node; 
} 

Comment trouver le plus proche voisin maintenant, après la construction du KD Les arbres?

Merci!

Answer 1

J'ai récemment codé un KDTree pour la recherche du plus proche voisin dans l'espace 3D et rencontré les mêmes problèmes de compréhension du NNS, particulièrement 3.2 du wiki.Je fini par utiliser cet algorithme qui semble fonctionner dans tous mes tests:

Voici la recherche de la feuille initiale:

public Collection<T> nearestNeighbourSearch(int K, T value) { 
    if (value==null) return null; 

    //Map used for results 
    TreeSet<KdNode> results = new TreeSet<KdNode>(new EuclideanComparator(value)); 

    //Find the closest leaf node 
    KdNode prev = null; 
    KdNode node = root; 
    while (node!=null) { 
     if (KdNode.compareTo(node.depth, node.k, node.id, value)<0) { 
      //Greater 
      prev = node; 
      node = node.greater; 
     } else { 
      //Lesser 
      prev = node; 
      node = node.lesser; 
     } 
    } 
    KdNode leaf = prev; 

    if (leaf!=null) { 
     //Used to not re-examine nodes 
     Set<KdNode> examined = new HashSet<KdNode>(); 

     //Go up the tree, looking for better solutions 
     node = leaf; 
     while (node!=null) { 
      //Search node 
      searchNode(value,node,K,results,examined); 
      node = node.parent; 
     } 
    } 

    //Load up the collection of the results 
    Collection<T> collection = new ArrayList<T>(K); 
    for (KdNode kdNode : results) { 
     collection.add((T)kdNode.id); 
    } 
    return collection; 
} 

Voici la recherche récursive qui commence au nœud feuille le plus proche:

private static final <T extends KdTree.XYZPoint> void searchNode(T value, KdNode node, int K, TreeSet<KdNode> results, Set<KdNode> examined) { 
    examined.add(node); 

    //Search node 
    KdNode lastNode = null; 
    Double lastDistance = Double.MAX_VALUE; 
    if (results.size()>0) { 
     lastNode = results.last(); 
     lastDistance = lastNode.id.euclideanDistance(value); 
    } 
    Double nodeDistance = node.id.euclideanDistance(value); 
    if (nodeDistance.compareTo(lastDistance)<0) { 
     if (results.size()==K && lastNode!=null) results.remove(lastNode); 
     results.add(node); 
    } else if (nodeDistance.equals(lastDistance)) { 
     results.add(node); 
    } else if (results.size()<K) { 
     results.add(node); 
    } 
    lastNode = results.last(); 
    lastDistance = lastNode.id.euclideanDistance(value); 

    int axis = node.depth % node.k; 
    KdNode lesser = node.lesser; 
    KdNode greater = node.greater; 

    //Search children branches, if axis aligned distance is less than current distance 
    if (lesser!=null && !examined.contains(lesser)) { 
     examined.add(lesser); 

     double nodePoint = Double.MIN_VALUE; 
     double valuePlusDistance = Double.MIN_VALUE; 
     if (axis==X_AXIS) { 
      nodePoint = node.id.x; 
      valuePlusDistance = value.x-lastDistance; 
     } else if (axis==Y_AXIS) { 
      nodePoint = node.id.y; 
      valuePlusDistance = value.y-lastDistance; 
     } else { 
      nodePoint = node.id.z; 
      valuePlusDistance = value.z-lastDistance; 
     } 
     boolean lineIntersectsCube = ((valuePlusDistance<=nodePoint)?true:false); 

     //Continue down lesser branch 
     if (lineIntersectsCube) searchNode(value,lesser,K,results,examined); 
    } 
    if (greater!=null && !examined.contains(greater)) { 
     examined.add(greater); 

     double nodePoint = Double.MIN_VALUE; 
     double valuePlusDistance = Double.MIN_VALUE; 
     if (axis==X_AXIS) { 
      nodePoint = node.id.x; 
      valuePlusDistance = value.x+lastDistance; 
     } else if (axis==Y_AXIS) { 
      nodePoint = node.id.y; 
      valuePlusDistance = value.y+lastDistance; 
     } else { 
      nodePoint = node.id.z; 
      valuePlusDistance = value.z+lastDistance; 
     } 
     boolean lineIntersectsCube = ((valuePlusDistance>=nodePoint)?true:false); 

     //Continue down greater branch 
     if (lineIntersectsCube) searchNode(value,greater,K,results,examined); 
    } 
} 

La source Java complète peut être trouvée here.

Answer 2

Vous trouvez le voisin le plus proche exactement comme décrit sur la page Wikipedia sous la rubrique "recherche du plus proche voisin". La description s'applique à n'importe quel nombre de dimensions. C'est-à-dire:

• Descendez l'arborescence de manière récursive depuis la racine, comme si vous étiez sur le point d'insérer le point dont vous recherchez le voisin le plus proche.
• Lorsque vous atteignez une feuille, notez-le comme meilleur-si loin.
• Sur le chemin de l'arbre à nouveau, pour chaque nœud que vous le rencontrez:
  • Si elle est plus proche que le meilleur si lointain, mettre à jour le meilleur si lointain.
  • Si la distance du meilleur si lointain au point cible est supérieure à la distance du point cible à l'hyperplan de division à ce noeud,
  processus
  • l'autre enfant du noeud trop (en utilisant la même récursivité) .

Answer 3

Je veux savoir, quels changements dois-je faire, lorsque les points sont 3-D (x, y, z).

Vous obtenez l'axe en cours sur cette ligne

var int axis := depth mod k; 

Maintenant, en fonction de l'axe, vous trouverez la médiane en comparant la propriété correspondante. Par exemple. Si axis = 0, vous comparez avec la propriété x. Une façon d'implémenter ceci est de passer une fonction de comparaison dans la routine qui fait la recherche.