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

Langage Delphi Discussion :

Algorithme particulier


Sujet :

Langage Delphi

  1. #1
    esa
    esa est déconnecté
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Octobre 2003
    Messages
    61
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2003
    Messages : 61
    Points : 38
    Points
    38
    Par défaut Algorithme particulier
    Bonjour,
    je me casse un peu le nez sur cet algo. Si l'un d'entre vous a déjà eu ce problème et l'a résolu, peut-il m'aider.

    J'ai une liste d'objets non ordonnée.
    Chaque objet a un TRect permettant de stocker le Top et le Bottom qui servent à définir la plage verticale.

    Le but est de répartir tous les objets (ou boites) dans une colonne de largeur fixe en recalculant, lors de l'affichage, le Left et le Right de chacun pour donner le shéma ci-dessous :



    Attention, il y a des cas assez complexes lorsque, par exemple, Box1 finit apres le début de Box3, Box2 doit prendre la bonne largeur car Box1 va avoir une largeur plus petite ; etc...

    A vos claviers et surtout merci d'avance !!!

  2. #2
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2002
    Messages
    3 434
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Mai 2002
    Messages : 3 434
    Points : 5 846
    Points
    5 846
    Par défaut
    salut

    quelle sont les contrainte exact
    les dimmension de tes boites sont elle fixe
    si oui c'est pas bien compliquer

    sinon ca ne l'est pas plus

    en fait le left est determiner si le top de la boite est en intersection avec une autres

    a priorie il faudra que tu creer un tableau a deux dimension si tu n'as pas trops d'element sinon tu creer
    un arbre
    tu fait donc une premiere boucle dans lequel tu definie
    les element afin de savoir si il se trouve sur la meme branche ou non

    ensuite il suffit de recalculer la taille par le nombre d'element de la branche

    aurait des donnée de test pour verifier

    @+ Phil

    peut tu nous donner des donner de test

  3. #3
    esa
    esa est déconnecté
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Octobre 2003
    Messages
    61
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2003
    Messages : 61
    Points : 38
    Points
    38
    Par défaut
    Citation Envoyé par anapurna
    quelle sont les contrainte exact
    les dimmension de tes boites sont elle fixe
    si oui c'est pas bien compliquer
    Il n'y a que le Top et le Bottom qui sont fixes lors des affichages.
    Le Left et le Right dépendent de la largeur que la boite peut occuper.

    Citation Envoyé par anapurna
    a priorie il faudra que tu creer un tableau a deux dimension si tu n'as pas trops d'element sinon tu creer
    un arbre
    tu fait donc une premiere boucle dans lequel tu definie
    les element afin de savoir si il se trouve sur la meme branche ou non

    ensuite il suffit de recalculer la taille par le nombre d'element de la branche
    Mais admettons que :
    - Box1 touche Box2
    - Box1 touche Box3 qui touche Box4

    Box1 doit prendre 1/3 de largeur
    Box3 doit prendre 1/3 de largeur
    Box4 doit prendre 1/3 de largeur
    MAIS
    Box2 doit prendre 2/3 de largeur et non pas 1/2.
    Pourtant Box2 ne touche que Box1.

    Citation Envoyé par anapurna
    peut tu nous donner des donner de test
    Box1.area.Top = 10
    Box1.area.Bottom = 140

    Box2.area.Top = 20
    Box2.area.Bottom = 70

    Box3.area.Top = 90
    Box3.area.Bottom = 150

    Box4.area.Top = 120
    Box4.area.Bottom = 160

    (ne correspondent pas au shéma du post précédent)

  4. #4
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2002
    Messages
    3 434
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Mai 2002
    Messages : 3 434
    Points : 5 846
    Points
    5 846
    Par défaut
    salut


    Box2 doit prendre 2/3 de largeur et non pas 1/2.
    Pourtant Box2 ne touche que Box1.
    Pourquoi 2/3 ?
    si je comprend bien
    il faut trouver le plus petit diviseur commun
    l'appliquer a chacune des boite sauf a la boite de fin de branche.
    celle-ci devras etre completer jusqu'a atteindre le bord de fin

    ... prenons un autre exemple alors
    si sur une branche j'ai 4 boites
    et sur la deuxieme j'ai 2 boites

    je divise donc la colonne par 4 donc chaque boite fait 1/4
    sauf la derniere qui fera 3/4

    @+ Phil

  5. #5
    esa
    esa est déconnecté
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Octobre 2003
    Messages
    61
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2003
    Messages : 61
    Points : 38
    Points
    38
    Par défaut
    Pas vraiment, car chaque boite doit prendre la largeur maximale, et c'est pas forcement la derniere qui prend la largeur max.

    Sur le schema suivant, ma Box1 (en jaune) s'affiche mal car mon algo est nase.

    il faudrait Box5, Box4, Box1 et Box2 à 1/4 et Box3 à 1/2.

    En fait, voici où j'en suis :
    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
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    procedure TKGridColumn.Calc;
    begin
      DispatchRAZ(Self);
      DispatchCalcRank(Self);
      DispatchCalcTotal(Self);
    end;
     
    // RAZ
    procedure TKGridColumn.DispatchRAZ(Contener: TWinControl);
    var
      Box: TKGridBox;
    begin
      Box := GetTopBoxOf(Contener);  // retourner la 1ere boite (la plus haute)
      while Box <> nil do
      begin
        Box.DispatchRank := 0;   // Numéro de rangée
        Box.DispatchTotal := 1;  // Nombre de boites concernées (boite en cours incluse)
        Box := GetNextBoxOf(Contener, Box);  // retourner la boite suivante
      end;
    end;
     
    // Définir la rangée de chaque boite :
    // Mettre à gauche toutes celles qui le peuvent
    // ensuite, augmenter le rank des autres
    // etc...
    procedure TKGridColumn.DispatchCalcRank(Contener: TWinControl);
    var
      Box, StartBox: TKGridBox;
      Rank, vBottom: Integer;
      CestFini: Boolean;
    begin
      Rank := 0;
      repeat
        Inc(Rank); // C'est la rangée d'affichage
        // Touver la 1ere boite non traitée
        StartBox := nil;
        Box := GetTopBoxOf(Contener);
        while Box <> nil do
        begin
          if Box.DispatchRank = 0 then
          begin
            StartBox := Box;
            Break;
          end;
          Box := GetNextBoxOf(Contener, Box);
        end;
        Box := StartBox;
        // J'ai une boite non traitée
        if Box <> nil then
        begin
          Box.DispatchRank := Rank;
          vBottom := Box.Area.Bottom;
          // BOX SUIVANTES
          Box := GetNextBoxOf(Contener, Box);
          while Box <> nil do
          begin
            if (Box.DispatchRank = 0) and (Box.Area.Top > vBottom) then // On ne touche pas le boite précédente dans le Rank en cours
            begin
              Box.DispatchRank := Rank;  // Affecter la rangée à cette boite
              vBottom := Box.Area.Bottom;
            end;
            Box := GetNextBoxOf(Contener, Box);
          end;
        end;
        // Vérifier s'il en reste à traiter
        CestFini := True;
        Box := GetTopBoxOf(Contener);
        while Box <> nil do
        begin
          if Box.DispatchRank = 0 then
          begin
            CestFini := False;
            Break;
          end;
          Box := GetNextBoxOf(Contener, Box);
        end;
      until CestFini;
    end;
     
    // Affecter a chaque boite le nombre de boites cotes a cotes
    // pour en déduire la largeur lors de l'affichage
    procedure TKGridColumn.DispatchCalcTotal(Contener: TWinControl);
    var
      i: Integer;
      Box, BoxSide: TKGridBox;
      RankList: TStringList;
      function InRankList(Value: string): Boolean;
      begin
        Result := RankList.IndexOf(Value) > -1;
      end;
    begin
      RankList := TStringList.Create; // Liste des ranks utilisés
      try
        Box := GetTopBoxOf(Contener);  // 1ere boite en partant du haut
        while Box <> nil do
        begin
          RankList.Clear;
          RankList.AddObject(IntToStr(Box.DispatchRank), Box);
          BoxSide := GetTopBoxOf(Contener);
          while BoxSide <> nil do
          begin
            if BoxSide <> Box then
            begin
              if not InRankList(IntToStr(BoxSide.DispatchRank)) then
              begin
                // vérifier si 2 boites se chevauchent
                if not ((Box.Area.Bottom < BoxSide.Area.Top) or (Box.Area.Top > BoxSide.Area.Bottom)) then
                begin
                  RankList.AddObject(IntToStr(BoxSide.DispatchRank), BoxSide);
                end;
              end;
            end;
            BoxSide := GetNextBoxOf(Contener, BoxSide);
          end;
          for i := 0 to RankList.Count -1 do
          begin        
            BoxSide := RankList.Objects[i] as TKGridBox;
            BoxSide.DispatchTotal := RankList.Count;
          end;
          Box := GetNextBoxOf(Contener, Box);
        end;
      finally
        RankList.Clear;
        FreeAndNil(RankList);
      end;
    end;
    Et lors de l'affichage, je les place en fonction du DispatchRank et du DispatchTotal.
    Mais toute la méthode est à revoir, je m'y prends mal pour traiter tous les cas.

  6. #6
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2002
    Messages
    3 434
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Mai 2002
    Messages : 3 434
    Points : 5 846
    Points
    5 846
    Par défaut
    salut ,

    bon a premiere vu il faut vraiment que tu utilise un arbre

    Regarde ce tuto :
    http://recursivite.developpez.com/?page=page_8#LVII-A

    j'ai pas trop le temps de regarder en profondeur mais
    la premiere operation que je ferait est un trie sur le Top
    une fois ta liste triée il faut que tu la range avec le top
    en condition devant ce trouver entre le Top et le bottom du precedent

    dans le dernier exemple que tu donne on voit que deux box peuvent etre juste derriere une meme boite
    c'est la ou l'arbre est interessant

    il ne te reste plus qu'a trouver le nombre maxi d'element par branche (nbmaxelem)

    ensuite il te suffit de divise la largeur du conteneur par le nombre trouver avant
    largeurElem= LarGeurContenr/nbmaxelem
    en sachant que le dernier element si il n'est pas pres du bord doit etre redimensionner
    si dernierelemBranche alors
    CurentLargeur = (nbmaxelem-poselem) *largeurElem
    sinom
    CurentLargeur = largeurElem
    @+ Phil

  7. #7
    esa
    esa est déconnecté
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Octobre 2003
    Messages
    61
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2003
    Messages : 61
    Points : 38
    Points
    38
    Par défaut
    Je comprends bien, mais dans mon cas, une boite peut avoir 2 peres.

    Je vais continuer de chercher de mon coté en partant sur des chaines de boites distinctes et calculer la largeur minimale de chaque boite sachant qu'elle peut appartenir a plusieurs chaines.

    Bref, c'est pas gagné

  8. #8
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2002
    Messages
    3 434
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Mai 2002
    Messages : 3 434
    Points : 5 846
    Points
    5 846
    Par défaut
    salut

    connait tu la position des tes elements
    je veut dire peut tu attribuer un indice de ligne et de colonne ?
    un peu comme ci tu les avait placer dans un tableau a double entrée

    exemple :
    [B5(0,0) ][B4(0,1) ][B1(0,2)][B2(0,3)]
    [ ][ ][B3(1,2)][ ]

    => maxelem = 4
    si c'est le cas il te suffit de parcourir la liste
    pour la premiere colonne
    largeurCol := LargeurTotal/maxelem;

    le (left =0;rigth=largeurCol*maxelem)
    ensuite pour les elment suivant
    le left = (indicecol*largeurCol)
    rigth= (maxelem)*largeurCol
    // en fait par defaut on donne la largeur maxi

    l'astuce ce trouve la il te suffit de redefinir
    l'element precedent, son right etant egale au left du suivant je precise que ce n'est valable que pour les indice d'une meme ligne

    l'exemple que tu donne avec la boite jaune ne te posera pas de probleme puique la boite 3 ne fait pas partie de la premier ligne mais d'une seconde ligne
    si tu avait une autre boite dont le top est inferieur donc elle devrait ce trouver a la colonne zero mais a la 3 ligne
    reprenon l'exemple precedent

    [B5(0,0) ][B4(0,1) ][B1(0,2)][B2(0,3)]
    [ ][ ][B3(1,2)][ ]
    [B6(2,0)][][][]
    Bon je sais pas is j'ai etait clair

    mais a priorie si tu arrive a les indicé y'a pas de soucis par la suite

    de plus

    il existe une fonction qui determine si il y a intersection entre deux rectangle dans delphi
    result := intersectrect(Collisionr,rect1,rect2);
    il te suffit d'affecter un left un un right par defaut et de faire le test


    @+ Phil

  9. #9
    esa
    esa est déconnecté
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Octobre 2003
    Messages
    61
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2003
    Messages : 61
    Points : 38
    Points
    38
    Par défaut
    Citation Envoyé par anapurna
    connait tu la position des tes elements
    je veut dire peut tu attribuer un indice de ligne et de colonne ?
    un peu comme ci tu les avait placer dans un tableau a double entrée
    Ben non justement. Je peux décréter que les plus a gauche sont de colonne 1 et incrémenter cet indice pour celles qui les touchent, etc... Mais il faudrait revenir sur toutes les boites précédentes de façon récurcive pour décaler encore cet indice dans le cas ou je tombe sur un nombre supérieur de boites cotes à cotes, etc...
    En plus, une boite peut être dans plusieurs chaines de boites.

    Citation Envoyé par anapurna
    il existe une fonction qui determine si il y a intersection entre deux rectangle dans delphi
    result := intersectrect(Collisionr,rect1,rect2);
    il te suffit d'affecter un left un un right par defaut et de faire le test
    Merci, c'est vrai que je n'ai même pas cherché ce genre de fonction (honte à moi )

    Je suis en congès et je m'y repencherai au retour pour trouver une solution complète. A moins que quelqu'un ne l'ait déjà sous le coude...

  10. #10
    Membre éclairé Avatar de slimjoe
    Homme Profil pro
    Inscrit en
    Juin 2005
    Messages
    647
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : Canada

    Informations forums :
    Inscription : Juin 2005
    Messages : 647
    Points : 789
    Points
    789
    Par défaut
    Salut!

    J'ai eu à faire un algo semblable il y a quelque temps. Et comme la largeur totale de l'espace disponible était variable, j'ai décidé de travailler avec des ratios. Alors pour être clair, sache que lorsque je parlerai de ratio, il s'agira du pourcentage de largeur de l'espace disponible dans lequel tu placera tes rectangles.

    J'y vais de mémoire alors j'espère ne rien oublier.


    Première étape : mettre les rectangles dans un tableau à 2 dimentions.
    Prend le rectangle dont le top est le plus petit et place le dans la première colonne, première ligne du tableau.

    Parcours les autres formes et cherche celui dont le top est le plus petit MAIS plus grand que le bottom de celui que tu as placé. Si tu n'en trouves pas, ajoute une colonne à ton tableau et recommence du début jusqu'à ce que toutes les formes soient en place.

    En gros, ce que tu cherches à faire, c'est de mettre tes rectangles en ordre de Top en t'assurant que jamais il n'y ait de collision dans une même colonne.

    Une fois ton tableau rempli, tu sauras le nombres de colonnes à afficher et ça va te permettre de calculer le ratio de largeur et de position de chaque rectangle.


    Deuxième étape : trouver le ratio de position des rectangles.
    Le ratio de position, c'est la position de Left en pourcentage de largeur de l'espace disponible. Par exemple, un ratio de .5 indique que le Left du rectangle est horizontalement en plein milieu de l'espace disponible.

    Pour le trouver, c'est facile. On prend l'indice "colonne" du tableau, qu'on divise par le nombre de colonnes total.

    Exemple #1: dans un tableau de 4 colonnes, les rectangles dans la 2e colonne (donc indice 1) auront un ratio de position de .25 parce que 1 / 4 = .25 (le Left de ces rectangles seront positionnés au quart de l'espace disponible).

    Exemple #2: dans un tableau de 4 colonnes, les rectangles dans la 1ère colonne (donc indice 0) auront un ratio de 0 parce que 0 / 4 = 0 ce qui veut dire qu'ils seront positionnés tout à fait à gauche de l'espace disponible.


    Troisième étape : trouver le ratio de largeur des rectangles.

    Le ratio de largeur est le pourcentage de l'espace disponible qu'occupera le rectangle en largeur. Par exemple, un ratio de .5 de largeur indique que le rectangle occupe 50% de l'espace disponible. Aussi, si ce même rectangle a un ratio de position de .5, on peut dire que son Left est au centre et qu'il occupe la moitié droite de l'espace disponible.

    Pour trouver le ratio de largeur il faut, pour chaque rectangle, chercher celui dans les colonnes suivantes qui entre en collision avec ce dernier (en d'autre mot, on cherche dans quelle colonne se trouve le premier rectangle à droite avec lequel on a une collision). Dès qu'on le trouve, on sait dans quelle colonne il se trouve et on peut calculer le ratio de largeur. Tu n'as qu'à soustraire le ratio de position du rectangle trouvé à droite par celui du rectangle pour lequel on cherche sa largeur.

    Exemple #1 : dans un tableau de 4 colonnes, si tu cherches le ratio d'un rectangle dans la 1ère colonne (ratio de position de 0) et que le premier à sa droite est dans la 2e colonne (ratio de position de .25), tu sais que le ratio de largeur de ton rectangle est de .25.

    Exemple #2 : dans un tableau de 4 colonnes, si tu cherches le ratio d'un rectangle dans la 1ère colonne (ratio de position de 0) et que le premier à sa droite est dans la 3e colonne (ratio de position de .50), tu sais que le ratio de largeur de ton rectangle est de .50. Ce rectangle prendra en réalité la largeur de 2 colonnes.


    Quatrième étape : placer tes rectangles.

    Le Top et le Bottom sont facile à retrouver (on y a pas touché ). Le Left, c'est le ratio de position multiplié par la largeur totale de l'espace disponible. Le Right c'est le Left plus le ratio de largeur multiplié par la largeur totale de l'espace disponible.

    Exemple:
    Largeur totale --> T
    Ratio de position --> P
    Ratio de largeur --> L

    Left := T * P;
    Right := Left + (T * L)
    C'est compliqué, je le sais. Et je sais aussi qu'il y a probablement un algo beaucoup plus performant que celui-ci mais bon... c'est gratuit Aussi, je suis désolé de ne pas être en mesure de te donner d'exemple de code. Je n'en ai pas sous la main

    Bon dev!

    -Slimjoe

  11. #11
    esa
    esa est déconnecté
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Octobre 2003
    Messages
    61
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2003
    Messages : 61
    Points : 38
    Points
    38
    Par défaut
    Oui, merci. C'est dans l'orientation que j'avais prise.
    J'ai déjà les fonctions qui retournent la Box la plus haute et les suivantes dans l'ordre, mais la difficulté réside dans la création du tableau à 2 dimensions car les boites peuvent se retrouver dans plusieurs colonnes du tableau (voir les schémas postés).

    Le reste est facile à traiter ensuite.

    Merci de ta réponse.

Discussions similaires

  1. Formalisation graphique des algorithmes
    Par David R. dans le forum Algorithmes et structures de données
    Réponses: 14
    Dernier message: 08/12/2012, 10h21
  2. Algorithme de randomisation ... ( Hasard ...? )
    Par Anonymous dans le forum Assembleur
    Réponses: 8
    Dernier message: 06/09/2002, 14h25
  3. recherches des cours ou des explications sur les algorithmes
    Par Marcus2211 dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 19/05/2002, 22h18
  4. Recherche de documentation complète en algorithmes
    Par Anonymous dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 29/03/2002, 12h09
  5. Algorithme génétique
    Par Stephane.P_(dis Postef) dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 15/03/2002, 17h14

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