Discussion :

[zuzuu]

Bonjour à tous, et Meilleurs Voeux !!!

Je reviens cette année avec encore (et toujours) des questions !
J'ai presque fini de mettre au point mon algorithme de disposition de fenêtres avec contraintes.

Je voudrais faire appel à vous pour un soucis, qui peut être vous rappellera quelque chose que vous avez déjà vu.

Donc je me lance :
J'ai des rectangles qui sont tous déjà positionnés (aucun ne se chevauche).
Et voici que je voudrais en aggrandir un ou le rétrécir... Cependant, je souhaiterais que les rectangles avoisinant se rétrécissent à leur tour où s'agrandissent afin de laisser de la place ou d'occuper celle qui se libère.

Voilà, c'est mon soucis, seulement il y a une contrainte. En effet, chaque rectangle à une taille maximum et minimum à respecter...
C'est à dire que lorsque l'un est réduit au maximum, il faut que je passe à un autre pour permettre de libérer assez de place pour l'agrandissement du rectangle courant. Et inversément, lorsqu'il s'agit de réduire le rectangle courant...

J'espère que je vous ai donné assez de détails... En attendant, je réfléchie encore un peu...

[ToTo13]

Bonjour,

quel est ton espace de représentation de tes rectangles ?
Si tu es dans un espace discret, cela est facile, sinon il nous faudra être un peu plus fin...

[zuzuu]

Oui, c'est dans un espace discret... Mes rectangles n'ont que des valeurs entieres pour taille.

J'ai omis aussi d'indiquer une contrainte : Les rectangles doivent garder leur proportions (ratio).

Je crois que je suis en bonne voie pour trouver la solution concernant l'agrandissement d'un rectangle (donc la réduction des autres). Ensuite, je ne suis pas sure que ce soit une méthode optimale... Donc je suis preneuse si vous avez des suggestions !

[edfed]

ça à l'air bien casse tete comme truc...
peut etre qu'en faisant des tests de collisions entre les regtangles et le rectangle redimensionné, et en lançant une routine pour chaque collisions, on peu faire ça:

incase collision de "cible" avec rect_redimensionné

case à_gauche?
appliquer l'equation de redimension par la droite de la "cible"
case à_droite?
appliquer l'equation de redimension par la gauche de la "cible"
case en_bas?
appliquer l'equation de redimension par le haut de la "cible"
case en_haut?
appliquer l'equation de redimension par le bas de la "cible"

que doit il se passer si l'on deplace un de ces rectangles, si c'est possible de le faire?
puis si le ratio doit etre conservé, on risque fort d'avoir des trous.

[zuzuu]

Bon finalement pour l'agrandissement d'un rectangle et donc la reduction des autres, je crois que j'ai une solution :
Je vais simuler que je l'ai agrandi, voir quels sont ceux qui sont chevauché, essayer de les reduire, et ainsi de suite tant qu'ils chevauchent eux meme à nouveaux un rectangle voisin. Arrivé contre la limite de la fenetre, j'indique de combien , je ne pourrais pas diminuer plus, et finalement, mon rectangle de base ne pourra être dimuné que de la valeur initiale moins cette dernière valeur.

Pour l'autre cas, je pense que lorsque je vais réduire la taille d'un rectangle, les autres ne vont finalement pas d'agrandir, mais se coller à celui qui diminue tant que cela est possible...

Voilà, si jamais une idée plus ingénieuse vous trottre dans l'esprit, je suis preneuse. En tout cas, je vous remercie !

[ToTo13]

Bonjour,

un espace discret wonderfull.
Une solution super simple c'est de représenter ton espace par un tableau 2D. Chaque case contiendra soit du vide, soit le numéro d'un rectangle.
Cet espace va te permettre de gérer facilement les voisinages et donc de savoir quels sont les rectangles voisins à agrandir ou à réduire.

[zuzuu]

Mais comment tu remplie ton tableau et le lit...
Il peut y avoir de nombreux rectangles voisins :

Exemple :

________________
.....1..........|.2.|.3.|
.................|__|__|
.................|.4.|.5.|
.................|...|...|
________________

[ToTo13]

Bonjour,

Mais comment tu remplie ton tableau et le lit...
Il peut y avoir de nombreux rectangles voisins

ben oui justement, le tableau va te donner tous les voisins :
- Pour un rectangle R (numéro de remplissage = R).
- Tu parcours tous les bords de R et tu listes tous les voisins. Un bord du rectangle est une case du tableau valant R et dont une case voisine est différente de R. En plus tu n'as que des rectangles, donc lorsque tu as deux coins tu connais ton rectangle.

Est ce que tu laisses une marge entre tes rectangles ?

[zuzuu]

Oui il peut y en avoir mais je ne comprends toujours pas ton tableaux... Tu peux me montrer avec un tout petit exemple ce que cela pourait donner...

[edfed]

incase collision de "cible" avec rect_redimensionné

case à_gauche?
appliquer l'equation de redimension par la droite de la "cible"
case à_droite?
appliquer l'equation de redimension par la gauche de la "cible"
case en_bas?
appliquer l'equation de redimension par le haut de la "cible"
case en_haut?
appliquer l'equation de redimension par le bas de la "cible"

ce shemas de base fonctione bien, je l'ai deja essayé, c'est la base de mon moteur 2D, un service de collisions couplé a des conitions de collision.

ça marche.
par contre je n'ai pas encore fait le redimensionement de rectangle, car je n'en suis pas là

[ToTo13]

Bonjour,

Trois rectangle : R 2 3
0 0 0 0 0 0
0 2 2 2 2 0
0 2 2 2 2 0
0 0 0 0 0 0
0 R R 0 0 0
0 R R 0 0 0
0 0 0 0 0 0
0 0 0 3 3 0
0 0 0 3 3 0
0 0 0 0 0 0

voilà.
Tu redimenssionnes le rectangle R. Avec un tableau, il te suffit de parcourir ses bords et de regarder plus ou moins loin en fonction de la taille de la marge afin de trouver ses voisins.
Si tu agrandis dans une direction et qu'il y a un voisin, tu as immédiatement le numéro du voisin et tu peux le réduire.
Inversement quand tu réduis, tu connais les voisins et tu les agrandis.

[edfed]

cette technique a le don de bouffer enormement de temps de cacul, pour faire la sillouette des objets, c'est pas la meilleure maniere pour tester les collisions de rectangles..

[ToTo13]

Bonjour,

cette technique a le don de bouffer enormement de temps de cacul, pour faire la sillouette des objets, c'est pas la meilleure maniere pour tester les collisions de rectangles..

Comme c'est des rectangles, la sillouhette est super rapide à trouvers. En revanche, je suis d'accord qu'elle n'est sans doute pas optimale, mais elle a le mérite d'être simple.

[edfed]

le plus pas drole, c'est que c'est meme pas simple, je l'ai essayée pour faire un moteur de collisions, et bien , c'est limité , et c'est long.
alors qu'avec le calcul des coordonnées, c'est plus rapide, et si les figure sont des formes non rectangulaires, le traçage des contour suffit, pas besoin des pixels interieurs pour detecter par couleurs.
mais par couleurs, le nombre d'objet est limité.
heu... par le nombre de couleurs possibles.
256 en 8 bits
16 millions et des brouettes en 24 bits
4 milliard et des tonneaux en 32 bits.
hum hum.. une combinaison des deux methodes serait pas mal pour un moteur de collisions de jeu video...
voire pour un moteur de collision pour un environement 3D.

je sais pas, il faut tout essayer, mesurer la vitesse d'execution, comparer les precisions, etc...

[JeromeBcx]

Une idée...
En 1 dimension, l'adaptation en 2D est assez facile.

Soit N segments S définis par a bord gauche, b bord droit.

Modification de la distance du segment i de d
On compte le nombre de segments n'ayant pas atteinds leur limite (haute si d<0, basse si d>0) avec Si exclu. Soit K cette valeur. S{k} la liste de ces segments

On calcul le pas p qui affecte la taille des N segments pour chaque segments

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
Si |d| < K, 
p = 1 pour d segments à choisir parmis les S{K} segments
p = 0 pour les autres sauf Si
p = d pour Si
 
Si |d| >=K, 
p = int(K/d)      pour int(K/d)*d parmis les S{K} segments
p = int(K/d) + 1 pour K-int(K/d)*d parmis les S{K} segments
p = 0               pour les autres sauf Si
p = d                pour Si

On calcul les listes pA et pB avec

Code :

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

1
2
3
4
5
6
7
8
9
 
pA[0] = 0
pB[0] = p[0]
 
pour n = 1 à N-2
<div style="margin-left:40px">pA[n] = - p[n]/2 + |pA[n-1]| +  |pB[n-1]|
pB[n] = p[n]/2 + |pA[n-1]| +  |pB[n-1]|</div>
pA[N-1] = - p[n-1] + |pA[N-2]| + |pB[N-1]|
pB[N-1] = 0

On affecte les changements de coordonnées au S{N} segments

Code :

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

1
2
3
4
 
pour n = 0 à N-1
<div style="margin-left:40px">a[n] += pA[n]
b[n] += pB[n]</div>

J'espère qu'aucune coquille ne s'est glissée. Bien sùr à vérifier et valider (surtout signes valeurs absolues).
Il me semble que l'algo reste assez simple à mettre en oeuvre. Peut être gérer une exeption lors du redimensionnement des rectangles aux bords...

En espérant avoir pu aider

Cdt

[souviron34]

bah il n'y a pas besoin de suivre les contours...

Un rectangle :

xmin, xmax
ymin, ymax


Si on augmente xmax (on allonge le rectangle horizontalement)
pour le rectangle i

Code :

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

1
2
3
4
5
6
7
8
9
Pour tous les autres rectangles :
   Si ymin > ymax_i  OU Si ymax < ymin_i OU si xmax < xmin_i OU si xmin > xmax_i
         Rien a faire
   Sinon
         Si xmin < xmax_i
              xmin = xmax_i (+marge)
         Fin si
   Fin si
Fin pour

[EDIT]
Ajoute un _i pour mieux discerner entre les rectangles utilises et le rectyangle de comparaison..
[/EDIT]