Discussion :

[outlawz94]

Bonjour, je dois faire un quadtree comme projet. Lorsque je fais l'inversion verticale et après plusieurs division, rien ne se passe à l'affichage, pourtant les coordonnées sont bien modifiées. Quelqu'un peut il m'aider ou me conseiller. Merci

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
void inverser(ARBRE *A)
{
	if((*A)->f1!=NULL)
	{
		inverser(&(*A)->f1);
		inverser(&(*A)->f2);
		inverser(&(*A)->f3);
		inverser(&(*A)->f4);
		change_coord_inversion(&(*A));
	}
}
 
void change_coord_inversion(ARBRE *A)
{
	int cote=(*A)->f1->P2.x-(*A)->f1->P1.x;
	if((*A)->f3->P1.y>(*A)->f1->P1.y)
	{
		(*A)->f1->P1.y+=cote;
		(*A)->f1->P2.y+=cote;
 
		(*A)->f3->P1.y-=cote;
		(*A)->f3->P2.y-=cote;
 
		(*A)->f2->P1.y+=cote;
		(*A)->f2->P2.y+=cote;
 
		(*A)->f4->P1.y-=cote;
		(*A)->f4->P2.y-=cote;
	}
	else
	{
		(*A)->f1->P1.y-=cote;
		(*A)->f1->P2.y-=cote;
 
		(*A)->f3->P1.y+=cote;
		(*A)->f3->P2.y+=cote;
 
		(*A)->f2->P1.y-=cote;
		(*A)->f2->P2.y-=cote;
 
		(*A)->f4->P1.y+=cote;
		(*A)->f4->P2.y+=cote;
	}
}

PS: A l'origine, f1 est en haut à gauche, f2 est en haut à droite, f3 est en bas à gauche, puis f4 en bas à droite.

[plxpy]

Salut

questions préliminaires indispensables : est-ce que le type ARBRE ou la structure NOEUD ont changé depuis ton dernier message ? La fonction init_arbre a-t-elle été modifiée ou pas ?

Et aussi (j'avais déja posé la question), dois-tu développer dans le cadre du projet un "gestionnaire" de Quadtree général et l'appliquer à ton découpage ou dois-tu seulement t'inspirer des Quadtree pour effectuer tes découpages ?

[plxpy]

les définitions de certains types ont été données dans cette discussion

• En laissant de côté pour le moment les détails de ton code C,
• en ne gardant que l'esprit de tes 2 fonctions,
• sans être sur de comprendre dans le détail ce que tu appelles inversion (ni quel est son intérêt)

j'ai bien l'impression qu'il y a, de toute façon, un problème dans ta façon de procéder.

C'est dû au fait que les coordonnées extrêmes (xmin,ymin,xmax,ymax) des zones couvertes par les noeuds de l'arbre sont fixées lors de leur création ou de la division du noeud père (ce sont les coordonnées des points P1 et P2). Ces coordonnées sont des coordonnées absolues mais, à la création, elles sont cohérentes : avant les "inversions", les fils sont spatialement localisés dans le père.


Quand tu commences à faire les inversions, c'est là que ça part en vrille : tu swappes les deux couples de fils (les gauches haut et bas, les droits haut et bas) qui, globalement, restent dans le père. Sauf qu'à l'étape suivante (attention, c'est du récursif et les changements se font en remontant dans l'arbre), le père change de place avec "un frère". Au final (sauf quelques cas particuliers, profondeur de 1), les noeuds pères ne contiennent pas, spatialement, leurs noeuds fils ... pour un Quadtree qui, dans ton cas, doit partitionner l'espace, ça coince.

Visuellement, sur un exemple minimaliste où on reconnaitra chacun des noeuds par une couleur de périmètre :



figure 1 : c'est la position de départ. La racine (noir) a été divisée et a 4 fils (jaune, gris, vert, rouge). Seul le fils jaune a été divisé (rose, bleu, violet et marron)

Première inversion sur f1 (jaune) qui (réursivité) lance les inversions sur les fils (feuilles de l'arbre : il ne se passe rien). Changement des coordonnées des dits-fils f1 et f3 (résultat figure 2 / inversion rose-violet) et f2 et f4 (résultat figure 3 - inversion bleu-marron).

L'inversion des fils de la racine f2 (gris), f3 (vert) et f4 (rouge) s'arrêtent de suite (ce sont des feuilles de l'arbre).

Vient alors le changement de coordonnées de f1 (jaune) et f3 (vert) : résultat à la figure 4 : cà y est ! Le noeud père JAUNE référence toujours (champs f1,f2,f3 et f4) ses fils violet, marron, rose et bleu mais ne les contient même plus.

Denier changement entre f2 et f4 de la racine : inversion gris-rouge et résultat final donné à la figure 5.



Et quand les divisions des noeuds sont plus poussées, ça part, encore un peu plus, dans tous les sens.

[outlawz94]

J'ai réussi à faire l'inversion finalement, en recalculant les coordonnées pour chaque nœuds et en échangeant les fils en mémoire. Merci .

[plxpy]

A moins que ce ne soit qu'une simple contrainte dans ton projet (une "figure imposée"), pourrais-tu m'éclairer sur l'intérêt de cette inversion ? Je ne vois pas du tout à quoi ça peut servir.