Discussion :

[Jean-Marc.Bourguet]

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.

[pseudocode]

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.

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

Sélectionner tout - Visualiser dans une fenêtre à part

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

[pseudocode]

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

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

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

[pseudocode]

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

[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

[pseudocode]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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)

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

Sélectionner tout - Visualiser dans une fenêtre à part

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

[zuzuu]

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

[pseudocode]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

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

[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é...!?!

[pseudocode]

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.

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.

[alex_pi]

Regardez éventuellement du coté de Xmonad, ils ont plein d'algo différents pour la répartition des fenetres.

[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é...?

[pseudocode]

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

demo-2 (jar)

[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à!

[pseudocode]

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

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

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.

[zuzuu]

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