Quadtree - partie 1

Je vais essayer d'écrire quelques articles concernant les arbres quaternaires (ou quadtree dans la langue de Shakespeare). Normalement, il ne sera pas nécessaire de posséder un grand niveau de programmation pour comprendre cette série. Tout d'abord, j'expliquerai le tout de manière assez simple, et progressivement je proposerais des idées dans le but d'améliorer cette structure.

Le type de donnée

Les données représentées doivent posséder les informations suivantes:

• deux nombres représentant un point de l'espace. Par soucis de facilité, nous nommerons "x" le nombre relatif à la première dimension et "y" celui relatif à la seconde dimension.
  

definition of Element{
x, y : Integer
}

Un noeud doit contenir les informations suivantes:

• quatre pointeurs vers les noeuds fils. La convention pour les nommer sera la suivante: on utilise deux lettres. La première pour spécifier si le noeud se trouve en haut (n) ou en bas (s), et la deuxième lettre pour indiquer s'il est à gauche (w) ou à droite (e). Ce qui donne: "ne", "nw", "se", "sw".
• un pointeur vers un élément que l'on nommera tout simplement "element"
• quatre nombre permettant de définir le domaine du noeud. Ces nombres consistent en la position du coin inférieur gauche ainsi que la largeur et la hauteur du noeud.
  

definition of Node{
ne, nw, se, sw : Node
x, y, w, h : Integer
element : Element
}

Voilà, c'est déjà tout pour les structures de données.

L'ajout d'un élément

L'ajout d'un élément est assez simple. Il suffit de regarder dans quel sous-arbre il faut ajouter l'élément et l'y ajouter. Voici un code dans un pseudo-langage:

procedure add( n : Node, e : Element){
centerX, centerY : Integer;
centerX = n.x + n.w / 2;
centerY = n.y + n.h / 2;
if( e.x > centerX){
 if( e.y > centerY){
   if( n.ne == null){
     create( n.ne);
     n.ne.element = e;
     n.ne.x = centerX;
     n.ne.y = centerY;
     n.ne.w = n.w / 2;
     n.ne.h = n.h / 2;
   }else{
     add( n.ne, e)
   }
 }else{
   if( n.se == null){
     create( n.se);
     n.se.element = e;
     n.se.x = centerX;
     n.se.y = n.y;
     n.se.w = n.w / 2;
     n.se.h = n.h / 2;
   }else{
     add( n.se, e)
   }
 }
} else {
 if( e.y > centerY){
   if( n.nw == null){
     create( n.nw);
     n.nw.element = e;
     n.nw.x = n.x;
     n.nw.y = centerY;
     n.nw.w = n.w / 2;
     n.nw.h = n.h / 2;
   }else{
     add( n.nw, e)
   }
 }else{
   if( n.sw == null){
     create( n.sw);
     n.sw.x = n.x;
     n.sw.y = n.y;
     n.sw.w = n.w / 2;
     n.sw.h = n.h / 2;
     n.sw.element = e;
   }else{
     add( n.sw, e)
   }
 }
}
}

Consultation d'un élément

Pour consulter un élément, la démarche à suivre est la suivante. Regarder si l'élément du noeud courant correspond aux indices donnés, sinon, aller voir dans le noeud approprié.

function lookup(n : Node, x : Integer, y : Integer) : Element {
centerX, centerY : Integer;
if( n.element.x == x && n.element.y == y ){
 lookup = n.element;
}else{
 centerX = n.x + n.w / 2;
 centerY = n.y + n.h / 2;
 if( x > centerX){
   if( y > centerY){
     if( n.ne != null){
       lookup = lookup( n.ne, x, y);
     }else {
       lookup = null;
     }
   } else{
     if( n.se != null){
       lookup = lookup( n.se, x, y);
     }else {
       lookup = null;
     }
   }
 } else{
   if( y > centerY){
     if( n.nw != null){
       lookup = lookup( n.nw, x, y);
     }else {
       lookup = null;
     }
   } else{
     if( n.sw != null){
       lookup = lookup( n.sw, x, y);
     }else {
       lookup = null;
     }
   }
 }
}
}

Supression d'un élément

Voilà, dernière étape avant d'obtenir une première version d'un arbre fonctionnel. Il faut principalement distinguer deux cas. Si l'élément est contenu dans une feuille, alors il suffit de supprimer celle-ci. Si l'élément n'est pas dans une feuille, il faut remplacer l'élément que l'on supprime par un élément contenu dans une feuille et ensuite supprimer la feuille.

Une question se pose naturellement: que se passe-t-il lorsque l'on veut supprimer la racine et que celle-ci n'a aucun fils? La solution proposée est la suivante: la fonction renvoie la valeur du noeud passé en paramètre. Si celui-ci n'est pas supprimé, alors il sera renvoyé, sinon, null est envoyé ce qui permettra à l'appelant de se mettre à jour.

function delete( n : Node, e : Element)  : Node{
t, d : Node;
a : Element;
delete = n;
if( n.element == e ) {
 if( n.ne == null && n.nw == null && n.se == null && n.sw == null){
   destroy( n);
   delete = null;
 }else {
   d = n;
   if( d.ne != null) {
     t = d.ne;
   } else if( d.se != null){
     t = d.se;
   } else if( d.nw != null){
     t = d.nw;
   } else {
     t = d.sw;
   }
   while( t != null){
     d = t;
     if( d.ne != null) {
       t = d.ne;
     } else if( d.se != null){
       t = d.se;
     } else if( d.nw != null){
       t = d.nw;
     } else if( d.sw != null){
       t = d.sw;
     } else {
       t = null;
     }
   }
   a = d.element;
   delete( t, a);
   n.element = a;
 }
}else{
 if( x > n.x + n.w / 2){
   if( y > n.y + n.h / 2){
     n.ne = delete( n.ne, e);
   } else{
     n.se = delete( n.se, e);
   }
 } else{
   if( y > n.y + n.h / 2){
     n.nw = delete( n.nw, e);
   } else{
     n.sw = delete( n.sw, e);
   }
 }
}
}

Voilà, le petit tour d'horizon est fini. Si vous avez des remarques ou questions, les commentaires sont là pour ça :-)

Prochaine étape: recherche d'éléments en fonction d'un domaine donné...