Bonjour à tous, j'ai une petite question à vous poser, il s'agit plus d'une question de fond que d'une question technique sur le JAVA. J'ai un tp de programmation à rendre mais lors de la réalisation des méthodes je bloque sur l'une d'entre elles en particulier.
Je vous explique brièvement le tp :
On souhaite encoder des images en noir et blanc (pixel allumé ou non) dans un arbre binaire.
Toutes les images possèdent la même taille (256x256 pixels)
Pour ce faire on procède ainsi :
- Si l'image est entièrement noire alors la valeur de la racine est égale à 0 (pixels éteints) et c'est tout (pas d'autre noeuds).
- Si l'image est entièrement blanche alors la valeur de la racine est égale à 1 (pixels allumés) et c'est tout aussi.
- Si l'image est composée à la fois de pixels noirs et blanc alors la valeur de la racine est 2 (ambiguë) mais la construction de l'arbre continue, on va réitérer l'algorithme ci dessus sur les fils gauche et droit de l'arbre avec respectivement les sous images haute et basse dans un premier temps puis en alternant avec les sous images gauche et droites
Ainsi l'image crée est encodée grâce aux rectangles de même pixel qui composent l'image (gain de place)
Voici un exemple d'image avec son arbre associé
Je doit coder une fonction qui effectue une rotation de 90° à cette image mais je n'ai absolument aucune idée de la manière de modifier mon arbre pour y parvenir.
J'ai aussi comme condition de parcourir mon arbre via des iterator.
Mon iterator est placé sur un nœud de l'arbre, je peux le déplacer comme tel :
//Se déplace sur le fils gauche
Iterator.goLeft();
//Se déplace sur le fils droit
Iterator.goRight();
//Retourne au noeud parent
Iterator.goUp();
//Retourne à la racine de l'arbre
Iterator.goRoot();
Je peux acceder au type du noeud de l'itérateur et à sa valeur :
//Retourne un EnumType NodeType : NodeType.LEAF, NodeType.DOUBLE, NodeType.SENTINELLE
Iterator.NodeType();
//Retourne la valeur du noeud (0,1 ou 2)
Iterator.getValue().state
Je peux aussi ajouter un noeud et modifier un noeud comme tel :
//prérequis : Le noeud courant doit être du type NodeType.SENTINELLE (noeud vide = à null)
Iterator.addValue(Node n);
//Prérequis : Le noeud courant n'est pas du type NODETYPE.SENTINELLE
Iterator.set(Node n);
Pour un peu plus de clareté voici mon code d'affectation d'un arbre à un autre (l'équivalent de clone)
/**
* this devient identique à image2.
*
* @param image2
* image à copier
*
* @pre !image2.isEmpty()
*/
@Override
public void affect(AbstractImage image2) {
Iterator<Node> itA = this.iterator(); //Crée un nouvel itérateur à l'arbre et le place sur ROOT
Iterator<Node> itB = image2.iterator();
itA.clear(); //supprime toute les nodes sur l'iterator ainsi que ses fils
affectSub(itA, itB);
}
private void affectSub(Iterator<Node> itA, Iterator<Node> itB){
if(itB.nodeType() != NodeType.SENTINEL){
itA.addValue(Node.valueOf(itB.getValue().state));
itA.goLeft(); itB.goLeft();
affectSub(itA, itB);
itA.goUp(); itB.goUp();
itA.goRight(); itB.goRight();
affectSub(itA, itB);
itA.goUp(); itB.goUp();
}
}
Ca vous donne une idée d'un parcours d'arbre classique avec les ressources à ma disposition.
Voici le squelette de ma la fonction qui me pose problème
/**
* this devient rotation de image2 à 90 degrés dans le sens des aiguilles
* d'une montre.
*
* @param image2
* image pour rotation
* @pre !image2.isEmpty()
*/
@Override
public void rotate90(AbstractImage image2) {
}
AbstractImage est la classe mère de Image (que je suis en train de coder), il s'agit directement de l'arbre (Image ne fait pas référence à un arbre dans l'un de ses attributs)
Où se situe le patern de modification ? Comment je fait pour reconnaitre qu'un chunk de pixel en bas à gauche doit se retrouver en haut à gauche ? Et comment le différencier d'un autre pattern à un autre endroit de l'image ?
J'ai pensé à appliquer une matrice de rotation mais ma structure de donnée n'est pas une matrice de pixel, pareil pour une modification via la trigonométrie (genre (x, y) -> (-y, x+255))
J'ai une idée qui m'est venu et qui peut paraître idiote mais... En inversant les branches (droites devient gauche et inversement) et-ce-que ça marcherait ?
Sinon, si c'est autorisé, je pense qu'il faut obtenir une matrice à partir de l'arbre, appliquer une rotation sur cette matrice et enfin générer le nouvel arbre à partir de cette matrice. Autrement je vois mal comment procéder.
J'y ai pensé aussi mais je pense que ça effectuera plus une symétrie qu'une rotation (vue que chunk des gauche et en haut sont stocké dans les fils gauches et inversement pour les fils droits), ou alors s'il y a une double symétrie (horizontale et verticale) une rotation à 180° au final.
C'est pas vraiment précisé dans le sujet, je trouvais juste le code un peu lourd (conversion vers matrice -> transformation -> convertion vers arbre) et surtout pas pratique. Étant donné qu'on nous impose la structure de donnée je trouvais ça logique que l'on ne manipule qu'elle. Mais ne voyant pas d'autre solution je crois que c'est le moyen que je vais utiliser
- Edité par BlepBloupBlop 25 novembre 2017 à 15:06:56
Le Tout est souvent plus grand que la somme de ses parties.