IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C Discussion :

Quadtree fonction chute


Sujet :

C

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre averti
    Homme Profil pro
    Étudiant
    Inscrit en
    Décembre 2012
    Messages
    11
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Décembre 2012
    Messages : 11
    Par défaut 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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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:


    On obtient ça:


    A partir de ça:


    On obtient ça:


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

  2. #2
    Membre averti
    Homme Profil pro
    Étudiant
    Inscrit en
    Décembre 2012
    Messages
    11
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Décembre 2012
    Messages : 11
    Par défaut
    Je suis parti sur quelque chose comme ça:

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

  3. #3
    Membre éclairé Avatar de Ngork
    Homme Profil pro
    Barbare IT
    Inscrit en
    Avril 2009
    Messages
    160
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loire Atlantique (Pays de la Loire)

    Informations professionnelles :
    Activité : Barbare IT
    Secteur : Finance

    Informations forums :
    Inscription : Avril 2009
    Messages : 160
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 ...

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 8
    Dernier message: 12/02/2013, 01h08
  2. Fonction API
    Par margilb dans le forum C++Builder
    Réponses: 2
    Dernier message: 08/07/2002, 11h11
  3. Implémentation des fonctions mathématiques
    Par mat.M dans le forum Mathématiques
    Réponses: 9
    Dernier message: 17/06/2002, 16h19
  4. fonction printf
    Par ydeleage dans le forum C
    Réponses: 7
    Dernier message: 30/05/2002, 11h24
  5. FOnction api specifiant la position de la souris
    Par florent dans le forum C++Builder
    Réponses: 4
    Dernier message: 15/05/2002, 20h07

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo