[Algo]Arbre[Résolu]

[Premium]

Salut,

j'aurai besoin d'aide pou créer un arbre sur le principe du quadtree.

L'algo que j'ai écrit ne fonctionne pas car mon image est chargée à chaque fois alors qu'elle ne devrait l'être qu'une fois et le code ne fait pas ce qu'il faut.

le code qui devrait créer l'arbre :

http://cjoint.com/data/lnoNvKVllB.htm

PS : je n'ai mis que la partie qui me pose problème

J'explique le principe :

Au départ, on a une image complete

+---------------+
|			   |
|			   |
|			   |
|	   T	   |
|			   |
|			   |
|			   |
+---------------+

Si élévation (point le plus haut - point le plus bas) > max, alors on découpes en 4.

+-------+-------+
|	   |	   |
|  NW   |   NE  |
|	   |	   |
+-------+-------+
|	   |	   |
|  SW   |   SE  |
|	   |	   |
+-------+-------+

On fait cela tant que la condition précédente est satisfaite pour toute les parties de l'image

Merci

[Sentinel]

Et quel est le problème exact ? Quelle est ta question ?

[Premium]

Et quel est le problème exact ? Quelle est ta question ?

Le problème que j'ai, c'est que mon image n'est pas découpé en différentes sections car l'image est rechargée à chaque appel de la fonction CreateQuadTree.

Ce qui fait que les valeur du min et du max sont toujours les mêmes.

Voici un exemple de ce que j'obtiens à la compilation :

http://cjoint.com/data/lnuPJPAgbI.htm

En principe, l'image entière doit se trouver à la racine et n'être chargée qu'une seule fois

Si élévation (point le plus haut - point le plus bas) > max, alors on découpes en 4, et on a ce dessin pour le premier découpage.

+-------+-------+
|	   |	   |
|  NW   |   NE  |
|	   |	   |
+-------+-------+
|	   |	   |
|  SW   |   SE  |
|	   |	   |
+-------+-------+

Ensuite on reprend chaque portion et on revérifie la condition précedente, jusqu'à ce que toute les portions de l'image donne élévation (point le plus haut - point le plus bas) < max.

Mon algo ne fait pas ceci ...

[lorinc]

bon, j'aurais fais ta fonction de création de cellule récursive (en pseudo code):

creer_cellule ( xmin, xmax, ymin, ymax, image)
{
 valeur_min = calcul de la valeur min dans image sur le carré défini par [xmin, ymin, xmax, ymax].
 valeur_max = calcul de la valeur max dans image sur le carré défini par [xmin, ymin, xmax, ymax].
 x_centre = calcul du centre du carré en x
 y_centre = calcul du centre du carré en y

 nouvelle cellule c;
 remplissage de c avec les corrdonées de c dans l'image, le centre, le min et max

 si (valeur_max - valeur_min) > seuil
c->NO = creer_cellule(xmin, x_centre, ymin, ycentre, image)
c->NE = creer_cellule(x_centre, xmax, ymin, ycentre, image)
c->SO = creer_cellule(xmin, xcentre, ycentre, ymax, image)
c->SE = creer_cellule(xcentre, xmax, ycentre, ymax, image)

 retourner c
}

et tu créés la première cellule en lui passant toute l'image : cree_cellule(0, image->w, 0, image->h, image)

voilà

[Premium]

Merci lorinc, pour l'algo.

A l'affichage de mon arbre, j'obtiens ceci :

xMin : 0.000000, yMin : 0.000000, xMax : 1024.000000, yMax : 1024.000000

Il n'y a que la racine qui a été crée

[lorinc]

rajoute un printf pour voir si tu fais bien les appels récursifs style

if(variations_fortes > tolerance){
 printf("création d'un sous-arbre\n");

et quand tu affiche, fais des tests sur les fils, sinon, ça risque de segfaulter :

if(c->NO != NULL) affiche(c->NO);

[Premium]

rajoute un printf pour voir si tu fais bien les appels récursifs style

if(variations_fortes > tolerance){
 printf("création d'un sous-arbre\n");

et quand tu affiche, fais des tests sur les fils, sinon, ça risque de segfaulter :

if(c->NO != NULL) affiche(c->NO);

J'ai rajouté le printf, mais il y n'y a que ça à l'excution

xMin : 0.000000, yMin : 0.000000, xMax : 1024.000000, yMax : 1024.000000

[lorinc]

ben fais des printf de variation_fortes et de tolerance, mais à mon avis, c'est là qu'est la boulette (mauvais calcul de variation, ou bien tolérance trop grande)

[Premium]

ben fais des printf de variation_fortes et de tolerance, mais à mon avis, c'est là qu'est la boulette (mauvais calcul de variation, ou bien tolérance trop grande)

Je suis bête

J'avais écrit :

variations_fortes = min-max;

au lieu de :

variations_fortes = max-min;

Normal que je n'entrais pas dans la boucle ...

J'obtiens cette affichage que je stoppe avec Ctrl-C

On voit que les variations ne changent jamais d'ou l'infinité de l'affichage ...

 ./a.out
variation_fortes : 183.000000
tolerance : 10.000000
creation d'un sous-arbre
variation_fortes : 183.000000
tolerance : 10.000000
creation d'un sous-arbre
variation_fortes : 183.000000
tolerance : 10.000000
creation d'un sous-arbre
variation_fortes : 183.000000
tolerance : 10.000000
creation d'un sous-arbre
variation_fortes : 183.000000
tolerance : 10.000000
creation d'un sous-arbre
variation_fortes : 183.000000
tolerance : 10.000000
creation d'un sous-arbre
variation_fortes : 183.000000
tolerance : 10.000000
creation d'un sous-arbre
variation_fortes : 183.000000
tolerance : 10.000000
creation d'un sous-arbre
variation_fortes : 183.000000
tolerance : 10.000000
creation d'un sous-arbre
variation_fortes : 183.000000
tolerance : 10.000000
creation d'un sous-arbre
variation_fortes : 183.000000
tolerance : 10.000000
creation d'un sous-arbre
variation_fortes : 183.000000
tolerance : 10.000000
creation d'un sous-arbre
variation_fortes : 183.000000
tolerance : 10.000000
creation d'un sous-arbre
variation_fortes : 183.000000
tolerance : 10.000000
creation d'un sous-arbre
variation_fortes : 183.000000
tolerance : 10.000000
creation d'un sous-arbre
etc

[lorinc]

c'est ton calcul de min/max qui est faux. Tu le fais sur toute l'image au lieu de le faire entre [xmin, ymin, xmax, ymax]

[Premium]

c'est ton calcul de min/max qui est faux. Tu le fais sur toute l'image au lieu de le faire entre [xmin, ymin, xmax, ymax]

Maitenant j'obtiens une erreur de segmentation ...

Ca m'affiche :

variation_fortes : 71.000000

tolerance : 10.000000

creation d'un sous-arbre

variation_fortes : 0.000000

tolerance : 10.000000

variation_fortes : 71.000000

tolerance : 10.000000

creation d'un sous-arbre

variation_fortes : 0.000000

tolerance : 10.000000

variation_fortes : 71.000000

tolerance : 10.000000

creation d'un sous-arbre

variation_fortes : 0.000000

tolerance : 10.000000

variation_fortes : 71.000000

tolerance : 10.000000

creation d'un sous-arbre

variation_fortes : 0.000000

...

Erreur de segmentation

[lorinc]

tes calculs de min/max ne sont toujours pas bons

la valeur d'un pixel en (x,y) c'est pixel[x*w + y] avec w la largeur de l'image

d'autre part, tu t'es emmelé dans tes NW, NE, SW, SE, si on suit ton code, ça fait un quad comme cela :

SW | SE

----------

NW | NE

[Premium]

J'ai fait les modifs mais j'obtiens toujours une erreur de segmentation mais il me semble que ça ne vient pas du calcul du min et du max mais de l'appel de mes différentes cellules.

Ce que j'obtiens à l'execution :

Debut du parsing
Parsing reussi
Debut chargement de l'image
Chargement de l'image reussi
Debut creation de l'arbre
Erreur de segmentation

J'obtiens ceci à l'execution :

http://cjoint.com/data/lplEmh4zcH.htm

On voit que certaines valeurs de xMin ne sont pas correcte car l'image a ses dimansions qui est un exposant de 2, et donc la valeur 384 ne peut pas être correcte.

Les valeurs des xMins ne sont pas décroissantes ...

On obtient aussi des valeurs négatives

[lorinc]

ce sont les calculs de tes centres qui sont faux. Le centre est défini comme suit :

x_center = x_min + (x_max - x_min)/2 = (x_min+x_max)/2

y_center = y_min + (y_max - y_min)/2 = (y_min+y_max)/2[\code]

[Premium]

ce sont les calculs de tes centres qui sont faux. Le centre est défini comme suit :

x_center = x_min + (x_max - x_min)/2 = (x_min+x_max)/2

y_center = y_min + (y_max - y_min)/2 = (y_min+y_max)/2

Merci bien

J'ai encore un souci mais cette fois au niveau de l'affichage

Ce que j'obtiens à l"execution :

http://cjoint.com/data/lpoCe6WimK.htm

Il y a des résultats faux comme par exemple cette ligne :

xMin : 0, yMin : 49, xMax : 23, yMax : 10

L'affichage de l'arbre est défini comme ceci:

void affichage(t_arbre arbre){
 if(arbre != NULL){
printf("xMin : %d, yMin : %d, xMax : %d, yMax : %d\n", arbre->xMin, arbre->yMin, 
   arbre->xMax, arbre->yMax);

if(arbre->NW != NULL) affichage(arbre->NW);
if(arbre->NE != NULL) affichage(arbre->NE);
if(arbre->SW != NULL) affichage(arbre->SW);
if(arbre->SE != NULL) affichage(arbre->SE);
 }

Qu'est-ce qui ne va pas

[lorinc]

l'exécution semble correct jusqu'à là :

Affichage de l'arbre :

xMin : 0, yMin : 0, xMax : 1024, yMax : 1024

xMin : 0, yMin : 0, xMax : 512, yMax : 512

xMin : 0, yMin : 0, xMax : 256, yMax : 256

xMin : 0, yMin : 0, xMax : 128, yMax : 128

xMin : 0, yMin : 0, xMax : 64, yMax : 64

xMin : 0, yMin : 0, xMax : 32, yMax : 32

xMin : 0, yMin : 0, xMax : 16, yMax : 16

xMin : 0, yMin : 0, xMax : 8, yMax : 8

xMin : 0, yMin : 0, xMax : 4, yMax : 4

xMin : 0, yMin : 0, xMax : 2, yMax : 2

xMin : 2, yMin : 0, xMax : 4, yMax : 2

le surplus qui est affiché vient du fait que tu n'initialise pas les sous-arbres NE,SW et SE à NULL alors que tu ne les crées pas encore, donc ils ne sont pas NULL, donc ils sont affichés... avec n'importe quelles valeurs, voire même des endroit en mémoire interdits ( et le segfault qui va avec)

[Premium]

l'exécution semble correct jusqu'à là :

Affichage de l'arbre :

xMin : 0, yMin : 0, xMax : 1024, yMax : 1024

xMin : 0, yMin : 0, xMax : 512, yMax : 512

xMin : 0, yMin : 0, xMax : 256, yMax : 256

xMin : 0, yMin : 0, xMax : 128, yMax : 128

xMin : 0, yMin : 0, xMax : 64, yMax : 64

xMin : 0, yMin : 0, xMax : 32, yMax : 32

xMin : 0, yMin : 0, xMax : 16, yMax : 16

xMin : 0, yMin : 0, xMax : 8, yMax : 8

xMin : 0, yMin : 0, xMax : 4, yMax : 4

xMin : 0, yMin : 0, xMax : 2, yMax : 2

xMin : 2, yMin : 0, xMax : 4, yMax : 2

le surplus qui est affiché vient du fait que tu n'initialise pas les sous-arbres NE,SW et SE à NULL alors que tu ne les crées pas encore, donc ils ne sont pas NULL, donc ils sont affichés... avec n'importe quelles valeurs, voire même des endroit en mémoire interdits ( et le segfault qui va avec)

Merci bien.

Ca fonctionne enfin sans seg fault

J'aurai maitenant besoin d'aide sur un autre problème qui concerne toujours les arbres

J'ai crée le quadtree a partir d'une image.

Il me faut réaliser une fonction qui construit un Vertex-Array qui stocke la géométrie du sol à partir des altitudes stockées dans les feuilles de l'arbre

Il me faut aussi parcourir cet arbre pour mémoriser les sommets (premier parcours) et pour définir les faces de mon maillage(2 ème parcours) qu'il faudra mettre dans des tableaux.

Si tu as des idées à me soumettre,(pseudo-code), ça m'aiderait beaucoup

Merci par avance

[lorinc]

là par contre, je ne peux pas vraiment faire le design de ton algo à ta place

tu devrais marquer le sujet en [résolu] dans le titre, et revenir en ouvrir un autre si tu as des difficultés sur la prochaine étape