Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 5 sur 5
  1. #1
    Invité de passage
    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
    Points : 3
    Points
    3

    Par défaut Problème quadtree inversion

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

  2. #2
    Modérateur
    Avatar de plxpy
    Homme Profil pro
    Ingénieur géographe
    Inscrit en
    janvier 2009
    Messages
    601
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Ingénieur géographe
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : janvier 2009
    Messages : 601
    Points : 965
    Points
    965

    Par défaut

    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 ?

  3. #3
    Modérateur
    Avatar de plxpy
    Homme Profil pro
    Ingénieur géographe
    Inscrit en
    janvier 2009
    Messages
    601
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Ingénieur géographe
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : janvier 2009
    Messages : 601
    Points : 965
    Points
    965

    Par défaut

    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.

  4. #4
    Invité de passage
    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
    Points : 3
    Points
    3

    Par défaut

    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 .

  5. #5
    Modérateur
    Avatar de plxpy
    Homme Profil pro
    Ingénieur géographe
    Inscrit en
    janvier 2009
    Messages
    601
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Ingénieur géographe
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : janvier 2009
    Messages : 601
    Points : 965
    Points
    965

    Par défaut

    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.

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

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •