Quadtree fonction chute

Version imprimable

03/02/2013, 11h52
outlawz94

Quadtree fonction chute
Bonjour, avant toute chose je tiens à dire que j'ai posté mon problème sur un autre site et je n'ai pas eu de réponse. Voici la structure d'un quadtree:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 typedef struct NOEUD* ARBRE; struct NOEUD{ POINT p1; POINT p2; COULEUR couleur; ARBRE f1,f2,f3,f4; }NOEUD;
Pour chaque noeud, p1 et p2 représentent graphiquement le point bas gauche et haut droit afin de tracer un rectangle. Le Rectangle d'origine se divise ,lorsqu'on clic, en 4 (4 fils) et un rectangle peut être noir ou blanc.

Voici quelques exemples de la fonction chute:

A partir de ça:
http://sdz-upload.s3.amazonaws.com/p...Capture311.PNG

On obtient ça:
http://sdz-upload.s3.amazonaws.com/p...Capture410.PNG

A partir de ça:
http://sdz-upload.s3.amazonaws.com/p.../Capture51.PNG

On obtient ça:
http://sdz-upload.s3.amazonaws.com/p.../Capture61.PNG

Je ne sais donc pas comment procéder. Pouvez vous m'aider s'il vous plait?
PS: Le "chutte" affiché a été modifié depuis. :)

Je suis parti sur quelque chose comme ça:

Code:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
void chute(ARBRE A)
{
	ARBRE racine=A;
	fonction(racine,A);
}
 
void fonction(ARBRE racine,ARBRE A)
{
	ARBRE vdd=NULL,tmp;
 
	if(A->f1!=NULL)
	{
		fonction(racine,A->f1);
		fonction(racine,A->f2);
		fonction(racine,A->f3);
		fonction(racine,A->f4);
	}
	else
	{
		vdd=v_d_d(racine,A,vdd);
 
		if(vdd!=NULL)
		{
			if(taille_arbre(vdd)<=taille_arbre(A))
			{
				if(vdd->couleur==noir)
				{
					tmp=A;
					A=vdd;
					vdd=tmp;
				}
			}
			else if(taille_arbre(vdd)>taille_arbre(A))
			{
				if(A->couleur==blanc)
				{
					tmp=vdd;
					vdd=A;
					A=tmp;
				}
			}
		}
	}
}
 
ARBRE v_d_d(ARBRE racine,ARBRE A,ARBRE vdd)
{
	if(racine->f1!=NULL)
	{
		vdd=v_d_d(racine->f1,A,vdd);
		vdd=v_d_d(racine->f2,A,vdd);
		vdd=v_d_d(racine->f3,A,vdd);
		vdd=v_d_d(racine->f4,A,vdd);
	}
	else if(racine->B_G.y==A->H_D.y)
	{
		if(distance(racine->B_G,racine->H_D)==distance(A->B_G,A->H_D))
		{
			vdd=racine;
		}
	}
 
	return vdd;
}

En cherchant à chaque fois le voisin du dessus de même surface puis en vérifiant si un échange est possible. B_G est le point bas gauche du rectangle et H_D le point haut droit. Hélas, aucun changement ne se produit et je suis un peu perdu :(

A mon avis, le problème est vraiment difficile si l'on reste dans la logique d'un arbre, donc, selon une méthode un peu lourde, je déconstruirais l'arbre, procèderais à mon opération de chute puis le reconstruirais.
Pour commencer, je rechercherais avec une fonction récursive (en première approche intuitive au moins, ensuite il faudra peut-être écrire une fonction plus performante) le niveau de maillage le plus fin, avec le code suivant par exemple (c'est le seul bout de code que je te propose, or il y a beaucoup beaucoup plus à coder - à commencer par une fonction max() - mais le but de l'opération n'est pas d'écrire le code complet à ta place ;)) :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 int maillage(ARBRE arbre) { int retour = 0; if (arbre != NULL) { retour = maillage(arbre->f1); retour = max(maillage(arbre->f2);retour); retour = max(maillage(arbre->f3);retour); retour = max(maillage(arbre->f4);retour); retour ++; } return retour; }
Puis je transformerais l'arbre en une matrice de points de dimension 2 puissance (n-1), n étant la valeur retournée par la recherche du maillage le plus fin.
Je compterais ensuite dans cette matrice le nombre de "points" noirs par colonne et recréerais la colonne avec les "points" noirs en bas.
Enfin, je convertirais la nouvelle matrice obtenue en un nouvel arbre.

Bon, il y a sans doute un meilleur algorithme (plus propre et/ou plus rapide), mais celui-ci me semble le plus facile à mettre en oeuvre ... :ccool: