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

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.