Algorithme de disposition de layout.

Version imprimable

Voir 40 message(s) de cette discussion en une page

08/11/2007, 15h20
Jean-Marc.Bourguet

Citation:

Envoyé par pseudocode

Si on diminue trop souvent la taille, on se retrouve avec plein de petites vignettes.

Faire une passe d'agrandissement apres. En fait, ma proposition etait basee sur des points puis de l'agrandissement uniquement.
08/11/2007, 16h32
pseudocode

Citation:

Envoyé par Jean-Marc.Bourguet

Faire une passe d'agrandissement apres. En fait, ma proposition etait basee sur des points puis de l'agrandissement uniquement.

Effectivement, je pense que ton idée est la meilleure.
08/11/2007, 16h36
zuzuu
Au fait, speudocode, je viens de réaliser qu'il y a un point de ton algorithme que je ne comprends pas... Je viens de le lancer et je m'aperçoie qu'il y a des cercles qui sont en dehors de la fenetre et d'autre qui se chevauchent...

Je ne comprends pas très bien le passage dans ton code où tu dépaces les cercles du bord. A quoi correspondent pour toi les variables suivantes :
bx?
by?
da?
ah oui, aussi que fait la fonction signum, elle fait ceci? :
Code:

1 2 3 4 5 6 7 8 int signum(int n) { if (n < 0) return -1; if (n > 0) return 1; return n; }

Citation:

Envoyé par zuzuu

Au fait, speudocode, je viens de réaliser qu'il y a un point de ton algorithme que je ne comprends pas... Je viens de le lancer et je m'aperçoie qu'il y a des cercles qui sont en dehors de la fenetre et d'autre qui se chevauchent...

Je ne comprends pas très bien le passage dans ton code où tu dépaces les cercles du bord. A quoi correspondent pour toi les variables suivantes :

Hum... c'est sur que mon code n'etait pas fait au départ pour déplacer des fenetres. Voila une version simplifiée de la methode move() qui devrait etre plus simple a utiliser:

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
 
public static boolean move(Circle[] circles, int width, int height) {
 
        boolean hasmoved=false;
 
        for(int i=0;i<circles.length;i++) {
            Circle ci = circles[i];
 
            // find the nearest circle
            int nearest_recover = 0;
            int nearest_id = -1;
            int nearest_dist = 0;
            for(int j=0;j<circles.length;j++) {
                if (i==j) continue;
                Circle cj = circles[j];
                int dcenter = (int)Math.sqrt((ci.x-cj.x)*(ci.x-cj.x)+(ci.y-cj.y)*(ci.y-cj.y));
                int sumradius = ci.radius+cj.radius;
                int recover = sumradius-dcenter;
                if (recover>nearest_recover) {
                    nearest_recover = recover;
                    nearest_dist = dcenter;
                    nearest_id = j;
                }
            }
 
            //  move away from the nearest circle
            if (nearest_id>=0) {
                Circle cn = circles[nearest_id];
                int dn = (int)nearest_dist;
                int delta = 1 + (ci.radius+cn.radius) - dn;
                ci.x += 1.0*(delta*(ci.x-cn.x))/dn;  // FIXME: dn=0
                ci.y += 1.0*(delta*(ci.y-cn.y))/dn;  // FIXME: dn=0
                hasmoved = true;
            }            
 
            //  limit to screen dimension
            if (ci.x-ci.radius<0) ci.x = ci.radius; 
            if (ci.x+ci.radius>width) ci.x = width-ci.radius; 
            if (ci.y-ci.radius<0) ci.y = ci.radius; 
            if (ci.y+ci.radius>height) ci.y = height-ci.radius; 
        }
 
        return hasmoved;
    }

08/11/2007, 17h25
zuzuu

Je vais regardé de plus prés... pour l'instant en ayant juste repris ton code, je me retrouve avec des cercles très proches les uns des autres et qui se chevauchent quasiment tous ! Hi ^^
08/11/2007, 17h28
pseudocode

Citation:

Envoyé par zuzuu

Je vais regardé de plus prés... pour l'instant en ayant juste repris ton code, je me retrouve avec des cercles très proches les uns des autres et qui se chevauchent quasiment tous ! Hi ^^

Normalement ils ne devraient pas se chevaucher... au pire etre tangents. Sauf si, bien sur, l'algo n'a pas trouvé de solution :?
08/11/2007, 17h35
zuzuu

il n'y aurait pas un problème dans cet algo...? mes cercles sont placés initialement tous au centre, et ils ne bougent pas
08/11/2007, 19h01
pseudocode
Citation:

Envoyé par zuzuu

il n'y aurait pas un problème dans cet algo...? mes cercles sont placés initialement tous au centre, et ils ne bougent pas

bah chez moi ca marche (enfin, ca fait ce que je lui demande). Il y a sans doute un probleme au niveau de ces lignes la:
Code:

1 2 3 ci.x += 1.0*(delta*(ci.x-cn.x))/dn; ci.y += 1.0*(delta*(ci.y-cn.y))/dn;
ce sont des operations sur des entiers alors il faut faire attention. En cas de doute, passe tout le monde en "double".
Code:

1 2 3 4 5 6 double dx = (double)(ci.x-cn.x)/(double)dn; double dy = (double)(ci.y-cn.y)/(double)dn; ci.x = (int)Math.round(ci.x + delta*dx); ci.y = (int)Math.round(ci.y + delta*dy);
Pour tester:

Demo.jar (java)
09/11/2007, 09h53
zuzuu
Sympa ton jar !!

Bon alors, j'ai passé en double, mais pour le detla aussi?

En fait, je code en C++ et je reprend ton code.
Par exemple, pour la méthode round, que je n'avais pas, j'ai mis cela...
Code:

1 2 3 4 5 6 7 int round (double n) { int result = (int) (n + .5); if (result < 0) --result; return result; }
Pour l'instant, cela ne marche toujours pas... Je regarde plus attentivement pour comprend bien ce que ton nouvel algo réalise...
09/11/2007, 10h12
zuzuu

C'est quoi en fait, pour toi le delta??? Je ne comprend pas exactement pourquoi tu le calcules comme cela ?
09/11/2007, 10h18
pseudocode
Citation:

Envoyé par zuzuu

C'est quoi en fait, pour toi le delta??? Je ne comprend pas exactement pourquoi tu le calcules comme cela ?
Code:

1 2 3 4 5 double dx = (double)(ci.x-cn.x)/(double)dn; double dy = (double)(ci.y-cn.y)/(double)dn; ci.x = (int)Math.round(ci.x + delta*dx); ci.y = (int)Math.round(ci.y + delta*dy);
(dx,dy) représente le vecteur direction du déplacement. C'est un vecteur unitaire (norme=1, car on a divisé par dn).

delta représente la "longueur" du déplacement a effectuer, dans la direction du vecteur (dx,dy). Cette longueur est egale a la taille du recouvrement des cercles, c'est a dire: (somme des 2 rayons)-(distance entre les centres).

Une fois qu'on a effectué le deplacement de longueur "delta", les 2 cercles deviennent tangeants.
09/11/2007, 10h28
zuzuu

C'est le calcul de delta que je ne comprends pas... J'ai l'impression que tu prenais le mauvaus bout de rayon.
Pourquoi tu rajoutes +1?
09/11/2007, 10h39
zuzuu

D'ailleurs je viens de réaliser... Si tu places tes cercles tous au centre avant de les réageancer, la direction va être la meme pour tout le monde... et les suivants à être placés, vont commencé à recouvrir ceux qui viennent précédement d'etre placé...!?!
09/11/2007, 11h14
pseudocode

Citation:

Envoyé par zuzuu

C'est le calcul de delta que je ne comprends pas... J'ai l'impression que tu prenais le mauvaus bout de rayon.
Pourquoi tu rajoutes +1?

le +1 c'est a cause de la troncature double/int de la distance . La distance est calculée par une racine carrée (type double) qui est tronquée en type int. Le résultat obtenu (le int) est donc toujours plus petit que la distance réelle (le double).

Ce qui fait que le "delta" est toujours trop petit, donc j'ajoute 1 pour corriger ce probleme.

Citation:

Envoyé par zuzuu

D'ailleurs je viens de réaliser... Si tu places tes cercles tous au centre avant de les réageancer, la direction va être la meme pour tout le monde... et les suivants à être placés, vont commencé à recouvrir ceux qui viennent précédement d'etre placé...!?!

Mon algo ne gere pas le cas ou 2 cercles ont exactement le meme centre. Dans ce cas la, je ne peux pas décider quelle est la direction du déplacement a effectuer: il faudrait choisir une direction aléatoire.Dans les autres cas, je peux toujours calculer la direction du déplacement.

Il ne faut pas oublier non plus que la position des centres des cercles change a mesure que la boucle se déroule, et donc que la direction du déplacement d'un cercle ne peut pas etre connue tant que les cercles précédants n'ont pas bougés.
09/11/2007, 14h09
alex_pi

Regardez éventuellement du coté de Xmonad, ils ont plein d'algo différents pour la répartition des fenetres.
09/11/2007, 14h17
zuzuu

Je regarde cela, j'avais aussi vu dans le meme genre ratpoison. Mais en fait, on peut récupérer directement leur code, apres faut fouiller, je ne vois pas comment trouver par exemple le principe de leur algorithme sans avoir à recomprendre tout ce qu'ils ont codé...?
09/11/2007, 19h07
pseudocode

J'ai fait une variante de mon jar, qui est peut etre plus pres de ce que tu souhaites:

demo-2 (jar)
12/11/2007, 09h56
zuzuu

Ah oui ! Ce jar est très sympa... Tu as fais comment?
C'est exactement cela !!! Et je vois que quand il y en a trop, ils se chevauchent un peu, mais c'est pas trop grave puisque apres je mettrais des rectangles à l'interieur !
Et puis en gros j'aurais juste une petite modification à faire, en augmentant ou reduisant la taille d'autre triangle de meme nature à chaque ajout d'un nouvel ajout !

J'aimerais bien savoir en fait comment tu as réussi aussi à penser pour en arriver là!

Citation:

Envoyé par zuzuu

Ah oui ! Ce jar est très sympa... Tu as fais comment?
C'est exactement cela !!! Et je vois que quand il y en a trop, ils se chevauchent un peu, mais c'est pas trop grave puisque apres je mettrais des rectangles à l'interieur !

Le source est dans le Jar. Voila la fonction principale de déplacement:
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 public static boolean move(double speed) { boolean hasmoved = false; // for each circle in the list for (int i = 0; i < circles.length; i++) { Circle ci = circles[i]; // move remaining overlapping circles for (int j = i+1; j < circles.length; j++) { Circle cj = circles[j]; int dcenter = (int) Math.sqrt((ci.x - cj.x) * (ci.x - cj.x) + (ci.y - cj.y) * (ci.y - cj.y)); int sumradius = ci.radius + cj.radius; int recover = sumradius - dcenter; if (recover < 0) continue; // move both circles (one in each direction, half the distance) int delta = recover/2; delta = (int) Math.max(1.0, speed * delta); double dx = (double) (ci.x - cj.x) / (double) dcenter; double dy = (double) (ci.y - cj.y) / (double) dcenter; ci.x = (int) Math.round(ci.x + delta * dx); // circle 1 ci.y = (int) Math.round(ci.y + delta * dy); // cj.x = (int) Math.round(cj.x - delta * dx); // circle 2 cj.y = (int) Math.round(cj.y - delta * dy); // hasmoved = true; } // limit to screen dimension if (ci.x - ci.radius < 0) ci.x = ci.radius; if (ci.x + ci.radius > width) ci.x = width - ci.radius; if (ci.y - ci.radius < 0) ci.y = ci.radius; if (ci.y + ci.radius > height) ci.y = height - ci.radius; } return hasmoved; }
Donc, en gros, on prend chaque cercle dans la liste (le 1er for(i=0;...) ) et on parcours tous les cercles suivants (le 2nd for(j=i+1;...)).

Si les 2 cercles se recouvrent, on les déplace CHACUN dans une direction opposée (= ils se repoussent mutuellement).

Pour faire cela, on calcule:
1. la distance de recouvrement (= somme des rayons - distance intercentres)
2. le vecteur direction (= droite passant par les centres)

Puis on effectur le déplacement:
Cercle 1: centre = centre + distance/2 * vecteur_direction
Cercle 2: centre = centre - distance/2 * vecteur_direction

Voila, on a fini de bouger tous les cercles. Comme ces déplacements peuvent a nouveau creer de recouvrement, on reappelle la fonction move() tant qu'il y a des recouvrements.

Le parametre "speed" (vitesse) permet de réduire la distance de déplacement. En réduisant progressivement la vitesse a chaque appel de move(), on evite que les mouvements deviennent chaotiques lorsqu'il y a trop de chevauchement. C'est ce qui permet d'obtenir une solution "approchée" lorsqu'il y a beaucoup de cercles: les cercles se recouvrent au minimum.

Citation:

Envoyé par zuzuu

J'aimerais bien savoir en fait comment tu as réussi aussi à penser pour en arriver là!

Ce sont des principes de base de la programmation dynamique adaptés à la simulation de système physique (:aie). Essaye de voir ca comme des billes posées dans une boite rectangulaire, vue du dessus. Quand tu ajoutes une nouvelle bille, elle "pousse" les autres billes jusqu'a trouver une place.

http://www.llerrah.com/images/thousand_marble3.jpg

12/11/2007, 10h33
zuzuu

Merci, je vais tester ton jar à la sauce C++ ;)

Voir 40 message(s) de cette discussion en une page