Rotation de case dans un tableau 2D

Version imprimable

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

21/08/2006, 17h50
Oberown

Rotation de case dans un tableau 2D
J'ai un tableau de 2D de dimension n * n (un carré)

Et je voudrais faire une rotation de mes cases de 90°.

Comment faire ?

Exemple
Code:

1 2 3 1 2 3 4 5 6 7 8 9
Devient
Code:

1 2 3 3 6 9 2 5 8 1 4 7
21/08/2006, 18h02
khayyam90

Bien le bonjour,

Ce qui me vient en tête, c'est de faire une rotation de manière tout à fait conventionelle, à savoir avec la matrice qui va bien.

le centre de rotation est (n/2,n/2), tu calcules donc les coordonnées de chacune de tes cases (par translation de (n/2,n/2)) puis tu leur appliques la matrice de rotation

0, -1
1, 0 , qui d'ailleurs dans ce cas se calcule sans même avoir à poser de produit matriciel
Et pour finir tu réappliques une translation inverse de (n/2,n/2) et tu as tes nouvelles coordonnées.

Et pout faire + algorithmique :
tu crées une matrice n*n vide
tu parcours ta matrice n*n de départ (boucle)
tu fais les étapes décrites précédemment avec la matrice de rotation
tu remplis la nouvelle matrice (fin de la boucle)
tu détruits la première matrice.
21/08/2006, 18h22
roulious

Citation:

Envoyé par khayyam90

Et pout faire + algorithmique :
tu crées une matrice n*n vide
tu parcours ta matrice n*n de départ (boucle)
tu fais les étapes décrites précédemment avec la matrice de rotation
tu remplis la nouvelle matrice (fin de la boucle)
tu détruits la première matrice.

Dans un cas général, mieux vaut parcourir le tableau d'arrivée plutôt que le tableau de départ et lui appliquer la transformation inverse (avec éventuellement une interpolation) : en parcourant le tableau de départ, on risque de "sauter" des cases du tableau d'arrivée et donc de se retrouver avec des cases non initialisées.
21/08/2006, 21h45
buzard

Une matrice de rotation!! Et en inversant le le rôle des indices, c'est pas plus simple?

La rotation de Pi/2 : S[i][j] = T[j][n-1-i]
La rotation de -Pi/2 : S[i][j] = T[n-1-j][i]
La symetrie Central : S[i][j] = T[n-1-i][n-1-j]
La symetrie horizontal : S[i][j] = T[n-1-i][j]
La symetrie vertical : S[i][j] = T[i][n-1-j]
La symetrie diagonal : S[i][j] = T[j][i]
La symetrie anti-diagonal : S[i][j] = T[n-1-j][n-1-i]
L'identité : S[i][j] = T[i][j]

Pourquoi voiloir absolument, faire la rotation. C'est la facon dont tu va acceder qui va determiner l'ordre des données. pourquoi faire un parcourt en O(n^2), si tu peut le remplacer avantageusement par des petites additions et soustraction aux bons endroits.
22/08/2006, 09h50
Oberown

Mon problème c'est la gestion déplacement des cases de départ dans la case d'arrivé.

La solution de khayyam90 me parait la plus simple. Or elle prend le plus de mémoire, si le tableau est grand.

J'ai penché sur une solution de faire dans la même matrice, et d'avoir une variable tmp de type case, pour faire un swap. Mais je n'arrive pas à le gérer.
22/08/2006, 10h48
10_GOTO_10
Citation:

Envoyé par Oberown

J'ai penché sur une solution de faire dans la même matrice, et d'avoir une variable tmp de type case, pour faire un swap. Mais je n'arrive pas à le gérer.

Parce que justement, c'est pas un swap mais une rotation. Dans ton exemple:

1 prend la place du 7
7 prend la place du 9
9 prend la place du 3
3 prend la place du 1

donc je vois deux solutions:
Code:

1 2 3 4 5 Tmp = S[0, 0] S[0] [0] = S[0] [2] S[0] [2] = S[2] [2] S[2] [2] = S[2] [0] S[2] [0] = Tmp
ou bien:
Code:

1 2 3 4 Swap(S[0] [0], S[0] [2]) Swap(S[0] [0], S[2] [2]) Swap(S[0] [0], S[2] [0])
Et pour le cas général, remplace tous les 0 par des i ou des j, et les 2 par des (n - i - 1) ou (n - j - 1).
22/08/2006, 11h10
Nemerle

Disons que ta matrice n*n se repésente par M(i,j) où i,j sont compris entre 1 et n, i représentant le No de ligne et j le No de colonne.

Notons N(i,j) la matrice où on a effectué la rotation de 90 degré.

Alors on a simplement N(i,j) = M(j,n+1-i) !!
22/08/2006, 12h33
buzard
Citation:

Envoyé par Oberown

J'ai penché sur une solution de faire dans la même matrice, et d'avoir une variable tmp de type case, pour faire un swap. Mais je n'arrive pas à le gérer.

pour faire une permutation sur place, tu permute quatre éléments à cahaque fois. ALors tu ne parcourt plus que le quart de ta matrice (sinon tu va revenir à ton etats initiale)
Code:

1 2 3 4 5 6 ###.. ###.. .. .. ..::: ..:::
Fait juste attention à la parité de n, si il est impaire il faudra rajouter un petit morceau.

sinon tu parcourt le triangle :
Code:

1 2 3 4 5 6 ####. .##.. .. .. ..::. .::::
22/08/2006, 14h07
Nemerle

Oubli, mais c'est evident: le swap s'effectue entre (i,j) et (j,n+1-i) !
22/08/2006, 14h53
buzard

Citation:

Envoyé par Nemerle

entre (i,j) et (j,n+1-i) !

c'est n-1-i, si tu considère les tableaux indéxés à partir de 0.
et
n+1-i, si ils sont indéxés à partir de 1.

Personnellement, je préfère les tableaux indéxés à la C, je sais c'est lpus par habitude. L'indéxation à partir de 1 est plus "naturelle", parcequ'on parle bien du i-ème élément à l'index i. Mais bon à un décalage près on s'y retrouve aussi.
22/08/2006, 16h12
Nemerle

Citation:

Envoyé par buzard

c'est n-1-i, si tu considère les tableaux indéxés à partir de 0.
et
n+1-i, si ils sont indéxés à partir de 1.

ce que j'avais dit --> cf + haut: indexés à partir de 1 ;)
22/08/2006, 16h23
Oberown

Merci beaucoup pour la case d'arrivé.

Mais comment gérer le déplacement de la case ? Pour ne pas effacer la case d'arrivé ?
22/08/2006, 17h40
Nemerle

Citation:

Envoyé par Oberown

Merci beaucoup pour la case d'arrivé.

Mais comment gérer le déplacement de la case ? Pour ne pas effacer la case d'arrivé ?

tu as besoin obligatoirement d'une var. tampon, non?
22/08/2006, 17h44
Oberown

Oui, mais je n'arrive pas à gerer.
En gros faut swaper 4 cases de la rotation puis passer à la case d'après. Une fois arrivé au milieu il faut arrêter.
22/08/2006, 18h01
Nemerle

Citation:

Envoyé par Oberown

Oui, mais je n'arrive pas à gerer.
En gros faut swaper 4 cases de la rotation puis passer à la case d'après. Une fois arrivé au milieu il faut arrêter.

je ne comprends pas ton problème!
22/08/2006, 18h03
Oberown

Si on continue de swapper les cases on va les swapper plusieurs fois.
23/08/2006, 11h34
Nemerle

no comprendo senior: tu parcours seulement la moitié des i,j, non?
23/08/2006, 12h05
Oberown

Mon problème c'est de gerer le déplacement de mes cases.
Je sais où est le départ et où est l'arrivé. Mais je ne sais pas omment les déplacer. Vu que le déplacement ce fait dans la même matrice et non dans une matrice de réception.
23/08/2006, 14h04
Nemerle

Bon, la chaîne de rotations x,r(x),rr(x),... où x=(i,j) est une case de ta matrice donne

(i,j) :arrow: (j,n+1-i) :arrow: (n+1-i,n+1-j) :arrow: (n+1-j,i )

et après on revient à (i,j). On a donc 4 valeurs différentes qui s'échangent par permutation circulaire (sauf pour la valeur "centrale" d'une matrice d'ordre impair, valeur qui ne bouge pas).

Donc il faut faire, en notant M(i,j) la matrice ou i,j sont dans 1...n:

Citation:

pour j de 1 à n-1
pour i de j à n-j
a=M(n+1-j,i) //*** variable tampon
M(n+1-j,i )=M(n+1-i,n+1-j)
M(n+1-i,n+1-j)=M(j,n+1-i)
M(j,n+1-i)=M(i,j)
M(i,j)=a
finpour
finpour

le truc était de vérifier que (j varie de 1 à n-1)&(i varie de j à n-j) ;)
23/08/2006, 16h52
10_GOTO_10
Citation:
Envoyé par Nemerle

Code:

1 2 pour j de 1 à n-1 pour i de j à n-j
Heu... Moi j'aurais plutôt dit:
Code:

1 2 pour j de 1 à n / 2 pour i de j à n-j

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