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

---

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.

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.

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.

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.

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

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) !!

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

####. .##.. .. .. ..::. .::::

---

Oubli, mais c'est evident: le swap s'effectue entre (i,j) et (j,n+1-i) !

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.

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

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

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?

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.

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!

Si on continue de swapper les cases on va les swapper plusieurs fois.

no comprendo senior: tu parcours seulement la moitié des i,j, non?

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.

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

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

---

nan-nan, tu peux vérifier, tu as besoin d'aller j'usqu'à n-1 ;)