Quadtree - partie 5

Un tout petit billet pour expliquer une petite modification possible relative aux quadtree dont les éléments sont contenus dans des feuilles. Plutôt que de contenir qu'un seul élément, une feuille pourrait contenir plusieurs éléments. Quel en serait l'avantage? Le plus évident est celui de la limitation de consommation de mémoire. En effet, si une feuille peut contenir N éléments, ce sont autant de feuilles qu'il ne faut pas créer.

Et comme souvent, il est également nécessaire de se poser la question: quel est le coût de ceci? Et bien, lors de la recherche, lorsque l'on arrive à une feuille, il faudra rechercher l'élément souhaité parmi N. Cette recherche peut être soit logarithmique (mais alors il faut maintenir le tableau trié), soit linéaire ( ce qui ne nécessite pas de garder le tableau trié lorsque l'on ajoute un élément). Toutes les opérations (consultation, ajout, suppression) s'en trouveront ralenties en fonction de N ce qui rend le choix de cette valeur assez crucial.

Quadtree - partie 4

Bon, pour ce billet, on va changer un peu les règles. Adieu la sauvegarde des éléments dans chacun des noeuds. On sauvegardera les éléments dans les feuilles. Quel est l'avantage me demanderez-vous? Et bien, cela dépend des applications. Si vous utilisez des langages assez modulaire, il y a moyen de créer deux structures de noeuds. La première sert la création l'arbre tandis que la seconde sert de feuille.
À quoi servirait la distinction? Simplement l'économie de mémoire. Et ce soucis d'économie n'est pas superflu. En effet, tous les noeuds servant à la création de l'arbre sont autant de données qui ne sont pas directement liée aux éléments.

Qu'est-ce que ça change? Et bien, un peu tout.

Retrait d'un élément

Le retrait est un peu plus compliqué que la version précédente. Nous devons nous assurer que si un noeud existe, il référence au minimum un élément, et s'il ne référence qu'un seul élément alors ce noeud ne possède pas de fils et il contient lui-même l'élément. Ensuite, si le noeud n'est pas une feuille et qu'il référence deux éléments, alors celui-ci deviendra une feuille lorsque l'on aura enlevé un des fils.
Dès lors, une question se pose. Comment connaitre le nombre de noeud référencés? Un parcours de l'arbre peut être effectué, mais ce n'est pas efficace. Une manière de connaitre ce nombre serait de maintenir un compteur dans chaque noeud. De ce fait, la structure deviendrait la suivante:

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

Un entier s est ajouté afin de retenir le nombre d'éléments référencés par ce noeud.

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

Pour ce code, on suppose que l'élément que l'on veut enlever existe bel et bien au sein de l'arbre.

Ajout d'un élément

Il y a plusieurs cas à distinguer. Soit le noeud courant est une feuille, alors il contient un élément. Soit ce n'est pas une feuille, alors on peut atteindre au moins deux éléments à partir de lui. Donc au moment d'ajouter un élément dans un noeud, il faut regarder si celui ci possède un fils.

procedure addElement( n: Node, e: Element){
  tmp : Element;
  centerX, centerY : Integer;
  n.s = n.s + 1;
  if( n.element == null){
    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;
         n.ne.s = 1;
       }else{
         addElement( 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;
         n.se.s = 1;
       }else{
         addElement( 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;
         n.nw.s = 1;
       }else{
         addElement( 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;
         n.sw.s = 1;
       }else{
         addElement( n.sw, e)
       }
     }
    }
  }else{
    tmp = n.element;
    n.element = null;
    addElement( n, tmp);
    addElement( n, e);
  }
}

Un petit mot d'explication lors d'ajout d'un élément dans une feuille. On peut facilement savoir si un noeud est une feuille. En effet, s'il l'est, alors il contient un élément. S'il n'en contient pas, c'est qu'il n'est pas une feuille.
Une fois que l'on sait qu'un élément est une feuille, il va falloir enlever l'élément de la feuille pour le mettre dans une nouvelle feuille, puis ajouter l'élément que l'on devait ajouter.

Recherche d'un élément

Il est assez facile d'effectuer la recherche d'un élément au sein d'un arbre quaternaire dont seules les feuilles contiennent des éléments. Le code parle de lui-même:

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

Quadtree - partie 3

Pour ce billet, une petite question: comment initialiser le noeud racine?

Soit on le définit comme représentant tout l'espace possible. Mais cela pose deux problèmes. Certains langages n'ont pas de limite sur la taille des nombre représentés, il n'y a pas donc pas moyen de borner l'espace possible. Le deuxième problème est plus vicieux. Supposons que les nombres entiers soient codés sur n bits. Il y a donc 2^n nombres différents. Généralement, le premier bit est utilisé pour le signe du chiffre. Ceci étant connu, quelle valeur doit-on mettre pour initialiser x, y, w, et h? Si l'on veut représenter tout l'espace w et h devraient valoir 2^n. Et il n'est pas toujours possible d'assigner une telle valeur à une variable.

Une autre solution est de spécifier un sous-domaine du domaine complet. Mais alors, que ce passe t'il lorsque l'on veut ajouter des éléments en dehors de ce sous-domaine?
Il existe une solution: agrandir l'arbre. L'idée est simple: avant d'ajouter un élément dans l'arbre, on regarde si le domaine représenté contient l'élément. Sinon, on crée un nouveau noeud A qui aura pour fils la racine de l'arbre. Et A devient donc la nouvelle racine.

Voici un petit extrait de code permettant de faire cette deuxième option.

function extend( r : Node, e : Element) : Node {
tmp : Node;
create( tmp);
tmp.w = r.w * 2;
tmp.h = r.h * 2;
if( e.x < r.x){
  if( e.y < r.y){
    tmp.ne = r;
  } else{
    tmp.se = r;
  }
} else{
  if( e.y < r.y){
    tmp.nw = r;
  } else{
    tmp.sw = r;
  }
}

Cependant, il faut faire attention: cela ne règle pas le problème de limitation des entiers. Et lorsque l'on augmente la taille de la nouvelle racine il se peut que l'on dépasse les limites pour les entiers...

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