Related: Inplace M x N size matrix transpose
You are given a 2D square matrix, or 2D array of integers of size n (n rows and n columns), your output should be n by n 2D matrix rotated by a given angle, which could be +90, -90, +180, -180.
1 4 7 7 4 1
2 5 8 -- 8 5 2
3 6 9 9 6 3
From http://www.geeksforgeeks.org/turn-an-image-by-90-degree/
http://coding-interview-archives.blogspot.com/2013/09/rotate-given-square-matrix-by-90-degrees.html
Read full article from Ashes To Glory: Rotating a 2D array of integers (matrix) by a given angle (+90, -90, +180, -180)
You are given a 2D square matrix, or 2D array of integers of size n (n rows and n columns), your output should be n by n 2D matrix rotated by a given angle, which could be +90, -90, +180, -180.
Rotate by +90 (clockwise once):
Input: n by n matrix M, where n >= 2
Algorithm:
Step 1: Transpose M
Step 2: Reverse each row
Dry run:
Step 1: Transpose
M M'
1 2 3 1 4 7
4 5 6 -- 2 5 8
7 8 9 3 6 9
Step 2: Reverse each row
M' M''
2 5 8 -- 8 5 2
3 6 9 9 6 3
Pseudocode: is here which is self explanatory and easily convertible to source code in a language of your choice.
Transpose
for i in [0, n)
for j in [0, n)
if ( i < j )
swap( M[i][j], M[j][i] )
Reverse a row (rowidx)
start = 0
end = cols - 1
while ( start < end ) {
swap( M[rowidx][start], M[rowidx][end] )
++start
--end
}
Rotate
Transpose
for i in [0, rows)
Reverse( i )
That was fair enough until only asked to rotate by +90 degree. If problem is further extended to be solved for any given angle, of course the rotation should make sense, for example, 47 degree is not a choice ;-). So, here are some elegant techniques (I'll be brief now for other angles, because for +90 degree I have elaborated the solution):
Rotation by -90 degree (anticlockwise once):
Step 1: Transpose
Step 2: Reverse each column
Rotation by +180 degree (clockwise twice): Two methods follows
First:
Rotate input matrix +90 degree twice, if routine for which is available to you
Second: (You'll be amazed!)
Step 1: Reverse each row
Step 2: Reverse each column
Rotation by -180 degree (anticlockwise twice): Three(!!!) methods follows
First:
Rotate input matrix -90 degree twice, if routine for which is available to you
Second: (You'll be amazed again!)
Step 1: Reverse each column
Step 2: Reverse each row
Third: (Aha!)
Because rotating a matrix +180 degree or -180 should produce same result. So you can rotate it by +180 degree using one of above methods.
Turn an image by 90 degree
for(r = 0; r < m; r++) { for(c = 0; c < n; c++) { // Hint: Map each source element indices into // indices of destination matrix element. dest_buffer [ c ] [ m - r - 1 ] = source_buffer [ r ] [ c ]; } }
Code From http://www.emanueleferonato.com/2012/11/07/how-to-rotate-a-two-dimensional-array-by-90-degrees-clockwise-or-counter-clockwise-like-knightfall-game/
https://rosettacode.org/wiki/Matrix_transposition#Javaprivate function rotateCounterClockwise(a:Array):void {var n:int=a.length;for (var i:int=0; i<n/2; i++) {for (var j:int=i; j<n-i-1; j++) {var tmp:String=a[i][j];a[i][j]=a[j][n-i-1];a[j][n-i-1]=a[n-i-1][n-j-1];a[n-i-1][n-j-1]=a[n-j-1][i];a[n-j-1][i]=tmp;}}}private function rotateClockwise(a:Array):void {var n:int=a.length;for (var i:int=0; i<n/2; i++) {for (var j:int=i; j<n-i-1; j++) {var tmp:String=a[i][j];a[i][j]=a[n-j-1][i];a[n-j-1][i]=a[n-i-1][n-j-1];a[n-i-1][n-j-1]=a[j][n-i-1];a[j][n-i-1]=tmp;}}}
double[][] ans = new double[m[0].length][m.length]; for(int rows = 0; rows < m.length; rows++){ for(int cols = 0; cols < m[0].length; cols++){ ans[cols][rows] = m[rows][cols]; } }http://introcs.cs.princeton.edu/java/14array/Transpose.java.html
// transpose in-place for (int i = 0; i < N; i++) { for (int j = i+1; j < N; j++) { int temp = a[i][j]; a[i][j] = a[j][i]; a[j][i] = temp; } }http://analgorithmaday.blogspot.com/2011/04/rotate-array90.html
http://coding-interview-archives.blogspot.com/2013/09/rotate-given-square-matrix-by-90-degrees.html
Read full article from Ashes To Glory: Rotating a 2D array of integers (matrix) by a given angle (+90, -90, +180, -180)