jeudi 4 juin 2009

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

Aucun commentaire:

Enregistrer un commentaire