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