Quadtree - partie 2

Dans cette partie, nous allons voir comment tirer parti de la structure d'un quadtree pour retrouver tout les éléments compris dans un domaine défini. Le temps nécessaire à cette opération sera proportionnel au nombre d'éléments trouvés.

Quelques éléments en guise d'introduction

Deux fonctions nous serons utiles pour la suite: savoir si deux domaines se chevauchent et savoir si un élément fait parti d'un domaine donné.

Commençons par le plus facile: savoir si un élément fait parti d'un domaine donné. Le code est très direct...

function isInside( e : Element, x : Integer, y : Integer,
       w : Integer, h : Integer) : Boolean {
 isInside = (e.x >= x && e.x < x + w) && (e.y >= y && e.y < y + h)
}

Ensuite, il faut tester l'intersection entre le domaine représenté par un noeud et un domaine donné. Ce test devra nous dire si l'intersection est vide ou non.

function overlap( n : Node, x : Integer, y : Integer,
       w : Integer, h : Integer) : Boolean {
 tx, ty, tw, th : Integer;
 tx = n.x; ty = n.y; tw = n.w; th = n.h;
 if( tx < x) {
   overlap = tx + tw >= x;
 }else {
   overlap = tx <= x + w
 }

 if( ty < y) {
   overlap = overlap && ty + th >= y;
 }else {
   overlap = overlap && ty <= y + h;
 }

}

On peut facilement voir qu'il est possible d'améliorer ce code en supprimant les instructions de choix et les remplacer par une seule commande. La fonction deviendrait dès lors la suivante.

function overlap( n : Node, x : Integer, y : Integer,
       w : Integer, h : Integer) : Boolean {
 tx, ty, tw, th : Integer;
 tx = n.x; ty = n.y; tw = n.w; th = n.h;
 overlap = ((tx < x && (tx + tw) >= x) ||
                  (tx >= x && (tx <= (x + w)) &&
                ((ty < y && (ty + th) >= y) ||
                  (ty >= y && (ty <= (y + h))))
}

Afin de retenir tout les éléments compris dans un domaine donné, il nous faut enregistrer les résultats dans une structure. Presque n'importe quelle structure peut convenir. Le choix fut porté sur la structure de pile. Pour que tout soit cohérent, voici quelques lignes de codes permettant d'utiliser une pile.

Lister les éléments d'un domaine

Cette fonction est selon moi la grande force des quadtree. En donnant un domaine particulier, retrouver tous les points qui s'y trouvent.

La façon de procéder est la suivante: on teste afin de savoir si l'élément contenu dans le noeud courant est contenu dans le domaine. Si oui, on l'ajoute à la liste des éléments contenus. Ensuite, pour chacun des noeuds fils, si leur domaine respectif intersecte celui donné alors on recherche parmi ce noeud aussi.
Ce qui nous donne la fonction suivante

procedure findElements( n : Node, x : Integer, y : Integer,
       w : Integer, h : Integer, s : Stack){
 if( isInside( n.element, x, y, w, h)){
   push( n.element, s);
 }
 if( n.se != null && overlap( n.se, x, y, w, h)){
   findElements( n.se, x, y, w, h, s);
 }
 if( n.ne != null && overlap( n.ne, x, y, w, h)){
   findElements( n.ne, x, y, w, h, s);
 }
 if( n.nw != null && overlap( n.nw, x, y, w, h)){
   findElements( n.nw, x, y, w, h, s);
 }
 if( n.sw != null && overlap( n.sw, x, y, w, h)){
   findElements( n.sw, x, y, w, h, s);
 }
}

Voilà, à nouveau rien de bien compliqué. Si vous avez des questions ou des remarques, les commentaires sont ouverts ;-)

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é...

Présentation

Bonjour tout le monde, un premier billet de présentations s'impose.
Tout d'abord, qui suis-je?
Étudiant à l'Université de Liège en Belgique, j'apprends l'art de la programmation. En informatique, différentes choses me plaisent. Tout d'abord c'est la résolution de problème. C'est assez jouissif de trouver une solution à un problème donné. Ensuite, pour être plus précis, les différents domaines que j'apprécie sont: les structures de données, l'intelligence artificielle et les jeux.
En dehors de ce domaine, j'ai quelques loisirs mais je ne pense pas qu'il soit nécessaire d'en parler ici. Et si à un moment ou un autre cela deviendrait important, alors ceux-ci seront exposé au moment opportun.

De quoi vais-je parler?
Je compte parler de choses et d'autres. L'écriture d'un blog est un nouvel exercice pour moi, on verra donc ou cela m'emmènera. Une chose est sûre: je m'amuse régulièrement à faire des petits programmes ou jeux. Vous en entendrez des nouvelles.