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