Algorithme de disposition de layout.

Version imprimable

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

12/10/2007, 10h02
zuzuu

Algorithme de disposition de layout.

Bonjour,

Je voudrais savoir si par hasard quelqu'un connaissait un algorithme déjà existant qui permettrait de disposer des fenêtres sur un écran de manière optimale. C'est à dire que chaque fenêtre possède une sorte de proportion (4/3, 16/9 par exemple) et à chaque nouvel ajout d'une fenetre suplémentaire à l'écran, les fenêtres se redimensionne de manière à occuper le plus d'espace possible tout en gardant leurs proportions (elles peuvent être réduite en taille, mais les proportions sont gardées).
13/10/2007, 20h46
acacia

si c'est faisable, ça m'intéresse aussi

mais je ne vois pas comment introduire ça dans un code html puisqu'il s'agit de layout comme indiqué dans le titre.
13/10/2007, 23h03
grob1212

Peux-tu être plus précis ?

Par exemple, est-ce que les fenêtres peuvent être déplacées par la suite ? Est-ce que les proportions des fenêtres sont fixes, y en a-t-il plusieurs ?
14/10/2007, 09h21
PRomu@ld

Ce que tu cherches à faire, c'est un exposé comme sous mac c'est ça ?
22/10/2007, 11h52
zuzuu

Non je n'ai aucun exposé à faire!? A moins que j'ai mal compris ce que tu voulais dire. C'est juste que je me suis posée la question si ce genre d'algorithme qui serait très pratique existait déjà, et je n'ai pas réussi à en trouver...
En fait, le concept serait par exemple que chaque fenetre ait une taille de base qui dépendent de son contenu (exemple une image). Le but est de pouvoir afficher plusieurs de ces images à l'écran de manière à ce que chaque fois que l'on désire afficher une image supplémentaire, celle ci soit visible directement meme si sa taille de toute les fenetres doit un peu diminuer. Mais il faut garder la proportion de chaque image et il faut si possible mettre plus en évidence la dernière image que l'on désire voir.
Par contre, il est possible de limiter le nombre maximale d'image visible en meme temps (par exemple, on ne pourra pas voir plus de 20 image à la fois).
De plus, il faudrait si possible que lorsqu'un image a été ajoutée vers la gauche par exemple. Lors de ces suivants redimmensionnement, elle reste tout de meme vers ce cote...

C'est un peu compliqué, je sais, mais je me suis dit que si l'on réfléchissait à plusieurs ce serait peu être un peu plus facile...
22/10/2007, 12h06
PRomu@ld

Non, on ne s'est pas compris, sous Mac, tu as une application qui s'appelle exposé qui réalise ce que tu veux. Sous linux, dans compiz tu dois avoir une fonctionnalité similaire (mais il me semble que le contenu n'est pas redimensionné en fonction de ses proportions, comme ça se fait sous mac).
22/10/2007, 12h08
pseudocode

Citation:

Envoyé par zuzuu

Non je n'ai aucun exposé à faire!?

Excelent ! :mrgreen:

Si tu as 5 minutes: http://www.youtube.com/watch?v=ktTNcj0fAM4
24/10/2007, 11h11
zuzuu

J'y ai jeté un oeil... En fait, j'avais complètement oublié que mac faisait cela. Le seul truc, c'est qu'il ne doit pas y avoir de vas et viens sur une fenetre.
Mais dans le principe, c'est un peu cela...
Vous savez comment ce genre d'algorithme est réalisé?
24/10/2007, 11h19
pseudocode

Citation:

Envoyé par zuzuu

Mais dans le principe, c'est un peu cela...
Vous savez comment ce genre d'algorithme est réalisé?

Dans Exposé, il y a une contrainte sur la position de la fenetre... En gros, si ta fenetre etait "la plus a gauche" en mode normal, elle est a l'extreme gauche en mode Exposé. C'est cette contrainte qui est la base de l'algorithme. Une fois qu'on a TOUTES les positions (x,y) des fenetres en mode Exposé, la taille n'est pas tres dure a calculer car il faut remplir uniformément l'espace => une sorte de diagramme de Voronoi simplifié.
05/11/2007, 16h22
zuzuu

Bon alors, sans mentir, je regarde un peu depuis un moment à trouver un exemple de l'algorithme de Voronoi "simplifié" qui pourrait s'adapter à cet exemple... en vain... Je ne comprend pas comment on peut gérer l'espace des fenetre en corélation avec cette algorithme, sachant que il serait interessant de repositionner les fenetres et pas seulement dimuniner leur taille...
En fait, je crois que c'est une sorte d'opitmisation de l'espace qui me faudrait avec contrainte (en effet, les fenetres ont chacune une résolution que l'on ne peut déterminer à l'avance !)
06/11/2007, 02h16
souviron34

tu as ce thread ici-même, pointant lui-même sur un autre, et je suis quasi cettain qu'il y en a quelques autres....
06/11/2007, 11h12
FrancisSourd

Une idée serait de partir de fenêtres de taille 0 avec pour position le centre de la fenêtre originelle. Ensuite, on peux itérativement essayer (éventuellement de manière aléatoire) de
- faire (un peu) grossir une fenêtre
- déplacer (un peu) une fenêtre

Si la nouvelle solution est faisable (pas de superposition), on la garde et elle devient solution courante sinon on la rejète et on reste avec la même solution courante.

On s'arête quand on n'arrive plus à améliorer la solution courante pendant un certain nombre d'itérations. Cette méthode est basée sur le principe d'amélioration itérative largement utilisé en optimisation.

On peut biaiser l'aléatoire, de manière à faire grossir plus vite une fenêtre plus importante.
06/11/2007, 20h31
pseudocode

Citation:

Envoyé par zuzuu

Bon alors, sans mentir, je regarde un peu depuis un moment à trouver un exemple de l'algorithme de Voronoi "simplifié" qui pourrait s'adapter à cet exemple... en vain...

:mrgreen: Le terme Voronoi "simplifié" n'est pas du tout standardisé. C'etait juste une maniere d'expliquer le principe.

Une fois qu'on connait la position du centre de chaque fenetre, pour trouver leur taille il faut trouver la plus courte distance entre les fenetres (et le bord de l'ecran). C'est le principe du diagramme de Voronoi. On peut aussi utiliser les cartes de distances.

Bien sur, tout ca ne dit pas comment on trouve la position du centre des fenetres. Comme le dit FrancisSourd, je pense que ca passe par un peu de programmation dynamique. Je me souvient d'avoir codé qqc qui ressemblait a ca: c'etait des cercles et pas des fenetres, donc c'etait plus simple (pas de pb de ratio)
06/11/2007, 21h36
Jean-Marc.Bourguet

Partir des positions initiales du centre des fenetres (en les décalants si deux fenetres ont le même centre). Calculer un diagramme de Voronoi pour ces points. Placer chaque fenetre dans sa région de manière a maximiser sa taille tout en respectant ses proportions (alternative à décaler les fenêtres ayant le même centre: les faire partager une région puis les placer côte à côte). Itérer en prenant cette fois un diagramme basé sur les rectangles plutôt que sur les points (ici il n'y a plus de fenêtres partageant la même région). Ca devrait converger très vite.
07/11/2007, 09h45
zuzuu

Merci, je vais regarder de ce coté là... Sinon, j'ai vu que l'outils ratpoison était un gestionnaire de fenetre dans ce genre. Il maximise l'affichage des fenetres, sans qu'elle se chevauche. Je voudrais essayer de comprendre quel genre d'algorithme ils ont mis en place à partir du code source, mais ce n'est pas très facile de s'y retrouver ^^.
07/11/2007, 15h11
zuzuu

Est ce que vous pensez que c'est possible d'adapter l'algorithme packing pour des cercles pour ce cas en fait. Puisque finalement un rectangle voit ces quatres coins dans un cercle circonscrit? Je ne trouve pas encore comment cet algorithme est implémenté...

1 pièce(s) jointe(s)

Citation:

Envoyé par zuzuu

Est ce que vous pensez que c'est possible d'adapter l'algorithme packing pour des cercles pour ce cas en fait. Puisque finalement un rectangle voit ces quatres coins dans un cercle circonscrit? Je ne trouve pas encore comment cet algorithme est implémenté...

En fait mon algo n'avait pas pour objectif de "maximiser" l'occupation de l'ecran, mais juste d'empecher les recouvrements.

Pièce jointe 21306

On doit pouvoir l'adapter pour mieux occuper l'espace vide, mais ca risque de ne pas etre optimal.

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
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
 
import java.util.Random;
 
public class DvpThread425402 {
 
    static class Circle {
        int x,y,radius;
        public Circle(int x, int y, int r) {
            this.x=x; this.y=y; this.radius=r;
        }
    }
 
    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];
 
            // move direction (vector)
            double dx=0, dy=0;
 
            //  move away from the left/right border
            int bx = 0;
            if (ci.x>(width-ci.x)) bx = width; 
            int da = Math.abs(ci.x-bx);
            if (da<ci.radius) {
                int delta = ci.radius-da;
                dx += delta*Math.signum(ci.x-bx);
                hasmoved = true;
            }
 
            // move away from top/bottom border
            int by = 0;
            if (ci.y>(height-ci.y))    by = height; 
            int db = Math.abs(ci.y-by);
            if (db<ci.radius) {
                int delta = ci.radius-db;
                dy += delta*Math.signum(ci.y-by);
                hasmoved = true;
            }
 
            // 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;
                dx += (delta*(ci.x-cn.x))/dn;
                dy += (delta*(ci.y-cn.y))/dn;
                hasmoved = true;
            }            
 
            // move circle center
            ci.x+=1.0*dx;
            ci.y+=1.0*dy;
        }
 
        return hasmoved;
    }
 
    public static void main(String[] args) {
        int width=320, height=200;
 
        Random random = new Random();
 
        Circle[] circles = new Circle[25];
        for(int i=0;i<circles.length;i++) {
            int x = random.nextInt(width);
            int y = random.nextInt(height);
            int r = random.nextInt(20)+10;
            circles[i] = new Circle(x,y,r);
        }
 
        for(int loop=0;loop<100;loop++)
            if (!move(circles,width,height)) break;
 
    }
 
}

08/11/2007, 10h22
zuzuu

Dis moi si j'ai compris ce que ton algorithme fait :
En fait, tu initialises 25 cercles avec des tailles aléatoires et ensuite tu testes si il est possible de les positionners dans le tableau sans qu'ils se recouvrent sans quoi aprés 100 tentatives, tu arretes.

Bon, pour le début, tu essayés de placer les cercles dans la zone d'affichage.
Ensuite, c'est quoi exactement ce que tu essayes de faire. Tu les positionnes aléatoirement? et tu regardes si ça colle?

Attend, je crois que tu prends en fait à chaque fois le plus pres et tu les pousses en fait...!?
08/11/2007, 12h49
pseudocode

Citation:

Envoyé par zuzuu

Attend, je crois que tu prends en fait à chaque fois le plus pres et tu les pousses en fait...!?

oui, c'est tout a fait ca. :king:

J'ai regardé un peu comment adapater le code pour des rectangles, et ce n'est pas tres compliqué. La principale modification consiste dans la formule pour trouver le rectangle le plus proche: il faut calculer la surface de recouvrement.

Si en plus on ajoute une diminution progressive de la taille des rectangles a chaque tour de boucle, ca converge tres vite. Le probleme c'est de décider si on refait un tour de boucle avec ou sans diminution des tailles. Si on diminue trop souvent la taille, on se retrouve avec plein de petites vignettes. Si on ne diminue pas assez souvent la taille, l'algo ne trouve pas de solution et il reste des rectangles qui se recouvrent. :?
08/11/2007, 14h50
zuzuu

D'accord, je pensais justement à bouger les cercles en prenant compte que ce sont en fait des rectangles.
D'ailleurs, ces rectangles ont un cercle intérieur et un cercle exterieur à prendre en compte selon le coté où se trouvent les autres cercles à comparer...

Sinon, avec ton algorithme, en fait, je peux partir du principe que je positionne mes cercles (rectangles) au centre, et l'algorithme va consiter à les pousser sur le bord, c'est ça?

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